【数据结构和算法】【二叉树】二叉树遍历的代码实现

阳光穿透心脏的1/2处 2022-08-13 12:55 150阅读 0赞

二叉树的顺序存储结构：

使用数组表示，将二叉树填充为完全二叉树并依次自上而下、自左至右进行编号\[1-n\]，而后将编号为\[1-n\]的结点元素一一对应地存储在数组下标为\[0-(n-1)\]的数组元素中。

二叉树的链式存储结构：

1、**二叉链表**：结点中有两个链域（指针），分别指向左儿子、右儿子；

2、**三叉链表**：结点中有三个链域（指针），分别指向左儿子、右儿子、双亲；

3、**线索链表**：二叉链表的升级版本，将结点中的空链域利用起来，如：左空链域指向遍历的前一个结点，而右空链域指向遍历的后一个结点。

特殊的二叉树概念：

**线索二叉树**：使用线索链表表示的二叉树。也就是基于二叉链表表示的二叉树，将其结点中的空链域利用起来，使其左空链域指向遍历的前一个结点，右空链域指向遍历的后一个结点。

二叉树的遍历方式：**先序遍历**、**中序遍历**、**后续遍历**、**层次遍历**。

根据L、D、R（分别表示遍历左子树、访问根节点、遍历右子树）的组合，共有6种排列顺序。约定“先L后R”，则只有3中排列顺序，分别称之为：先序遍历DLR、中序遍历LDR、后序遍历LRD。

拿到一颗二叉树，快速写出各类遍历方式的结点访问顺序的方法参考《数据结构》P130“图6.10 三种遍历过程示意图”。

结点穿越原则：1、方向向下时，总是指向儿子结点的左侧；2、方向向上时，作为左儿子则指向双亲的左侧，作为右儿子则指向双亲的右侧；3、左儿子指向双亲后，再指向右儿子。

![Center][]

三种遍历的非递归实现（空指针不入栈）总体步骤：

步骤1：建立堆栈并初始化；

步骤2：根指针入栈；（中序遍历时，根指针无需入栈）

步骤3：遍历过程；（重点！！）

步骤4：销毁堆栈。

注：

1、入栈时要判定指针是否为空，空的话就不入栈，以确保栈中的指针都是有对应节点的；

2、出栈时可以立即访问该节点（出栈==遍历/访问），因为入栈保证了都是非空节点。

<table style="font-size:undefined; border-collapse:collapse; margin-top:10px; margin-bottom:10px; font-family:微软雅黑; width:970px"> 
 <tbody style="background-color:inherit"> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:27px; background-color:inherit; width:87px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">遍历方式</span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:27px; background-color:inherit; width:123px"> <span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="background-color:inherit"><span style="font-size:18px">辅助变量</span></span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:27px; background-color:inherit; width:104px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">循环原则</span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:27px; background-color:inherit; width:250px"> <span style="background-color:inherit"><span style="color:#ff0000; background-color:inherit"><span style="font-size:18px"><span style="font-family:Simsun; background-color:inherit">每次循环做的事情（</span><span style="font-family:Simsun; background-color:inherit">空指针不入栈</span><span style="font-family:Simsun; background-color:inherit">）</span></span></span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:27px; background-color:inherit; width:301px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">代码框架</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:87px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">先序遍历</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:123px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">p为出栈指针</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:104px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">栈不空时进行循环</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:250px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">出栈访问 -&gt; 右子树入栈 -&gt; &nbsp;左子树入栈</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:301px"> <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">while (栈不空)<br style="background-color:inherit"> <span style="color:#ff0000; background-color:inherit">pop visit;&nbsp;push right;&nbsp;push left;</span></span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:87px"> <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">中序遍历</span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:123px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">p为出栈指针和<span style="background-color:inherit"><span style="color:#ff0000; background-color:inherit">遍历指针，并初始为T</span></span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:104px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px"><span style="color:#ff0000; background-color:inherit"><span style="background-color:inherit">p不空</span></span>或栈不空时进行循环</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:250px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">p不空则将p入栈，并将p指向其左子树；</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">p空则出栈访问，并将p指向栈顶结点的右子树；</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:301px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun"><span style="font-size:18px">while (栈不空 || p不空)</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">if (p) { push(p); p = p-&gt;left; }</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">else { pop visit; p&nbsp;= p-&gt;right;&nbsp;}</span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:87px"> <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">后续遍历</span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:123px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">p为出栈指针；<span style="background-color:inherit">pre为已完成出栈/遍历的结点指针，并初始为NULL</span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:104px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">栈不空时进行循环</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:250px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; background-color:inherit"><span style="font-size:18px">查看栈顶指针(GetTop)：如果左右子树都完成了遍历或者pre为其左儿子或者pre为其右儿子则出栈访问并刷新pre；否则<span style="line-height:1.5">右子树入栈 -&gt; &nbsp;左子树入栈</span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:301px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun"><span style="font-size:18px">while (栈不空)</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">GetTop(p);</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:Simsun; color:#ff0000; background-color:inherit"><span style="font-size:18px">if () {&nbsp;<span style="line-height:1.5">pop visit; pre = p;</span><span style="line-height:1.5">&nbsp;}</span></span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="line-height:1.5"><span style="font-family:Simsun; color:rgb(255,0,0); background-color:inherit"><span style="font-size:18px">else { push right; push left; }</span></span></span> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

先序遍历二叉树（非递归 - 根指针不入栈）

void PreOrderTraverseNoRec(BiTree T)
    {
        SqStack S; // 堆栈管理结构
        BiTree p; // 二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针入栈
        (void)Push(&S, &T);
    
        // STEP3: 遍历
        while (!StackEmpty(&S))
        {
            (void)Pop(&S, &p);
            Visit(p->data);
            if (p->rchild) (void)Push(&S, &p->rchild);
            if (p->lchild) (void)Push(&S, &p->lchild);
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }

中序遍历二叉树（非递归 - 空指针不入栈）

void InOrderTraverseNoRec2(BiTree T)
    {
        SqStack S;
        BiTree p; // 二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针在下面循环中入栈入栈
        //(void)Push(&S, &T);
    
        // STEP3: 遍历
        p = T;
        while (p || !StackEmpty(&S))
        {
            if (p)
            {
                (void)Push(&S, &p);
                p = p->lchild;
            }
            else
            {
                (void)Pop(&S, &p);
                Visit(p->data);
                p = p->rchild;
            }
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }

后序遍历二叉树（非递归 - 空指针不入栈）

void PostOrderTraverseNoRec(BiTree T)
    {
        SqStack S; // 堆栈管理结构
        BiTree p; // 二叉树根节点指针
        BiTree pre = NULL; // 已访问完成的二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针入栈
        (void)Push(&S, &T);
    
        // STEP3: 遍历
        while (!StackEmpty(&S))
        {
            (void)GetTop(&S, &p);
            if ((!p->lchild && !p->rchild)
                || (pre && ((p->lchild == pre) || (p->rchild == pre))))
            {
                (void)Pop(&S, &p);
                Visit(p->data);
                pre = p;
            }
            else
            {
                if (p->rchild) (void)Push(&S, &p->rchild);
                if (p->lchild) (void)Push(&S, &p->lchild);
            }
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }

**二叉树遍历的全部代码实现**：

<span style="font-family:SimSun;">// Filename: bitree.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "sq_stack.h"
    
    #ifndef _OK_
    #define OK  0
    #endif
    
    #ifndef _ERROR_
    #define ERROR  1
    #endif
    
    #ifndef _TRUE_
    #define TRUE  1
    #endif
    
    #ifndef _FALSE_
    #define FALSE  0
    #endif
    
    #ifndef _BiTNode_
    #define _BiTNode_
    typedef char TElemType;
    
    typedef struct BiTNode
    {
        TElemType data;
        struct BiTNode *lchild;
        struct BiTNode *rchild;
    } BiTNode, *BiTree;
    #endif // _BiTNode_
    
    // 创建二叉树，按照先序遍历的方式进行输入
    //               A
    //      B                 ^
    //  ^       C
    //        ^    ^
    //上面的二叉树对应的先序输入序列为： AB^C^^^
    void CreateBiTree(BiTree *pT)
    {
        char c;
        scanf("%c", &c);
    
        if (' ' == c)
        {
            *pT = NULL;
        }
        else
        {
            *pT = (BiTNode *)malloc(sizeof(BiTNode));
            (*pT)->data = c;
            CreateBiTree(&(*pT)->lchild);
            CreateBiTree(&(*pT)->rchild);
        }
    
        return;
    }
    
    // 访问根结点
    void Visit(char data)
    {
        printf("%c", data);
        return;
    }
    
    // 先序遍历二叉树（递归）
    void PreOrderTraverse(BiTree T)
    {
        if (!T) return;
        Visit(T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
        return;
    }
    
    // 先序遍历二叉树（非递归 - 根指针不入栈）
    void PreOrderTraverseNoRec(BiTree T)
    {
        SqStack S;  // 堆栈管理结构
        BiTree p;   // 二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针入栈
        (void)Push(&S, &T);
    
        // STEP3: 遍历
        while (!StackEmpty(&S))
        {
            (void)Pop(&S, &p);
            Visit(p->data);
            if (p->rchild) (void)Push(&S, &p->rchild);
            if (p->lchild) (void)Push(&S, &p->lchild);
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }
    
    // 中序遍历二叉树（递归）
    void InOrderTraverse(BiTree T)
    {
        if (!T) return;
        InOrderTraverse(T->lchild);
        Visit(T->data);
        InOrderTraverse(T->rchild);
        return;
    }
    
    // 中序遍历二叉树（非递归 - 空指针入栈）
    void InOrderTraverseNoRec1(BiTree T)
    {
        SqStack S;
        BiTree p; // 二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针入栈
        (void)Push(&S, &T);
    
        // STEP3: 遍历
        while (!StackEmpty(&S))
        {
            while ((OK == GetTop(&S, &p)) && p)
            {
                (void)Push(&S, &p->lchild);
            }
    
            (void)Pop(&S, &p);
    
            if (!StackEmpty(&S))
            {
                (void)Pop(&S, &p); Visit(p->data);
                (void)Push(&S, &p->rchild);
            }
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }
    
    // 中序遍历二叉树（非递归 - 空指针不入栈）
    void InOrderTraverseNoRec2(BiTree T)
    {
        SqStack S;
        BiTree p;    // 二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针在下面循环中入栈入栈
        //(void)Push(&S, &T);
    
        // STEP3: 遍历
        p = T;
        while (p || !StackEmpty(&S))
        {
            if (p)
            {
                (void)Push(&S, &p);
                p = p->lchild;
            }
            else
            {
                (void)Pop(&S, &p);
                Visit(p->data);
                p = p->rchild;
            }
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }
    
    // 后序遍历二叉树（递归）
    void PostOrderTraverse(BiTree T)
    {
        if (!T) return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        Visit(T->data);
        return;
    }
    
    // 后序遍历二叉树（非递归 - 根指针不入栈）
    void PostOrderTraverseNoRec(BiTree T)
    {
        SqStack S;  // 堆栈管理结构
        BiTree p;   // 二叉树根节点指针
        BiTree pre = NULL; // 已访问完成的二叉树根节点指针
    
        // 空树直接返回
        if (!T) return;
    
        // STEP1: 建立堆栈并初始化
        (void)InitStack(&S);
    
        // STEP2: 根指针入栈
        (void)Push(&S, &T);
    
        // STEP3: 遍历
        while (!StackEmpty(&S))
        {
            (void)GetTop(&S, &p);
            if ((!p->lchild && !p->rchild)
                || (pre && ((p->lchild == pre) || (p->rchild == pre))))
            {
                (void)Pop(&S, &p);
                Visit(p->data);
                pre = p;
            }
            else
            {
                if (p->rchild) (void)Push(&S, &p->rchild);
                if (p->lchild) (void)Push(&S, &p->lchild);
            }
        }
    
        // STEP4: 销毁堆栈
        (void)DestroyStack(&S);
    
        return;
    }
    
    int main()
    {
    	BiTree T = NULL;
    	int input;
    
    	while (1)
    	{
    		printf("----------------------------------\n");
    		printf("二叉树基本操作\n");
    		printf("----------------------------------\n");
    		printf("0.建立二叉树的存储结构\n");
    		printf("1.求解二叉树的前序遍历\n");
    		printf("2.求解二叉树的中序遍历\n");
    		printf("3.求解二叉树的后序遍历\n");
    		printf("9.退出系统\n");
    		printf("----------------------------------\n");
    		printf("请选择:");
    		scanf("%d", &input);
    		getchar();
    
    		switch (input)
    		{
                case 0:
                    printf("输入二叉树的先序序列结点值: --> ");  // 测试样例：ABC^^DE^G^^F^^^
                    CreateBiTree(&T);
                    printf("二叉树的链式存储结构建立完成!\n");
                    break;
    
    
                case 1:
                    printf("该二叉树的前序遍历序列（递归）是: --> ");   // 目标输出：ABCDEGF
                    PreOrderTraverse(T);
                    printf("\n");
    
                    printf("该二叉树的前序遍历序列（非递归）是: --> ");
                    PreOrderTraverseNoRec(T);
                    printf("\n");
                    break;
    
                case 2:
                    printf("该二叉树的中序遍历序列（递归）是:--> ");    // 目标输出：CBEGDFA
                    InOrderTraverse(T);
                    printf("\n");
    
                    printf("该二叉树的中序遍历序列（非递归 空指针入栈）是:--> ");
                    InOrderTraverseNoRec1(T);
                    printf("\n");
    
                    printf("该二叉树的中序遍历序列（非递归 空指针不入栈）是:--> ");
                    InOrderTraverseNoRec2(T);
                    printf("\n");
                    break;
    
                case 3:
                    printf("该二叉树的后序遍历序列（递归）是: --> ");   // 目标输出：CGEFDBA
                    PostOrderTraverse(T);
                    printf("\n");
    
                    printf("该二叉树的后序遍历序列（非递归）是: --> ");
                    PostOrderTraverseNoRec(T);
                    printf("\n");
                    break;
    
                case 9:
                    printf("系统已退出！\n");
                    exit(0);
    
                default:
                    printf("输入错误，退出！\n");
                    exit(0);
    		}
    	}
    
    	return 0;
    }
    </span>

参考文章：[http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html][http_www.cnblogs.com_dolphin0520_archive_2011_08_25_2153720.html]

[Center]: /images/20220810/47ce94914b9042d5a72df4d31428bdeb.png
[http_www.cnblogs.com_dolphin0520_archive_2011_08_25_2153720.html]: http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html