2023年6月22日发(作者：)

「算法」⼆叉树的四种遍历⽅式和⼀些题⽬⽂章⽬录⼆叉树的基本概念⼆叉树（binary tree）是

n(n>=0) 个结点的有限集合，该集合或者为空集（称为空⼆叉树），或者由⼀个根结点以及两棵互不相交的、分别称为根节点的左⼦树和右⼦树的⼆叉树组成。每个根节点最多只有两个⼦节点的就叫做⼆叉树。⼆叉树的特点每个结点最多有两棵⼦树，所以⼆叉树中不存在度⼤于 2 的结点。注意不是只有两棵⼦树，⽽是最多有。没有⼦树或者有⼀棵⼦树都是可以的。左⼦树和右⼦树是有顺序的，次序不能任意颠倒。即使树中某结点只有⼀棵⼦树，也要区分它是左⼦树还是右⼦树。完全⼆叉树对于⼀棵具有 n 个节点的⼆叉树按照层序编号，如果编号为

i(1<=i<=n) 的节点与同样深度的满⼆叉树中编号为 i 的节点在⼆叉树中位置完全相同，则这棵⼆叉树称为”完全⼆叉树“。如下图：把完全⼆叉树的节点与同样深度的满⼆叉树各个节点进⾏编号⽐较，所有节点出现的位置相同，则是完全⼆叉树。所以，满⼆叉树⼀定是⼀棵完全⼆叉树，⽽完全⼆叉树不⼀定是满⼆叉树。完全⼆叉树的深度：h=[log2(n+1)]+1 ([ ]表⽰向下取整）完全⼆叉树的特点：叶⼦节点只能出现在最下两层。最下层的叶⼦⼀定集中左部连续位置。倒数第⼆层，若有叶⼦节点，⼀定都在右部连续位置。如果结点度为1，则该结点只有左孩⼦，即不存在右⼦树的情况。同样节点的⼆叉树，完全⼆叉树的深度最⼩。⼆叉树的存储结构1、⼆叉树顺序存储结构⼆叉树的顺序存储结构就是⽤⼀维数组存储⼆叉树中的结点，井且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。顺序存储⼀般只⽤于完全⼆叉树。2、⼆叉链表⼆叉树每个结点最多有两个孩⼦，所以为官设计⼀个数据域和两个指针域，我们称这样的链表叫做⼆叉链表。typedef struct BiTNode{ TElemType data; //结点数据 struct BiTNode *lchild, *rchild; //左右孩⼦结点} BiTNode, *BiTree;⼆叉树的遍历⼆叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问⼆叉树中所有结点，使得每个结点被访问⼀次且仅被访问⼀次。前序遍历规则是若⼆叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左⼦树，再前序遍历右⼦树。递归实现：void PreOrderTraverse(BiTree T) { if (T == NULL) return; cout << T->val; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchile); }⾮递归实现：使⽤栈来实现前序遍历，⾸先将根节点压⼊栈中，然后打印栈顶元素。⼊栈和出栈的顺序是相反的，所以我们先将根节点的右⼦节点压⼊栈中，然后将左⼦节点也压⼊栈中，打印栈顶元素。操作完元素后让栈顶元素出栈，在压⼊该元素节点的右、左⼦节点，以此操作即可得出⼆叉树的前序遍历元素。void PreOrderTraverse(BiTree T){ if (T == NULL) return; stack bi_tree; bi_(T->data); //

先将根节点压⼊栈中 while (!bi_()) { BiTree* top = bi_(); cout << top->val; //

对栈顶元素操作 bi_(); //

栈顶元素出栈 if (top->rchild != NULL) //

压⼊该元素节点的右⼦节点 bi_(top->rchild); if (top->lchild != NULL) //

压⼊该元素节点的左⼦节点 bi_(top->lchild); }}中序遍历若树为空，则空操作返回。否则从根节点开始（并不是先访问根节点），中序遍历根节点的左⼦树，然后访问根节点，最后中序遍历右⼦树。递归实现： void InOrderTraverse(BiTree T) { if (T == NULL) return; InOrderTraverse(T->lchild); cout << T->val; InOrderTraverse(T->rchild); }⾮递归实现：使⽤栈来实现⼆叉树的中序遍历，先将根节点压⼊栈中，然后⼀直遍历左⼦节点并压⼊栈中。完成之后将栈顶元素节点出栈并操作，再将出栈的这个节点的右⼦节点压⼊栈中，重复上述操作。void InOrderTraverse(TreeNode* root){ if (root == nullptr) return; stack bi_tree; while (!bi_() || root != nullptr) { while (root != nullptr) { //

遍历左⼦节点并压⼊栈中 bi_(root); root = root->left; } root = bi_(); //

栈顶元素出栈 bi_(); cout << root->val; //

操作元素 root = root->right; //

将右⼦节点压⼊栈中 }}后序遍历规则是若树为空，则空操作返回，否则从左到右先叶⼦后结点的⽅式遍历访问左右⼦树，最后是访问根结点。递归实现：void PostOrderTraverse(BiTree T){ if (T == NULL) return; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout << T->val;}⾮递归实现：使⽤两个栈来实现⼆叉树的后序遍历，我们很容易得到⼀种遍历⽅式：“根节点 -> 右⼦节点 -> 左⼦节点”，这种遍历⽅式是后序遍历的反序。根据栈 LIFO 的特性就可以实现后序遍历。因此我们使⽤⼀个辅助栈来保存⽗节点，使⽤另⼀个栈保存我们需要的遍历结果的反序。void postOrderTraverse(TreeNode* root){

if (root == nullptr) return; stack res; stack tmp; (root); while (!()) { TreeNode* top = (); (); if (top->left != nullptr) (top->left); if (top->right != nullptr) (top->right); (top); } while (!()) { top = (); cout << top->val; (); }}层序遍历规则是若树为空，则空操作返回，否则从树的第⼀层，也就是根结点开始访问，从上⽽下逐层遍历，在同⼀层中，按从左到右的顺序对结点逐个访问。即对⼆叉树的⼴度优先搜索（BFS）。对于层序遍历，我们可以借助队列 queue 容器来实现，⾸先压⼊根节点，每次遍历我们⽤队列⾸元素遍历其左⼦节点并⼊队，然后遍历其右⼦节点并⼊队，最后将队⾸元素打印并出队，⼀次迭代直到队列为空。void levelOrderTraverse(TreeNode* root){ queue level_node; if (root == nullptr) return; level_(root); while (!level_()) { TreeNode* front = level_(); if (front->left != nullptr) level_(front->left); if (front->right != nullptr) level_(front->right); cout << front->val; level_(); } cout << endl;}⼆叉树的相关题⽬1. 重建⼆叉树题⽬描述：输⼊⼆叉树的前序遍历和中序遍历结果，重建⼆叉树。算法分析：如前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，根据前序遍历特点，⼆叉树根节点为 1，在中序遍历序列中找到根节点 1，则根节点的前三个节点为左⼦树节点，后⾯的节点为右⼦树节点。根据中序遍历得到的结果，在前序遍历序列中根节点 1 后⾯的三个节点即为左⼦树节点。BinaryTreeNode* Construct(int* preorder, int* inorder, int length){ if (preorder == nullptr || inorder == nullptr || length <= 0) return nullptr; return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);}BinaryTreeNode* ConstructCore(int* stratPreorder, int* endPreorder int* startInorder, int* endInorder){ //

前序遍历第⼀个数字就是根节点的值，初始化⼀个⼆叉树 int rootValue = startPreorder; BinaryTreeNode* root = new BinaryTreeNode(); root->m_value = rootValue; root->m_pLeft = root->m_pRight = nullptr;

if (startPreorder == endPreorder) { if (startInorder == endInorder && *startPreorder == *startInorder) return root; else throw std::exception("Invalid input."); }

//

在中序遍历序列中找到根节点的值 int* rootInorder = startInorder; while (rootInorder <= endInorder && *rootInorder != rootValue) ++rootInorder;

if (rootInorder == endInorder && *rootInorder != rootValue) throw std::exception("Invalid input.");

int leftLength = rootInorder - startInorder; int *leftPreorderEnd = startPreorder + leftLength; if (leftLength > 0) { //

构建左⼦树 root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1); } if (leftLength < endPreorder - startPreorder) { //

构建右⼦树 root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder); } return root;}2. ⼆叉树的下⼀个节点题⽬描述：给定⼀个⼆叉树和其中的⼀个节点，找到中序遍历序列的下⼀个节点。树中节点有两个指向左右⼦节点的指针，和⼀个指向⽗节点的指针。算法分析：分为三种情况：1）⼀个节点如果有右⼦树，则下⼀个节点就是它的右⼦树中最左⼦节点；2）节点没有右⼦树，且它是⽗节点的左⼦节点，则下⼀个节点就是它的⽗节点；3）节点没有右⼦树，且是⽗节点的右⼦节点，这种情况⽐较复杂，我们需要沿指向它⽗节点的指针⼀直向上遍历，直到找到⼀个节点是其⽗节点的左⼦节点，则这个节点的⽗节点就是下⼀个节点。BinaryTreeNode* GetNext(BinaryTreeNext* pNode){ if (pNode == nullptr) return nullptr;

BinaryTreeNode* pNext = nullptr; //

情况1 if (pNode->m_right != nullptr) { BinaryTreeNode* pRight = pNode->m_right; while (pRight->m_left != nullptr) pRight = pRight->m_left; pNext = pRight; } //

情况2和3 else if(pNode->m_parent != nullptr) { BinartTreeNode* pCurrent = pNode; BinaryTreeNode* pParent = pNode->m_parent; while (pParent != nullptr && pCurrent == pParent->m_right) { pCurrent = pParent; pParent = pParent->m_parent; } pNext = pParent; } return pNext;}3. ⼆叉树的⼦结构题⽬描述：输⼊两颗⼆叉树 A 和 B，判断 B 是不是 A 的⼦结构。算法分析：查找树 A 中是否有和树 B ⼀样的⼦结构，可以分为两步：1）在树 A 中找到和树 B 根节点值⼀样的节点 R；2）判断 A 中以 R为根节点的⼦树是不是包含和树 B ⼀样的结构。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isSubStructure(TreeNode* A, TreeNode* B) { bool result = false; if (A != nullptr && B != nullptr) { if (Equal(A->val, B->val)) result = DoesAHaveB(A, B); if (!result) result = isSubStructure(A->left, B); if (!result) result = isSubStructure(A->right, B); } return result; } bool DoesAHaveB(TreeNode* A, TreeNode* B) { if (B == nullptr) return true; if (A == nullptr) return false; if (!Equal(A->val, B->val)) return false; return DoesAHaveB(A->left, B->left)

&& DoesAHaveB(A->right, B->right); } bool Equal(int num1, int num2) { return num1 == num2 ? true : false; }};4. ⼆叉树的镜像题⽬描述：完成⼀个函数，输出⼀棵⼆叉树的镜像。算法分析：前序遍历⼆叉树，如果遍历的节点有⼦节点，就交换两个⼦节点的位置。class Solution {public: TreeNode* mirrorTree(TreeNode* root) { if (root == nullptr) return nullptr; if (root->left == nullptr && root->right) return nullptr; TreeNode* pNode = root->left; root->left = root->right; root->right = pNode; if (root->left != nullptr) root->left = mirrorTree(root->left); if (root->right != nullptr) root->right = mirrorTree(root->right); return root; }};