⼆叉树先序遍历，中序遍历，后序遍历，层次遍历学习总结及完整CC++代码伪代码阐述
先序遍历
先序遍历：先访问根节点, 然后深⼊左⼦树，直到不能深⼊时再深⼊右⼦树
由定义可得递归式
void travPre_R(BinNodePosi* x,VISIT& visit){
if(!X) return; //到达叶⼦节点，开始回归
visit(x->data);//向左⼦树深⼊的过程中便开始进⾏对每个节点的数据进⾏访问
travPre_R(x->lChild,visit);//深⼊右⼦树
travPre_R(x->rChild,visit);//深⼊右⼦树
}
例:
其遍历顺序为: 0-1-3-7-8-4-9-10-2-5-11-12-6-13-14
就上述顺序表明遍历过程总是从根到左，再到右
由消除尾递归的⽅式可得其迭代式
void travPre_I1(BinNodePosi* x,VISIT& visit){
stack<BinNodePosi>s; //借助辅助栈记录根节点的左右孩⼦，以便于回溯
if(x) s.push(x);
while(!s.empty()){
p()->data);//访问当前节点
s.pop();//删除栈顶
if(x->lChild) s.push(x->rchild);//由于栈的结构，所以让rChild先进,lChild后进即可做到先访问lChild，后rChild
if(x->rChild) s.push(x->lChild);
}
//整个while操作就可以实现向左⼦树深⼊的过程，直到没有左⼦树
}
通过消除尾递归的⽅式所得到的迭代式不具有普遍性(⽆法推⼴到中序，后序，这⼆者⾮尾递归)，就此通过以下迭代式做阐述
void travPre_I2(BinNodePosi* x,VISIT& visit){
stack<BinNodePosi>s;
while(x){//
visit(x->data);
while(x->lChild){
s.push(x->rChild);//有右孩⼦存⼊栈中，以便回溯访问
x=x->lchild;//迭代向左⼦树进⾏深⼊
}
p();
s.pop();
}
/
/看似O(n^2)，但复杂度低于递归版
}
中序遍历
中序遍历：先查看最左端的叶⼦节点，然后根节点，最后右⼦树
得递归式:
void traveIn_R(BinNodePosi* x,VISIT& visit){
if(!x) return;
traveIn_R(x->lChild,visit);//先向左深⼊直到最左的叶⼦节点
visit(x->data);
traveIn_R(x->lChild,visit);
}
上图的中序遍历顺序:7-3-8-1-9-4-10-0-11-5-12-2-13-6-14
根据先序遍历的迭代可推⼴到中序遍历
void traveIn_I(BinNodePosi* x,VISIT& visit){
stack<BinNodePosi>s;
while(!s.empty()){
while(x){
s.push(x);
x=x->lChild;//向左⼦树不断深⼊
}
p();
visit(x->data);
x=x->rChild;
s.pop();
}
}
上述过程描述如下:先序中序后序遍历二叉树
先将所有最左边的左⼦树存⼊栈中，直到到达最左端的叶⼦节点(如上图的7号位置)，当进⾏完visit操作后，节点转向7号的右⼦树，没有右⼦树的情况下将弹出栈内元素，开始回溯，向上回溯⾄当前节点具有右⼦树时，将该右⼦树下的所有左⼦树⼊栈，重复上述操作，直到所有节点都遍历.
遍历过程中⽆右⼦树的节点需要做回溯处理
后序遍历
后序遍历: 先依次遍历完左⼦树，右⼦树后才访问根节点
得如下递归定义式:
void travePost_R(BinNodePosi* x,VISIT& visit){
if(!x) return;
travePost_R(x->lChild,visit);
travePost_R(x->rChild,visit);
visit(x->data);
}
上述图⽚中的遍历顺序:7-8-3-9-10-4-1-11-12-5-13-14-6-2-0
迭代式如下:
void travePast_I(BinNodePosi* x,VISIT& visit){
stack<BinNodePosi>s;
if(x)
s.push(x);
while(!s.empty()){
p()!=x->parent){
//s.top()!=x->parent主要⽤于判断两节点是否属于兄弟节点，例如上图的3,4；使得可以转向4号，将4号下的最左边的左⼦树及部分右⼦树进⾏⼊栈处理
while(x){
if(x->rChild) s.push(x->rChild);
if(x->lChild) s.push(x->lChild);
x=x->lChild;
//将最左边的左⼦树，及部分右⼦树依次存⼊栈中
}
}
p();
visit(x->data);
s.pop();
}
}
层次遍历
层次遍历：将⼆叉树看做⾦字塔形状，层次遍历做到的就是对每⼀层中左⼦树，右⼦树进⾏遍历处理，遍历顺序总是"先上后下，先左后右", 该遍历⽅式在⼴度优先遍历中也有所应⽤
由于层次遍历具有顺序性,⽽⾮后进先出原则，所以采⽤queue处理
上图中的遍历顺序:0-1-2-3-4-5-6-7-8-9-10-11-12-13-14
迭代式如下:
void traveLevel_R(BinNodePosi* x,VISIT& visit){
queue<BinNodePosi>q;
if(x)  q.push(x);
while(!q.empty()){
x=queue.front();
visit(x->data);
if(x->lChild) q.push(x->lChild);
if(x->rChild) q.push(x->rChild);
}
}
每当⼀个节点⼊队时，便让该节点的左右⼦树⼊队，由于队列的先进先出的性质，就能使每⼀层都能依次遍历
来⼀点⼩插曲
完全⼆叉树
在层次遍历中，每⼀次迭代中都必定有⼀个节点出队，如果在前n/2次迭代中都有左孩⼦⼊队, 且前n/2-1次迭代中都有右孩⼦⼊队，那么这棵树就是完全⼆叉树
拓扑结构特征: 叶⼦节点只能出现在最底部的两层，且最底层的叶⼦节点必须位于次叶⼦节点的左侧
⾼度h的完全⼆叉树, 规模介于2(h+1)-1之间
满⼆叉树
所有叶⼦节点都位于最底层, ⾼度为h的满⼆叉树由2^(h+1)-1个节点组成
完整详细设计(递归的设计⽅式很简单将不再阐述)
数据结构定义如下:
⼆叉树本⾝主要由结构体完成, 该结构体包含每个节点存储的节点数据value, 以及两个左右指针 lchild 和 rchild和⼀个⽗指针 parent , 这两个指针主要⽤来指向⼆叉树的左右⼦树, 通过左右指针, 就能很好的完成⼆叉树的遍历, 使⽤⽗指针也能很好完成节点的记录, 由于采⽤的⾮递归的⽅式遍历树结构, 所以需要使⽤到辅助数组, 通过数组, 和循环模拟递归遍历的过程。
功能详细设计:⼆叉树结构：每⼀个⼆叉树节点包含数据域以及3个指针(分别指向左⼦树，右⼦树，⽗节点)。创建⼆叉树: 采⽤前序遍历的⽅式创建⼀棵完整的⼆叉树, 便于后⾯的遍历⽅式的测试，我使⽤"#"字符代表空。
⾮递归的前序遍历: 前序遍历的⽅式是先查看当前节点内容然后再查看左⼦树, 最后查看右⼦树。所以在⾮递归遍历中, 就模拟这种遍历⽅式, ⾸先存⼊根节点, 使⽤循环, 每次将数组最后位置的节点取出, 进⾏访问, 将访问过的节点的右⼦树存⼊数组中, 然后存左⼦树, 循环终⽌条件是数组为空, 模拟这种情况, 就能每次做到先访问根, 然后访问左⼦树, 最后访问右⼦树
⾮递归中序遍历: 中序遍历是先访问左⼦树, 再访问根节点, 最后访问右⼦树, 同样的采⽤数组模拟这种遍历⽅式。⾸先将当前节点的所有依次左⼦树存⼊数组中(直到没有左⼦树)，然后取出数组中最后⼀个位置的节点进⾏访问，此时再转向右⼦树(⽆论右⼦树是否存在，这⾥需要利⽤右⼦树等于空的条件进⾏判断下⼀次循环是否要再将左⼦树存⼊数组中)，执⾏完上述操作后，再重复执⾏，直到所有节点都访问完。
⾮递归后序遍历：后序遍历是先访问左⼦树，再访问右⼦树，最后访问根节点，⾮递归实现：将当前节点的所有左⼦树依次存⼊数组中(同时将该节点的右⼦树存⼊数组中，便于待会模拟回溯)，左右⼦树存储的条件是：左右节点都访问过才能访问⽗节点，当栈顶元素与当前元素的⽗节点是同⼀个，则说明当前节点存在兄弟节点还没被访问1.整个过程尽量往左⼦树⽅向⾛，如果该节点没有左⼦树，就往右⼦树⽅向⾛⼀次，然后重复步骤1，直到节点左右⼦树都不存在，此时输出该节点存储的数据
函数关系调⽤图如下:
写代码容易出现的问题:
h~2
正确理解递归遍历的⽅式, 防⽌理解错误导致, 不能⽤栈结构模拟出遍历的过程, 在⾮递归后序遍历，没
⽤弄清楚循环判断和条件判断，导致在遍历过程中出现错误，最后采⽤得到⽅式就是判断栈顶元素与当前节点的⽗节点是否是同⼀个，通过这样的⽅式判断是否输出该节点的⽗节点内容。
树结构体:
struct BitNode{
BitNode(char c,BitNode *p):data(c),parent(p){}
Type data;
BitNode *parent=NULL,*lchild=NULL,*rchild=NULL;
};
⾮递归先序遍历:
void nrperOrder(BitNode *bt){//⾮递归先序遍历
int top=-1;
BitNode *stack[size],*p;
if(bt!=NULL)stack[++top]=bt;
else return;
while(top>-1){
p=stack[top--];
cout<<p->data;
//有右存右，有左存左，先存右再存左
if(p->rchild!=NULL)stack[++top]=p->rchild;
if(p->lchild!=NULL)stack[++top]=p->lchild;
}
}
⾮递归中序遍历:
void nrinOrder(BitNode *bt){//⾮递归中序遍历
int top=-1;
BitNode *stack[size],*p=bt;
while(p||top>-1){
if(p){
stack[++top]=p;
p=p->lchild;
}else{
p=stack[top--];
cout<<p->data;
p=p->rchild;
}
}
}
⾮递归后序遍历:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。