二叉树遍历与操作全解析

二叉树操作全解析从基础遍历到高级应用1. 二叉树基础概念与遍历算法1.1 前序遍历前序遍历遵循根-左-右的顺序访问节点。对于当前节点先输出该节点然后输出它的左孩子最后输出它的右孩子。递归实现void PreOrderRec(Node * node) { if(node nullptr) return; cout node-data ; // 先输出当前结点 PreOrderRec(node-left); // 然后输出左孩子 PreOrderRec(node-right); // 最后输出右孩子 }非递归实现利用栈模拟递归过程void PreOrderNonRec(Node * node) { if(node nullptr) return; stackNode* S; cout node-data ; S.push(node); node node-left; while(!S.empty() || node) { while(node) { cout node-data ; // 先输出当前结点 S.push(node); node node-left; // 然后输出左孩子 } // while结束意味着左孩子已经全部输出 node S.top()-right; // 最后输出右孩子 S.pop(); } }1.2 中序遍历中序遍历遵循左-根-右的顺序。对于当前节点先输出它的左孩子然后输出该节点最后输出它的右孩子。递归实现void InOrderRec(Node * node) { if(node nullptr) return; InOrderRec(node-left); // 先输出左孩子 cout node-data ; // 然后输出当前结点 InOrderRec(node-right); // 最后输出右孩子 }非递归实现void InOrderNonRec(Node * node) { if(node nullptr) return; stackNode* S; S.push(node); node node-left; while(!S.empty() || node) { while(node) { S.push(node); node node-left; } // while结束意味着左孩子为空 cout S.top()-data ; // 左孩子已经全部输出接着输出当前结点 node S.top()-right; // 左孩子全部输出当前结点也输出后最后输出右孩子 S.pop(); } }1.3 后序遍历后序遍历遵循左-右-根的顺序。对于当前节点先输出它的左孩子然后输出它的右孩子最后输出该节点。递归实现void PostOrderRec(Node * node) { if(node nullptr) return; PostOrderRec(node-left); // 先输出左孩子 PostOrderRec(node-right); // 然后输出右孩子 cout node-data ; // 最后输出当前结点 }非递归实现较为复杂需要记录前一个访问的节点void PostOrderNonRec(Node * node) { if(node nullptr) return; Node * pre nullptr; stackNode* S; S.push(node); while(!S.empty()) { node S.top(); if((!node-left !node-left) || // 第一个输出的必是无左右孩子的叶子结点 (pre (pre node-left || pre node-right))) { cout node-data ; // 左右孩子都全部输出再输出当前结点 pre node; S.pop(); } else { if(node-right) S.push(node-right); // 先进右孩子再进左孩子取出来的才是左孩子 if(node-left) S.push(node-left); } } }2. 层次遍历与基本操作2.1 层次遍历层次遍历使用队列实现按层输出节点void LevelOrder(Node * node) { Node * p node; queueNode* Q; // 队列 Q.push(p); while(!Q.empty()) { p Q.front(); cout p-data ; Q.pop(); if(p-left) Q.push(p-left); // 注意顺序先进左孩子 if(p-right) Q.push(p-right); } }2.2 基本统计操作求树的节点数int CountNodes(Node * node) { if(node nullptr) return 0; return CountNodes(node-left) CountNodes(node-right) 1; }求树的叶子数int CountLeaves(Node * node) { if(node nullptr) return 0; if(!node-left !node-right) return 1; return CountLeaves(node-left) CountLeaves(node-right); }求树的深度int GetDepth(Node * node) { if(node nullptr) return 0; int left_depth GetDepth(node-left) 1; int right_depth GetDepth(node-right) 1; return left_depth right_depth ? left_depth : right_depth; }求二叉树第k层的节点个数int GetKLevel(Node * node, int k) { if(node nullptr) return 0; if(k 1) return 1; return GetKLevel(node-left, k - 1) GetKLevel(node-right, k - 1); }3. 高级二叉树操作3.1 判断两棵二叉树结构是否相同bool StructureCmp(Node * node1, Node * node2) { if(node1 nullptr node2 nullptr) return true; else if(node1 nullptr || node2 nullptr) return false; return StructureCmp(node1-left, node2-left) StructureCmp(node1-right, node2-right); }3.2 求二叉树的镜像void Mirror(Node * node) { if(node nullptr) return; Node * temp node-left; node-left node-right; node-right temp; Mirror(node-left); Mirror(node-right); }3.3 求两个节点的最低公共祖先(LCA)Node * FindLCA(Node * node, Node * target1, Node * target2) { if(node nullptr) return nullptr; if(node target1 || node target2) return node; Node * left FindLCA(node-left, target1, target2); Node * right FindLCA(node-right, target1, target2); if(left right) // 分别在左右子树 return node; return left ? left : right; // 都在左子树或右子树 }3.4 求任意两节点距离int FindLevel(Node * node, Node * target) { if(node nullptr) return -1; if(node target) return 0; int level FindLevel(node-left, target); // 先在左子树找 if(level -1) level FindLevel(node-right, target); // 如果左子树没找到在右子树找 if(level ! -1) // 找到了回溯 return level 1; return -1; // 如果左右子树都没找到 } int DistanceNodes(Node * node, Node * target1, Node * target2) { Node * lca FindLCA(node, target1, target2); // 找到最低公共祖先结点 int level1 FindLevel(lca, target1); int level2 FindLevel(lca, target2); return level1 level2; }4. 进阶二叉树算法4.1 Morris遍历算法Morris遍历可以在不使用栈和递归的情况下完成二叉树遍历空间复杂度为O(1)。前序遍历void PreOrderMorris(Node * root) { Node * cur root; Node * pre nullptr; while(cur) { if(cur-left nullptr) // 步骤1 { cout cur-data ; cur cur-right; } else { pre cur-left; while(pre-right pre-right ! cur) // 步骤2找到cur的前驱结点 pre pre-right; if(pre-right nullptr) // 步骤2.1cur未被访问将cur结点作为其前驱结点的右孩子 { cout cur-data ; pre-right cur; cur cur-left; } else // 步骤2.2cur已被访问恢复树的原有结构更改right指针 { pre-right nullptr; cur cur-right; } } } }中序遍历void InOrderMorris(Node * root) { Node * cur root; Node * pre nullptr; while(cur) { if(cur-left nullptr) //1 { cout cur-data ; cur cur-right; } else { pre cur-left; while(pre-right pre-right ! cur) //2找到cur的前驱结点 pre pre-right; if(pre-right nullptr) //2.1cur未被访问将cur结点作为其前驱结点的右孩子 { pre-right cur; cur cur-left; } else //2.2cur已被访问恢复树的原有结构更改right指针 { cout cur-data ; pre-right nullptr; cur cur-right; } } } }后序遍历后序遍历的Morris算法较为复杂需要建立虚假根节点并实现倒序输出功能void ReversePrint(Node * from, Node * to) { if(from to) { cout from-data ; return; } ReversePrint(from-right, to); cout from-data ; } void PostOrderMorris(Node * root) { Node * dummy new Node(-1, root, nullptr); // 一个虚假根结点 Node * cur dummy; Node * pre nullptr; while(cur) { if(cur-left nullptr) // 步骤1 cur cur-right; else { pre cur-left; while(pre-right pre-right ! cur) // 步骤2找到cur的前驱结点 pre pre-right; if(pre-right nullptr) // 步骤2.1cur未被访问将cur结点作为其前驱结点的右孩子 { pre-right cur; cur cur-left; } else // 步骤2.2cur已被访问恢复树的原有结构更改right指针 { pre-right nullptr; ReversePrint(cur-left, pre); cur cur-right; } } } }5. 二叉树与序列转换5.1 前序中序推后序给定前序和中序遍历序列可以推导出后序遍历序列int pre_order_arry[n]; int in_order_arry[n]; void PrintPostOrder(int pos1, int pos2, int n) { if(n 1) { cout pre_order_arry[pos1]; return; } if(n 0) return; int i 0; for(; pre_order_arry[pos1] ! in_order_arry[pos2 i]; i) ; PrintPostOrder(pos1 1, pos2, i); PrintPostOrder(pos1 i 1, pos2 i 1, n - i - 1); cout pre_order_arry[pos1]; }5.2 有序链表转化为平衡二叉查找树TreeNode * SortedListToBST(ListNode * list_node) { if(!list_node) return nullptr; if(!list_node-next) return new TreeNode(list_node-data); // 用快慢指针找到中间结点 ListNode * pre_slow nullptr; // 记录慢指针的前一个结点 ListNode * slow list_node; // 慢指针 ListNode * fast list_node; // 快指针 while(fast fast-next) { pre_slow slow; slow slow-next; fast fast-next-next; } TreeNode * mid new TreeNode(slow-data); // 分别递归左右两部分 if(pre_slow) { pre_slow-next nullptr; mid-left SortedListToBST(list_node); } mid-right SortedListToBST(slow-next); return mid; }6. 二叉查找树特殊操作6.1 判断是否是二叉查找树bool IsBST(Node * node, int min, int max) { if(node nullptr) return true; if(node-data min || node-data max) return false; return IsBST(node-left, min, node-data) IsBST(node-right, node-data, max); }6.2 二分查找树转化为排序的循环双链表Node * Append(Node * a, Node * b) { if(a nullptr) return b; if(b nullptr) return a; // 分别得到两个链表的最后一个元素 Node * a_last a-left; Node * b_last b-left; // 将两个链表头尾相连 a_last-right b; b-left a_last; a-left b_last; b_last-right a; return a; } Node * TreeToList(Node * node) { if(node nullptr) return nullptr; // 递归解决子树 Node * left_list TreeToList(node-left); Node * right_list TreeToList(node-right); // 把根结点转换为一个结点的双链表方便后面的链表合并 node-left node; node-right node; // 合并之后即为升序排列 left_list Append(left_list, node); left_list Append(left_list, right_list); return left_list; }