1、二叉树的遍历

为什么要有遍历操作：将线性结构-------->非线性结构；

将递归程序-------->非递归程序；

2、二叉树的三种递归遍历：

先序遍历：先访问根(父)结点，在访问左分支，最后访问右分支；

中序遍历：先访问左分支，在根结点，最后右分支；

后序遍历：先访问左分支，在访问右分支，最后访问根节点；

所有程序皆正确测试过，后面将给完整程序和测试程序，测试结果。

以下就是递归遍历，先序，中序，后序：

下面的都是在类外定义的函数，所以为模板函数：

//先序遍历template<typenameType>voidBinTree<Type>::prevOrder(BinTreeNode<Type>*t)const{if(t==NULL){return;}else{cout<<t->data<<"";prevOrder(t->leftChild);prevOrder(t->rightChild);}}//中序遍历template<typenameType>voidBinTree<Type>::inOrder(BinTreeNode<Type>*t)const{if(t==NULL){return;}else{inOrder(t->leftChild);cout<<t->data<<"";inOrder(t->rightChild);}}//后序遍历template<typenameType>voidBinTree<Type>::endOrder(BinTreeNode<Type>*t)const{if(t==NULL){return;}else{endOrder(t->leftChild);endOrder(t->rightChild);cout<<t->data<<"";}}

3、二叉树的4种非递归遍历

(1)、深度优先用栈

先序的非递归遍历：栈先入后出，根结点入栈，栈不空，出栈访问，此时将右孩子入栈，在将左孩子入栈，栈不空，出栈访问，就是循环了；

代码如下：

template<typenameType>voidBinTree<Type>::prevOrder_1(BinTreeNode<Type>*t)const{stack<BinTreeNode<Type>*>st;//栈里面放的是指向节点的指针BinTreeNode<Type>*tmp;if(t!=NULL){//根不为空st.push(t);//根入栈while(!st.empty()){//栈非空tmp=st.top();//读栈顶元素st.pop();//出栈cout<<tmp->data<<"";//访问if(tmp->rightChild){//右孩子存在st.push(tmp->rightChild);//入栈}if(tmp->leftChild){//左孩子存在st.push(tmp->leftChild);//入栈}}}}

中序的非递归遍历：就是先把根及左分支一直压栈，栈不空，出栈访问，再看右孩子，有的话，压栈，结束条件想清楚就行。

代码如下：

template<typenameType>voidBinTree<Type>::inOrder_1(BinTreeNode<Type>*t)const{stack<BinTreeNode<Type>*>st;//栈里面放的是指向节点的指针BinTreeNode<Type>*p=t;//用的是dowhile()循环do{while(p!=NULL){//将根和左子树一直入栈st.push(p);p=p->leftChild;}if(!st.empty()){//栈不空，p=st.top();//读栈顶元素st.pop();//出栈cout<<p->data<<"";//访问p=p->rightChild;//此时往刚才栈顶元素的右孩子走；}//中序遍历时，当root出栈时，此时栈空，没有p!=NULL的话，将出错。}while(p!=NULL||!st.empty());//为根的时候右边还要入栈。}

后序的非递归遍历：思想就是要有一个标志，当为右边回来的时候才能访问根节点！！！

代码如下：

typedefenum{L,R}Tag;//枚举定义新的类型template<typenameType>//定义一个类，为的是做标志classstkNode{public:stkNode(BinTreeNode<Type>*p=NULL):ptr(p),tag(L){}public://数据成员为公有，便于访问BinTreeNode<Type>*ptr;Tagtag;//LR};template<typenameType>voidBinTree<Type>::endOrder_1(BinTreeNode<Type>*t)const{stkNode<Type>n;stack<stkNode<Type>>st;//此时栈中存放的是对象！BinTreeNode<Type>*p=t;do{while(p!=NULL){//不为空，一路向左入栈n.ptr=p;//将指针给过去n.tar=L;//记为左边入栈st.push(n);p=p->leftChild;}boolisRun=true;//是否继续的标志while(isRun&&!st.empty()){n=st.top();//读栈顶st.pop();//出栈switch(n.tag){//根据L和R选择caseL:p=n.ptr;n.tag=R;//更改为Rst.push(n);//压入栈p=p->rightChild;//看有没有右孩子，有的话，结束循环，要入栈的；isRun=false;//特别重要，保证了右孩子的入栈！break;caseR:cout<<n.ptr->data<<"";break;}}}while(!st.empty());//不用p1=NULL,因为当栈空时，最后一个节点刚好被访问完成。}

画图跟踪后序如下：

(2)、广度优先用队列

层次遍历：根结点入队列，队列非空，出队访问，在将左右孩子入队，非空，访问，构成循环；

代码如下：

template<typenameType>voidBinTree<Type>::levelOrder(BinTreeNode<Type>*t)const{queue<BinTreeNode<Type>*>qu;//队列里面放的是指向节点的指针BinTreeNode<Type>*p;if(t!=NULL){//根非空qu.push(t);//根入队while(!qu.empty()){//队列非空p=qu.front();//读队首qu.pop();//出队cout<<p->data<<"";//访问if(p->leftChild){//左孩子存在qu.push(p->leftChild);//入队}if(p->rightChild){//右孩子存在qu.push(p->rightChild);//入队}}}}