二叉树遍历
|
|
数据结构

1505 字
|
31 分钟

遍历方法

前、种、后序遍历

阿Q理解：树有 根结点D+ 左子树L + 右子树R 组成（该结点左右子树同理 – 递归），这三部分就有 A(3,2) = 6 种遍历方式（DLR，DRL，LDR，LRD，RDL，RLD），其中DLR – RLD，LDR – RDL，LRD – DRL对称。所以捏，咱们严格按照 先左后右 讨论三种就行，即 DLR（先序），LDR（中序），LRD（后序）。

咱就不整下有的没的，其实这三种遍历走的路径是一样的（访问时机不一样），如下图。

层次遍历

如何实现层次遍历呢？ 这就用到了队列的先进先出的思想。

来看第 n 层是如何 确定第 n+1层顺序的：

第n层从左到右扫描，先看结点左孩子，有则进队，再看右孩子，有则进队。 这样第 n+1层先后顺序就有了。

算法实现（二叉链表）

前、中、后序遍历

递归

typedef char ElemType; 

// 设 Visit 为输出当前结点的值
void Visit(BtNode *t)
{
    printf("%c",t->data);
}

// 前序遍历
void PreOrder(Btree T)
{
    // 若为空，则说明上一层递归的结点为叶子结点
    if(T != NULL){
        // 对根结点进行访问操作（访问不仅仅是输出当前结点的值，还有求最大值、求和...）
        Visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 中序遍历
void InOrder(Btree T)
{
    if(T != NULL){
        InOrder(T->lchild);
        Visit(T);
        InOrder(T->rchild);
    }
}

// 后序遍历
void PostOrder(Btree T)
{
    if(T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        Visit(T);
    }
}

测试代码

int main(){
    // 构造树
    BtNode Root;
    Root.data = 'A';
    Btree T = &Root;

    BtNode A1;
    A1.data = 'B';
    Root.lchild = &A1;
    
    BtNode A2;
    A2.data = 'C';
    Root.rchild = &A2;
    A2.lchild = NULL;
    A2.rchild = NULL;

    BtNode A3;
    A3.data = 'D';
    A1.lchild = &A3;
    A3.lchild = NULL;
    A3.rchild = NULL;

    BtNode A4;
    A4.data = 'E';
    A1.rchild = &A4;
    A4.lchild = NULL;
    A4.rchild = NULL;

    printf("前序遍历:");
    PreOrder(T);

    printf("\n中序遍历:");
    InOrder(T);

    printf("\n后序遍历:");
    PostOrder(T);    

    return 0;
}
/*
此处建立的为图一的树
输出结果：
前序遍历:ABDEC
中序遍历:DBEAC
后序遍历:DEBCA
*/

若用顺序存储也可以，先把树改成完全二叉树，然后数组存放（下标从1开始），结点 i 的左孩子为 2i，右孩子为 2i + 1 代替 T.lchild 和 T.rchild，修改下递归结束条件即可。

顺序存储结构下的前序递归算法演示（后面就不弄了）

void PreOrder_sequential(char tree[],int i){
    if(i < TreeSize){
        Visit(tree[i]);
        PreOrder_sequential(tree,2*i);
        PreOrder_sequential(tree,2*i + 1);
    }
}

阿Q建议还是用二叉链表存树。

非递归

阿Q建议先看一下递归转非递归。

Btree.h 
typedef char BtElemtype;

typedef struct BtNode
{
    /* data */
    BtElemtype data;
    struct BtNode *lchild, *rchild; 
}BtNode,*Btree;
Stack.h 
#include"BTree.h"
typedef  Btree SElemType;  // 此处建议存栈内存指针（指针32位只占4个字节，而结构体：char(1字节) + 两个指针(8) = 9 字节）
// 顺序栈（逻辑指针）
#define MaxSize 50

typedef struct
{
    /* data */
    SElemType data[MaxSize];
    int top;
}SqStack;
中序非递归遍历
// 非递归实现中序遍历
void InOrder(Btree T)
{
    // 左 根 右
    SqStack S;
    InitStack(S);

    Btree Ptr = T;

    while(Ptr || !StackEmpty(S)){     // 只有在：1、当前结点为空 2、栈为空  两条件满足时才结束循环
        if(Ptr){        // 当前结点不为空，看看左子树是否为空
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }
        else{     // 当前结点为空
            Pop(S, Ptr);
            Visit(Ptr);   // 第二次经过时访问
            Ptr = Ptr->rchild;
        }
    }
}

阿Q经过思考，上面这一段代码其实不是那么好理解的，下面这段更好理解的

void InOrder(Btree T)
{
    // 左 根 右
    SqStack S;
    InitStack(S);

    Btree Ptr = T;

    while(Ptr || !StackEmpty(S)){     
        while(Ptr){        // 左子树全部入栈
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }
        // 取栈顶元素
        Pop(S,Ptr);
        // 无论是否有右子树，都要访问根结点
        Visit(Ptr);
        if(Ptr->rchild == NULL)
        {
            // 跳过循环
            Ptr = NULL;
        }
        else  // 有右子树遍历右子树，但是要访问根哦（左 根 右）
        {
            Ptr = Ptr->rchild;
        }
    }
}
前序非递归
// 非递归实现前序遍历
void PreOrder(Btree T)
{
    // 根 左 右
    SqStack S;
    InitStack(S);

    Btree Ptr = T;

    while(Ptr || !StackEmpty(S))
    {
        if(Ptr){
            Visit(Ptr);
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }
        else{
            Pop(S,Ptr);
            Ptr = Ptr->rchild;
        }
    }
}

同样修改为下面这段好理解

void PreOrder(Btree T)
{
    // 根 左 右
    SqStack S;
    InitStack(S);

    Btree Ptr = T;

    while(Ptr || !StackEmpty(S))
    {
        // 左子树全进栈，但是由于其同时为根结点，先访问
        while(Ptr){
            Push(S,Ptr);
            Visit(Ptr);
            Ptr = Ptr->lchild;
        }
        // 出栈顶元素
        Pop(S, Ptr);
        // 若无右子树，则出栈，但需要注意将Ptr设置为NULL,防止左树重复进入
        
        if(Ptr->rchild == NULL) Ptr = NULL;
        // 有右子树访问右子树
        else Ptr = Ptr->rchild;
    }
}
后序非递归 （有难度，建议常看）
双栈法
void PostOrder2(Btree T)
{
   // 左、右、根 与  根、右、左对称
   // 那么可以先根据 根、右、左遍历，然后将遍历结果依次进另一个栈，再出栈即为后序遍历
   SqStack S1;
   InitStack(S1);
   SqStack S2;
   InitStack(S2);

   Btree Ptr = T;
   while(Ptr || !StackEmpty(S1))
   {
        while(Ptr) // 此处是先把右边全部进栈，同时其为根结点，需访问
        {
            Push(S1,Ptr);
            
            // 将访问结果 依次入栈
            Push(S2,Ptr);

            Ptr = Ptr->rchild;
        }

        // 出栈顶元素
        Pop(S1,Ptr);
        // 若 无左子树，需要将Ptr设置为空，防止右子树重复进入
        if(Ptr->lchild == NULL) Ptr = NULL;
        else Ptr = Ptr->lchild; // 有左结点即遍历左结点
   }

   // S2出栈即为后序遍历结果
   while(!StackEmpty(S2))
   {
        Pop(S2,Ptr);
        Visit(Ptr);
   }
}
单栈法
// 非递归实现后序遍历
void PostOrder(Btree T)
{
    // 左 右 根
    SqStack S;
    InitStack(S);

   Btree Ptr = T;
   // 记录上一个访问的结点
   Btree Pre;
   while(Ptr || !StackEmpty(S))
   {
        // 左 全入栈
        while(Ptr)
        {
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }
        // 先出栈顶元素原因：此处由于根是最后被访问的，因此先对其右子树进行判断
        Pop(S,Ptr);
        // 什么条件下能访问该栈顶呢？
        // 此处有两个情况：
        // 1、右子树不存在
        // 2、当前栈顶元素的右子树已经被访问
        if(Ptr->rchild == NULL || Ptr->rchild == Pre)
        {
            Visit(Ptr);
            Pre = Ptr;
            // 跳过第一个while循环 (重要)
            Ptr = NULL;
        }
        else   // 还有右子树没遍历
        {
            Push(S,Ptr);
            Ptr = Ptr->rchild;
        }
   }
}

25-2-27 ：修改下判断顺序或许会更好

void PostOrder(Btree T)
{
    SqStack S;
    InitStack(S);
 
   Btree Ptr = T;
   Btree Pre = NULL;
   while(Ptr || !StackEmpty(S))
   {
        while(Ptr)
        {
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }
        // 查栈顶元素 - 修改部分
        GetTop(S,Ptr);
        // 存在右孩子且先前访问的不为右孩子时  访问右孩子 - 修改部分
        if(Ptr->rchild && Ptr->rchild != Pre)   Ptr = Ptr->rchild;
        else   
        {
            Pop(S,Ptr);
            Visit(Ptr);
            Pre = Ptr;
            Ptr = NULL;
        }
   }
}

二叉树后序非递归算法有妙用（根到结点的路径；两个结点的最近公共祖先），如图：

前、中、后遍历非递归的统一写法

阿Q先自己写了一遍，有不少逻辑问题，后经过AI辅助，写出以下较为清晰的统一写法。

阿Q出现的逻辑错误：

1、先设置了Ptr = NULL，然后还进行了if判断导致出现 NULL->rchild的判断（有点逆天的）；

2、中序遍历无论是否有右子树都先访问根结点，而阿Q还对其进行了if判断。

void traverse2(Btree T, TraversalType type = PREORDER) {
    SqStack S;
    InitStack(S);
    Btree Ptr = T;
    Btree Pre = NULL; // 后序遍历记录前一个访问的节点

    while (Ptr || !StackEmpty(S)) {
        // 遍历左子树并入栈
        while (Ptr) {
            if (type == PREORDER) Visit(Ptr); // 前序在入栈时访问
            Push(S, Ptr);
            Ptr = Ptr->lchild;
        }

        Pop(S, Ptr);

        // 中序遍历：直接访问当前节点
        if (type == INORDER) {
            Visit(Ptr);
        }

        // 处理右子树或访问节点（后序）
        if (type == POSTORDER) {
            // 右子树已处理或不存在，可以访问当前节点
            if (Ptr->rchild == Pre || !Ptr->rchild) {
                Visit(Ptr);
                Pre = Ptr;
                Ptr = NULL;
            } else {
                // 重新入栈并处理右子树
                Push(S, Ptr);
                Ptr = Ptr->rchild;
            }
        } else { // 前序或中序处理右子树
            if (Ptr->rchild) {
                Ptr = Ptr->rchild;
            } else {
                Ptr = NULL;
            }
        }
    }
}

显示栈模拟

显式栈模拟递归过程实现二叉树中序遍历的非递归方法

层次遍历

队列实现

阿Q就不用传统方法写了，用STL容器 Queue 快速完成

#include<Queue>
#include<iostream>

typedef char Elemtype;

typedef struct BtNode
{
    /* data */
    Elemtype data;
    struct BtNode *lchild, *rchild;
    BtNode(Elemtype x) : data(x), lchild(nullptr), rchild(nullptr) {}
    // 结构体( 形参 ): 结构体成员设初值;
}BtNode,*Btree;


void operate(BtNode *node)
{
    std::cout << node->data << "  ";
}


void LevelOrder(Btree T) 
{
    // 用队列辅助 二叉树的层次遍历
    std::queue<BtNode *> Q;  // 存指针比存结构体成员省空间
    
    Btree ptr = T;
    // 入队根元素
    Q.push(ptr);
    
    // 入队 各层（除第一层）的结点指针
    while(!Q.empty())
    {
        // 出队队头元素
        ptr = Q.front();
        Q.pop();

        // 对该结点进行访问操作
        operate(ptr);

        if(ptr->lchild != nullptr) Q.push(ptr->lchild);
        if(ptr->rchild != nullptr) Q.push(ptr->rchild);
    }
} 

int main()
{
    // 快速建树
    Btree root = new BtNode('A');
    root->lchild = new BtNode('B');
    root->rchild = new BtNode('C');
    root->lchild->lchild = new BtNode('D');
    root->lchild->rchild = new BtNode('E');
    root->rchild->lchild = new BtNode('F');
    root->rchild->rchild = new BtNode('G');
    root->rchild->lchild->lchild = new BtNode('H');
    root->rchild->rchild->rchild = new BtNode('I');

    LevelOrder(root);

    return 0;
}
/*
输出结果：
A  B  C  D  E  F  G  H  I  
/*
main函数快速构建的二叉树形状

栈实现

参考队列存储结构的算法题1，用两个栈模拟队列

接下来阿Q用STL容器 Stack 快速实现一下

#include<Stack>
#include<iostream>
typedef char Elemtype;

typedef struct BtNode
{
    /* data */
    Elemtype data;
    struct BtNode *lchild, *rchild;
    BtNode(Elemtype x): data(x), lchild(nullptr), rchild(nullptr){};    
}BtNode,*Btree;


// 用两个栈 S1  和 S2 模拟队列

// 判空
bool QueueEmpty(std::stack<BtNode*> S1, std::stack<BtNode*> S2)
{
    return (S1.empty() && S2.empty());
}

// 进队
bool EnQueue(std::stack<BtNode*> &S1, BtNode *node)
{
    // S1 不可能满（链栈），这也是与 队列存储方式的算法题1区别之处
    // 那就直接往 S1中存就行
    S1.push(node);
    return true;
}

// 出队
bool DeQueue(std::stack<BtNode*> &S1, std::stack<BtNode*> &S2, BtNode *&node)
{
    // 若 S2中有元素，则直接S2出栈顶元素即可
    if(!S2.empty()){
        node = S2.top();
        S2.pop();
        return true;
    }

    // 若S1有元素，S2为空，则需要将 S1的元素全部出栈依次进入S2，然后S2出栈顶元素
    if(!S1.empty() && S2.empty()){
        while(!S1.empty()){
            node = S1.top();
            S1.pop();
            S2.push(node);
        }
        node = S2.top();
        S2.pop();
        return true;
    }

    // S1，S2都空
    else return false;
}

void operate(BtNode *node)
{
    std::cout << node->data << "  ";
}


// 用栈实现 二叉树的层次遍历
void LevelOrder(Btree T)
{
    // 创建两个栈
    std::stack<BtNode*> S1;
    std::stack<BtNode*> S2;

    // 以下均为逻辑上的进队和出队操作（实际为栈的操作）
    BtNode *ptr = T;

    // "入队"根节点
    EnQueue(S1,ptr);

    // "入队"各层（除第一层外）的结点
    while(!QueueEmpty(S1,S2))
    {
        // "出队"队头元素
        DeQueue(S1,S2,ptr);
        operate(ptr);

        // "入队"左右孩子
        if(ptr->lchild != nullptr) EnQueue(S1,ptr->lchild);
        if(ptr->rchild != nullptr) EnQueue(S1,ptr->rchild);
    }
}

// 测试
int main()
{
    // 快速建树
    Btree root = new BtNode('A');
    root->lchild = new BtNode('B');
    root->rchild = new BtNode('C');
    root->lchild->lchild = new BtNode('D');
    root->lchild->rchild = new BtNode('E');
    root->rchild->lchild = new BtNode('F');
    root->rchild->rchild = new BtNode('G');
    root->rchild->lchild->lchild = new BtNode('H');
    root->rchild->rchild->rchild = new BtNode('I');

    LevelOrder(root);
    return 0;
}
/*
输出结果：
A  B  C  D  E  F  G  H  I
*/

前序 + 中序 / 后序 + 中序 确定一棵树

阿Q：为什么一定要中序呢？因为中序 D 在中间，可以把整个遍历结果 分为 左右子树。

先用前序或后序确定根结点，然后根据中序 分为 左右子树，递归下去就行了。

看一道练习就行，如下：

后序 + 中序，当前后序集合最后一个元素是根结点。

应用

二叉树遍历应用

二叉树递归非递归

评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
									

			

			
			
		

	






上一篇
下一篇