树：二叉树的集中遍历方法（先序，中序，后序遍历，线索二叉树）

时间：2022-12-17 19:56:31

一：二叉树的几种遍历方法

树：二叉树的集中遍历方法（先序，中序，后序遍历，线索二叉树）

1:先序遍历

根→左→右
先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。
比如上图，先序遍历的输出如下 : - + a * b - c d / e f

根据上面的思想，很容易用递归的形式写出先序遍历的代码：

//先序遍历  
Status PreOrderTraverse(BiTree T , Status(*visit)(TElemType)){
if(T){
if(visit( T->data )){//打印T->data
if(PreOrderTraverse( T->lchild , visit )){
if(PreOrderTraverse( T->rchild , visit )){
return OK;
 }
            }
        }
    }else return OK;
}

2,中序遍历

左→根→右
先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。
比如上图，中序遍历的输出如下 : a + b * c - d - e / f

3,后序遍历

左→右→根
先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。
比如上图，后序遍历的输出如下 : a b c d - * + e f / -

例题：

知道后序DABEC，中序DEBAC，求二叉树图
由后序最后一个字母知:整个树的开始结点为C;
由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树;
所以经过第一次推理,C为根结点,DEBA为其左子树;
然后去掉C,考虑下面的左子树;
后序DABE 中序DEBA
由后序最后一个字母知:整个左子树的开始结点为E;
由中序E的位置知:E前面的为结点E的左子树;E后面的为结点E的右子树;
所以经过第一次推理,E为开始结点,D为E的左结点.BA为E的右结点.
然后去掉DE,考虑下面E的右子树;
后序AB 中序BA
易知:B为根结点,A为其右结点.
所以整个树为:C(E(D,B(,A)));
先序:CEDBA

二：使用代码实现遍历

树：二叉树的集中遍历方法（先序，中序，后序遍历，线索二叉树）

1，先创建二叉树

#include <iostream>
using namespace std;
char array[] = "ABD##E##C#F##";  
int i(0);

typedef struct BTree{
char data;
struct BTree *left,*right;

};
//创建子节点（递归）
void CerateNode(BTree *&p){//注意*&p在c中表示为**p，是指针地址
    i++;
if(strlen(array)>i&&array[i]!='#'){
        BTree* node = (BTree*)malloc(sizeof(BTree));
        node->left = 0;
        node->right = 0;
        node->data = array[i];
        p = node;//指针地址指向节点
        CerateNode(node->left);//左
        CerateNode(node->right);//右
    }else{
return;
    }


}
//创建根节点
BTree* CreateRoot(){
    BTree* node = (BTree*)malloc(sizeof(BTree));
    node->left = 0;
    node->right = 0;
    node->data = array[0];
return node;
}

//主函数
void main(void){
    BTree* head = CreateRoot();//创建根节点
    CerateNode( head->left);//添加左子树
    CerateNode(head->right);//添加右子树
cout<<endl<<"先序：";
    PreOrderTravse(head,0);
cout<<endl<<"中序：";
    PreOrderTravse(head,1);
cout<<endl<<"后序：";
    PreOrderTravse(head,2);
cout<<endl;
    system("pause");
}

2，递归方便遍历

//遍历i=0时为先序，i=1是为中序，i=2时为后序
void PreOrderTravse(BTree* &t,int i){
if(t){
if(i==0)cout<<t->data;//先序
if(!t->left==0)PreOrderTravse(t->left,i);
if(i==1)cout<<t->data;//中序
if(!t->right==0)PreOrderTravse(t->right,i);
if(i==2)cout<<t->data;//后序
    }
}

3，非递归方法遍历

后序遍历二叉树（非递归）思想：

1.对于一棵树t,如果t非空，首先应该进入t的左子树访问，此时由于t的右子树及根结点尚未访问，
2. 因此必须将t保存起来，放入栈中，以便访问完左子树后，从栈中取出t，进行其右子树及根结点的访问。
3. 这里值得注意的是，当一个元素位于栈顶即将处理时，其左子树的访问一定已经完成，
4. 如果其右子树尚未遍历，接下来应该进入其右子树的访问，而此时该栈顶元素是不能出栈的，
5. 因为其根结点还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输其根结点的值。
6. 因此，在二叉树后序遍历的过程中，必须使用标记数组，其每个元素取值为0或1，
7. 用于标识栈中每个元素的状态。当一个元素刚进栈时，其对应的tag值置0；当它第一次位于栈顶即将
8. 被处理时，其tag值为0，意味着应该访问其右子树，于是将其右子树作为当前处理的对象，
9. 此时该栈顶元素仍应该保留在栈中，并将其对应的tag值改为1；当其右子树访问完成后，
10. 该元素又一次位于栈顶，而此时其tag值为1，意味着应该访问其根结点，并将其出栈。
11.在整个二叉树后序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）
12.和保存在栈中待处理的部分。只有这两部分的工作均完成后，程序方能结束。 

BTree *stack[30] = {0}; //用一个静态数组模拟栈
int ntag[30] = {0};//标记数组标记每个元素的左右子树是否都已经被访问过了 
int top = -1;//初始状态下Top=-1表示栈空 

//非递归的先序，中序遍历
void PreOrderTravse2(BTree* t,int i){
int top = -1;
    BTree *p = t;
while(p!=0||top!=-1){//当前指针不空或栈不空 
while (p){//当前指针不空 
if(i==0)cout<<p->data;
stack[++top] = p;//将当前指针入栈 
            p = p->left;
        }
if(top!=-1){//栈不空 
            p = stack[top--];//获取栈顶指针且栈顶指针出栈
if(i==1)cout<<p->data;
            p = p->right;
        }
    }
}
//后序遍历
void hou(BTree* t){
    top = -1;
    BTree *p = t;
while(p!=0||top!=-1){//当前指针不空或栈不空 
while (p){//当前指针不空 
stack[++top] = p;//将当前指针入栈 
            ntag[top] = 0;//表示第一次位于栈顶 
            p = p->left;
        }
//栈不空且栈顶指针指向的结点被标记为1即表示给结点的左右子树都已经被访问过了，第二次位于栈顶 
while(top!=-1&&ntag[top]==1){
            BTree *c = stack[top--];//获取栈顶指针且栈顶指针出栈
cout<<c->data;
        }
if(top!=-1){//栈不空 此时标记为0,意味着应该访问其右子树 
            p = stack[top];//取到栈顶元素，注意此时不能出栈
            ntag[top] = 1;
            p = p->right;
        }
    }
}
标签：

相关文章