花了些时间总结了二叉树四种经典遍历方式。特别是层次遍历，值得思考。
#include<stdio.h> #include<malloc.h> typedef char ElemType; typedef struct BiNode { ElemType data; struct BiNode *lchild; struct BiNode *rchild; }BiNode,*BiTree; //先序拓展序列建立二叉树 void create(BiTree &T) { ElemType c; //printf("Enter the data \n"); scanf("%c",&c); if(c=='#') T=NULL; //很重要 创建的时候要注意，如果输入为#，则T=NULL，否则新建节点。这个很容易错误。 else{ T =(BiNode*) malloc (sizeof(BiNode)); T->data=c; create(T->lchild); create(T->rchild); } } void preorder(BiTree T) { if(T) { printf("%c\t",T->data); preorder(T->lchild); preorder(T->rchild); } } void inorder(BiTree T) { if(T) { inorder(T->lchild); printf("%c\t",T->data); inorder(T->rchild); } } void postorder(BiTree T) { if(T) { postorder(T->lchild); postorder(T->rchild); printf("%c\t",T->data); } } void levelorder(BiTree T) { BiTree Queue[20]; BiTree p; int front=0,rear=0; if(T) { p=T; Queue[rear]=p; rear=(rear+1)%20; while(front!=rear) { p=Queue[front] ; printf("%c\t",p->data); front=(front+1)%20; if(p->lchild) { Queue[rear]=p->lchild; rear=(rear+1)%20; } if(p->rchild) { Queue[rear]=p->rchild; rear=(rear+1)%20; } } } } int main() { BiTree T; create(T); preorder(T); printf("\n"); inorder(T); printf("\n"); postorder(T); printf("\n"); levelorder(T); printf("\n"); }
注意创建二叉树的时候一定要引用。
BiTree &T 改变指针T的指向（最开始是指向0）
我最开始没有写引用，导致错误。
输入时要特别注意，是按照先序方式来构造二叉树的，还有，用#代表没有空节点。输入了n个字符，就应该有n+1个#空字符。
层次遍历中用到队列，是用数组来实现 的。
/*按层遍历*/ void levelTraverse(BiTree T) { BiTree Queue[20]; BiTree p; int front=0,rear=0; /*表示队头指针和队尾指针*/ if(T) { p=T; /*根指针入队*/ Queue[rear]=p; rear=(rear+1)%20; /*队尾指针加一对20取余，可实现循环队列，合理利用空间*/ while(front!=rear) /*队不空*/ { p=Queue[front]; /*出队，将值赋给p*/ printf("%c",p->data); front=(front+1)%20; if(p->lchild) /*如果p有左子树，将左子树入队*/ { Queue[rear]=p->lchild; rear=(rear+1)%20; } if(p->rchild) /*如果p有右子树，将右子树入队*/ { Queue[rear]=p->rchild; rear=(rear+1)%20; } } } }
用队列实现层次遍历真正的思想如下：
编写按层次（同一层从左至右）遍历二叉树的算 法。 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }
我们来解剖下中序遍历的代码。代码看起来简单，真正的威力来源于递归，实际上是双重递归，系统在运行时栈上完成这些工作。
void inorder(BiTree T) { if(T) { inorder(T->lchild); printf("%c\t",T->data); inorder(T->rchild); } }
按照robert sedgewick的书中的概念想法，对于中序，我们压入右子树，然后是节点，最后是左子树，按照这种想法，一开始就无从下手了：
void inOrderNonRecur(BiTree T)
{
stack<BiTree> s;
if(T->right!=0) s.push(T->right);
else s.push(T);
因为不知道右子树是否为空，我们要做判断，接下来的代码就越来越不好写了。必须放弃这种思路。我们还是根先入栈。
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
void inorder_nonrecursive(BiTree T) { stack<BiTree> s; s.push(T); //根指针入栈 BiTree p; while(!s.empty()) { while(p=s.top())//向左走到尽头 s.push(p->lchild); s.pop();//空指针NULL退栈 if(!s.empty()) { p=s.top(); s.pop(); printf("%c\t",p->data); s.push(p->rchild); } } }
过程如下：
15
15 4 1 #向左走到尽头 #表示空
15 4 1 //s.pop
15 4 输出1
15 4 #
15 //输出4
15 #
输出15，
20
20 16 #
20 输出16
20 #
输出20 s.push(25)
25
25 #
输出25 .push(#)
#
s.pop() if(！s.empty())不成立，
while 退出
看过上面的，应该知道，根也是左孩子线上的。斜线看更清楚。
前序遍历：
void preorder_nonrecursive(BiTree T) { stack<BiTree> s; s.push(T); //根指针进栈 BiTree p; while(!s.empty()) { while(p=s.top()) { printf("%c\t",p->data); s.push(p->lchild);//向左走到尽头，每向前一步都访问当前节点 } s.pop(); if(!s.empty()) { p=s.top(); s.pop(); s.push(p->rchild); /* 向右走一步 */ } } }
15 输出15
15 4 1 输出 4 ，1
15 4 1 #
15 4 1
15 4 s.pop() 1
15 4 #
15 4
15 s.top 4
15 #
15 s.pop
pop 15
s.push(20);
个人推荐的前序和中序遍历方法：
void preOrder3(BiTree root) { stack<Node*> s ; Node* p=root; while(p || !s.empty()) { while(p) { cout<<p->data<<" "; s.push(p); p=p->left; } p=s.top();s.pop(); p=p->right; } } void inOrder3(BiTree root) { stack<Node*> s; Node* p=root; while(p || !s.empty()) { while(p) { s.push(p); p=p->left; } p=s.top();s.pop(); cout<<p->data; p=p->right; } }
上面的代码大致相同，只是改变cout<<p->data即可。
个人推荐的后续遍历方法：
void postOrder5(BiTree root) { stack<Node*> s; Node *p=root; Node* lastVisited=NULL; while(p || !s.empty()) { while(p) { s.push(p); p=p->left; } p=s.top();//现在还不能pop() if(!p->right || p->right==lastVisited) { cout<<p->data<<ends; s.pop(); lastVisited=p; p=NULL;//很重要，否则while(p)循环会继续下去 } else p=p->right; } }
另一种方法：
后续遍历跟前面2个不同；
typedef struct { BTNode* ptr; enum {0,1,2} mark; } PMType; /* 有mark域的结点指针类型 */ void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */ { PMType a; initstack(S); /* S的元素为PMType类型 */ push (S,{T,0}); /* 根结点入栈 */ while(!stackempty(S)) { pop(S,a); switch(a.mark) { case 0: push(S,{a.ptr,1}); /* 修改mark域 */ if(a.ptr->;lchild) push(S,{a.ptr->;lchild,0}); /* 访问左子树 */ break; case 1: push(S,{a.ptr,2}); /* 修改mark域 */ if(a.ptr->;rchild) push(S,{a.ptr->;rchild,0}); /* 访问右子树 */ break; case 2: visit(a.ptr); /* 访问结点 */ } } }
另一个版本的：
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
前序、中序、后序的非递归遍历中，要数后序最为麻烦，如果只在栈中保留指向结点的指针，那是不够的，必须有一些额外的信息存放在栈中。 方法有很多，这里只举一种，先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。 lastOrderTraverse(BiTree bt){ //首先，从根节点开始，往左下方走，一直走到头，将路径上的每一个结点入栈。 p = bt; while(bt){ push(bt, 0); //push到栈中两个信息，一是结点指针，一是其右结点是否被访问过 bt = bt.lchild; } //然后进入循环体 while(!Stack.empty()){ //只要栈非空 sn = Stack.getTop(); // sn是栈顶结点 //注意，任意一个结点N，只要他有左孩子，则在N入栈之后，N的左孩子必然也跟着入栈了(这个体现在算法的后半部分)，所以当我们拿到栈顶元素的时候，可以确信这个元素要么没有左孩子，要么其左孩子已经被访问过，所以此时我们就不关心它的左孩子了，我们只关心其右孩子。 //若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时可以visit这个结点了。 if(!sn.p.rchild || sn.rvisited){ p = pop(); visit(p); } else //若它的右孩子存在且rvisited为0，说明以前还没有动过它的右孩子，于是就去处理一下其右孩子。 { //此时我们要从其右孩子结点开始一直往左下方走，直至走到尽头，将这条路径上的所有结点都入栈。 //当然，入栈之前要先将该结点的rvisited设成1，因为其右孩子的入栈意味着它的右孩子必将先于它被访问(这很好理解，因为我们总是从栈顶取出元素来进行visit)。由此可知，下一次该元素再处于栈顶时，其右孩子必然已被visit过了，所以此处可以将rvisited设置为1。 sn.rvisited = 1; //往左下方走到尽头，将路径上所有元素入栈 p = sn.p.rchild; while(p != 0){ push(p, 0); p = p.lchild; } }//这一轮循环已结束，刚刚入栈的那些结点我们不必管它了，下一轮循环会将这些结点照顾的很好。 } }
第一个while:
ABD.注意我们没有把NULL进栈
进入第二个while，由于D没有右孩子，也没用访问过，所以出栈并访问它（输出D)，变成了
AB 取出B，由于b的右孩子没有被访问过，把B设为1.AB(1),然后把E入栈。E没有左孩子，变成了:
AB(1)E,E没有右孩子，访问E，栈变成了
AB(1)由于B已经设置为1，代表它的有孩子已经被访问了，输出B，栈变成了：
A(1)。(可以看到，设置1是必要的)
由于A有有孩子并且没有访问过，把右孩子C入栈，还有F。栈变成了：
A(1)CF
F没有右孩子，输出F，C也没有右孩子，输出C，
A，A虽然有右孩子，但是已经访问过，输出A。
此时栈空，结束。
总输出：
D E B F C A
按照上面的方法写的c++代码，用了STL的stack：
typedef struct SNode{ Node* pNode; int rvisited; SNode(Node* p,int x){ pNode=p; rvisited=x;} }SNode; ////Node 是二叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。 void postOrderNonCur2(BiTree T) { BiTree p=T; stack<SNode*> s; SNode * sNode; while(p) { sNode=new SNode(p,0);//每次都要新建一个节点 s.push(sNode); p=p->left; } while(!s.empty()) { sNode=s.top(); if(!sNode->pNode->right || sNode->rvisited) { sNode=s.top(); s.pop(); visit(sNode->pNode->data); } else { sNode->rvisited=1; //往左下方走到尽头，将路径上的所有元素入栈 p=sNode->pNode->right; while(p!=0) { sNode=new SNode(p,0); s.push(sNode); p=p->left; } } } }
必须每次新建SNode，
sNode=new SNode(p,0);//每次都要新建一个节点
我最开始都是SNode->pNode=p;
sNode->rvisited=0;
导致stack栈里面都是一样的值，同一个元素的地址。
更多参考：
二叉树遍历非递归算法 http://www.360doc.com/content/07/0601/21/9889_533413.shtml 详细列出了多种解法
二叉树 非递归遍历 栈实现（前、中后序）http://www.360doc.com/content/12/0410/11/4186481_202433750.shtml
先序遍历：
void traverse(link h,void visit(link)) { if(h==0) return; visit(h); traverse(h->lchild,visit); traverse(h->rchild,visit); }
前序遍历函数调用如下：
非递归遍历算法
我们从一个抽象的栈开始考察，这个栈能够保存项或树，以将被遍历的树做初始化，然后，我们进入一个循环，在这个循环中我们弹出并处理在栈顶端的项，如此继续，直到栈空了为止。如果已经弹出的实体是个个项，我们就访问它，如果弹出的实体是一棵树，我们就以希望的顺序进行一系列入栈操作：
1对于前序，我们压入右子树，然后左子树，最后是节点
2对于中序，我们压入右子树，然后节点，最后左子树
3对于后序，我们压入节点，然后是右子树，最后左子树。
我们前面的描述是概念性的，在实际中实现要简单一些，比如，对于前序，我们不需要把节点推到栈上（我们访问弹出来的每一棵树的根），这样的话，我们就能使用一个仅包含一种类型的项（树链接）的简单栈，类似于下面的实现，支持递归程序的系统栈包含返回地址与参数值，而不是项或节点，但是我们进行计算（访问节点）的实际顺序对于递归方法和基于栈的办法来说是一样的。
void preTraverse(BiTree T) { stack<BiTree> s; s.push(T); while(!s.empty()) { T=s.top(); s.pop(); printf("%c\t",T->data); if(T->rchild!=0) s.push(T->rchild); if(T->lchild!=0) s.push(T->lchild); } }
层次遍历：
我们可以用一个队列来代替上面的stack实现层次便利了，
void levelTraverse(BiTree T) { queue<BiTree> q; q.push(T); while(!q.empty()) { T=q.front(); q.pop(); printf("%c\t",T->data); if(T->lchild!=0) q.push(T->lchild); if(T->rchild!=0) q.push(T->rchild); } }
或者：
void inOrderTraverse(BiTree T) { queue<BiTree> q; q.push(T); while(!q.empty()) { BiTree h=q.front();q.pop(); visit(h->data); if(h->left!=0) q.push(h->left); if(h->right!=0) q.push(h->right); } }
我们建了一个临时变量BiTree h 来代替T。
其实层次遍历就是图的BFS。
中序和后序要复杂些，参看：
参考：algorithms in C++ parts 1-4
求深度：
int depth(BiTree t) { if(t==NULL) return 0; int left=depth(t->left); int right=depth(t->right); return 1+(left>right?left:right); }
更多方法：
/法1：后序遍历，结点最大栈长即为树的高度 //法2：层次遍历，层次即为高度 //法3：递归求树高 //输入：-+a##*b##-c##d##/e##f## //输出：5 #include<iostream> #include<stack> #include<queue> using namespace std; typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void CreateTree(BiTree &T) { char ch; cin>>ch; if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) cout<<"生成结点错误！"<<endl; T->data=ch; CreateTree(T->lchild); CreateTree(T->rchild); } } //法1：后序遍历，结点最大栈长即为树的高度 int BT_high(BiTree T) { BiTree p=T,r=NULL; int max=0; //树高 stack<BiTree> s; while(p||!s.empty()) { if(p!=NULL) { s.push(p); p=p->lchild; } else { p=s.top(); if(p->rchild!=NULL && p->rchild!=r) p=p->rchild; else { if(s.size()>max) max=s.size();//最大层次即为高度 r=p; s.pop(); p=NULL; } } } return max; } //法2：层次遍历，层次即为高度 int BT_level_depth(BiTree T) { if(!T) return 0; BiTree p=T,Q[100]; int front=-1,rear=-1,last=0,level=0; Q[++rear]=p; while(front<rear) { p=Q[++front]; if(p->lchild) Q[++rear]=p->lchild; if(p->rchild) Q[++rear]=p->rchild; if(front==last) { last=rear; level++; //层次+1 } } return level; } //法3：递归求树高1 int max1=0;//树高 int BT_depth1(BiTree T,int depth) { if(T) { if(T->lchild) BT_depth1(T->lchild,depth+1); if(T->rchild) BT_depth1(T->rchild,depth+1); } if(depth>max1) max1=depth; return depth; } //法3：递归求树高2 int Height (BiTree T) { if(T==NULL) return 0; else { int m = Height ( T->lchild ); int n = Height(T->rchild); return (m > n) ? (m+1) : (n+1); } } int main() { BiTree T=NULL; CreateTree(T); cout<<"后序遍历求树高："<<endl; cout<<BT_high(T)<<endl; cout<<"层次遍历求树高："<<endl; cout<<BT_level_depth(T)<<endl; cout<<"递归求树高1："<<endl; BT_depth1(T,1); cout<<max1<<endl; cout<<"递归求树高2："<<endl; cout<<Height(T)<<endl; return 0; }
打印某一层所有节点：(编程之美：3.10）
写一个函数，打印二叉树中某层次节点（从左到右）。其中根节点为第0层。函数原型
int printNodeAtLevel(Node* root,int level)成功返回1，失败返回0.
答案参考以前的：http://www.cnblogs.com/youxin/p/3288281.html
二叉树的宽度：所有深度中含有的最多的子叶数。
#include "stdafx.h" #include<iostream> #include<queue> using namespace std; typedef struct BTreeNode { int data; struct BTreeNode *lchild,*rchild; }BTree; int _tmain(int argc, _TCHAR* argv[]) { return 0; } int width(BTree *bt) { BTree *p=bt; if(bt)return 0; BTree *q[100]; int front=0,rear=0;//队头指针，队尾指针 int last=0;//同一层最右结点在队列中位置 int temp=0,maxw=0;//当前层宽度与最大宽度 q[rear]=bt; while(front<=last) { p=q[front++];temp++;//同层元素加1; if(p->lchild)q[rear++]=p->lchild; if(p->rchild)q[rear++]=p->rchild; if(front>last)//一层结束 { last=rear; if(temp>maxw)maxw=temp;//更新最大宽度 temp=0; } } return maxw; }
参考：http://blog.csdn.net/conanswp/article/details/19831129
二叉树前序中序后序的DFS非递归实现
https://www.cnblogs.com/anthony-dong/p/12250802.html