其他二叉树知识！二叉树知识汇总

---

目录

二叉树的几种遍历方式

一、先序遍历，中序遍历，后序遍历的常见递归版本

二、迭代版本的实现三种遍历

中序遍历：

先序遍历：

后序遍历：

三、层次遍历

四、DFS和BFS遍历

---

二叉树的几种遍历方式

 

关于二叉树的存储方式，在汇总中可以找到。

一、先序遍历，中序遍历，后序遍历的常见递归版本

void Pre_Order(Node* t){ //先序 if (t==NULL) return; cout << t->data << " "; Pre_Order(t->leftchild); Pre_Order(t->rightchild); } void In_Order(Node* t){ //中序 if (t==NULL) return; In_Order(t->leftchild); cout<<t->data<<" "; In_Order(t->rightchild); } void Post_Order(Node* t){ //后序 if (t==NULL) return; Post_Order(t->leftchild); Post_Order(t->rightchild); cout<< t->data << " "; }

 

二、迭代版本的实现三种遍历

中序遍历：

void D_In_Order(Node* root){ stack<Node*> s; Node* t=root; while ( (!s.empty()) || (t!=NULL) ){ while (t!=NULL){ //从当前的"根"出发，找到最左的节点 s.push(t); t=t->leftchild; } t=s.top(); cout<<t->data<<" "; //输出这个节点 s.pop(); t=t->rightchild; //再管右子树 } }

从宏观上：

中序遍历，要先把左子树遍历完，再输出根节点，再去遍历右子树。 所以我们最开始，一定要去找这根树的最左最底层的那个节点，这个节点的特征就是左孩子是空。 找到这个节点，我们就可以输出它，然后继续查看它的右孩子。 右孩子不管是空还是非空，我们都可以把右孩子本身当成一个新的树根来看，用上述方法再去遍历。

代码段的作用：

代码5-8行：指针t会一直深入，直到最底层的左孩子，这样一次操作可以保证其父亲节点的左孩子一定是被检查完毕的，可以处理父亲节点了。

代码9-11行：将指针t指向栈顶，输出这个元素，然后同时出栈。 执行这个操作分为两种情况：情况一：t 此时是指向一个节点的左空孩子节点，也就是说t==NULL是因为执行了5-8行的while循环。while循环一路向左下找，之后，我们的t不断更新，最终变成了最底层的左孩子节点1的左空指针(t==NULL)。既然 t 已经到达了最底层，说明没有左孩子了，中序遍历处理完左孩子，那么就可以输出根节点了，操作也就是把  t 更新为栈顶，也就是其父亲，然后输出他。                    情况二：指针 t 指向的是一个节点的右空孩子节点。t==NULL并不是因为执行了5-8行的while，而是因为第12行，例如指向了节点1的右空孩子，当一个节点的右孩子为空，也就是右孩子也处理完了，那么这个节点1的全部我们都处理完了，而节点1作为一个整体，它又是节点2的左孩子，所以我们这时还是需要操作把t指向栈顶，也就是节点2，然后输出他。小总结一下：代码的9-11行为什么可以直接输出栈顶元素？要么是左孩子是空，输出其父亲，要么是右孩子为空，代表整体一棵左子树完成，输出其左子树的父亲。

代码12行：中序遍历，当t的左孩子访问完了，自己本身也已经输出了，这时要再查看右孩子，把t=t->rightchild，这里也是递归的实现，t变成了代表右孩子的一个整体，若是存在右孩子，那么t会按照之前的一套再重新访问，如果没有右孩子，那么t=NULL的这个标志也会让代码9-11行知道，整个 t 所在的左子树结束了，t 又借助栈往上跳了一层。

栈的作用：每个节点都会入栈出栈一次。入栈的时候，并且在栈内的顺序是：栈底层的元素是栈顶层元素的祖先。更重要的特性是：每次正在处理的都是栈顶元素top()的左子树。这个很神奇，与算法设计有关，所以我们可以在代码9-11行放心的直接让 t 指向栈顶。

结合这个图对代码进行解释：

自始至终这个t指针都可以看成“根”，只不过最开始我1们初始化t为真正的树根，后边t代表的是以t为根的树。

首先，利用 5-8行的while循环找到了“以t为根的这棵树”的最左节点。这个过程需要用到栈，因为从根遍历到最左节点是一个从上到下的顺序，而我们中序遍历是先左再根，是一个从下往上的顺序，必然用栈来存储这个顺序关系，以便在处理完子树返回上一层。

在这个例子中，显然t的变化过程式1 2 4 NULL，栈里面是1 2 4

然后9-11行代码就可以直接输出这个栈顶节点4了，因为当前的t已经指向了最左节点的空指针，已经到头了，说明节点4不存在左孩子了，直接放心输出即可。这个过程中t指向了栈顶节点，代表着当前要检查的对象是节点4。

第12行代码的目的是查看t的右子树，显然4没有右子树，t再一次变成了NULL，再下一次的循环过程中，t因为是NULL所以没有执行5-8行的while循环，意味着4没有右孩子了。那么对于4这个节点，左右孩子都已经检查了，结束。

对于栈顶的2这个元素，他们左孩子4检查完毕，说明环节进行到它这里了，可以输出，再去检查2节点的右孩子，如此反复。

先序遍历：

void D_Pre_Order(Node* root){ stack<Node*> s; Node* t=root; while ( (!s.empty()) || (t!=NULL) ){ while (t!=NULL){ cout<<t->data<<" "; if (t->rightchild!=NULL) s.push(t->rightchild); t=t->leftchild; } if(!s.empty()){ t=s.top(); s.pop(); } } }

后序遍历：

后序遍历递归定义：先左子树，后右子树，再根节点。后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

实现方法两种：一种是定义两个指针，一个用于记录当前访问节点，另一个记录上次访问的节点，这样来判断左右子树；                         另一种是给每个节点附加一个标记(left,right)。如果该节点的左子树已被访问过则置标记为left；若右子树被访问过，则置标记为right。显然，只有当节点的标记位是right时，才可访问该节点；否则，必须先进入它的右子树。

 

三、层次遍历

void Level(Node* t){ queue<Node*> q; if (t!=NULL) q.push(t); while (!q.empty()){ Node *p=q.front(); cout<<p->data<<" "; if (p->leftchild!=NULL) q.push(p->leftchild); if (p->rightchild!=NULL) q.push(p->rightchild); q.pop(); } }

层次遍历需要用到数据结构队列。

层次遍历的时候，需要把一层遍历完，再继续下一层的遍历，那么对于第i层的一个节点，他的左右孩子我们现在访问到了，但是不能输出，所以我们要先用队列储存起来。

四、DFS和BFS遍历

DFS遍历和递归形式的先序遍历是一样的。

BFS遍历和用队列的层次遍历是一样的。