二叉树遍历的递归与非递归算法

￡神魔★判官ぃ 2023-07-17 14:12 12阅读 0赞

### 二叉树的递归遍历（深度优先遍历） ###

先来张图，看看各结点遍历时的情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70][]

**二叉树深度优先遍历总结（分别为第一次，第二次，第三次进入某个结点）：**

1.  先序遍历：先访问根结点，然后先序遍历左子树，最后先序遍历右子树；**根->左->右**
2.  中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树；**左->根->右**
3.  后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根结点；**左->右->根**

**递归遍历代码比较简单，先、中、后序遍历递归代码基本相似，总代码：**

void r(BTNode *p)
    {
        if (p != NULL)
        {
            //第一次进入-先序
            r(p->lchild);
            //第二次进入-中序
            r(p->rchild);
            //第三次进入-后序
        }
    }

**1. 先序遍历递归函数：**

void r(BTNode *p)
    {
        if (p != NULL)
        {
            visit(p);
            r(p->lChild);
            r(p->rChild);
        }
    }

**2. 中序遍历递归函数：**

void r(BTNode *p)
    {
        if (p != NULL)
        {
            r(p->lChild);
            visit(p);
            r(p->rChild);
        }
    }

**3. 后序遍历递归函数：**

void r(BTNode *p)
    {
        if (p != NULL)
        {
            r(p->lChild);
            r(p->rChild);
            visit(p);
        }
    }

### 二叉树的非递归遍历（深度优先遍历） ###

须知：非递归需要自定制辅助栈

**1. 先序遍历非递归化:**

**1）**利用辅助栈将根节点入栈，出栈操作，访问该节点，将其右、左孩子分别入栈，保证左孩子先出来（每次访问节点后，对其左、右孩子需要做一个检测，为空的孩子无需入栈）  
**2）**左孩子出栈后，访问该节点，将其右、左孩子分别入栈，多次操作！  
**3）**直至栈空为止（出栈是在循环之内执行，即使栈空也会执行右左孩子入栈操作）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1][]

**栈辅助先序遍历过程：**

1入栈、1出栈  
3入栈、2入栈、2出栈  
5入栈、4入栈、4出栈  
4没有孩子结点，5出栈、3出栈  
7入栈、6入栈、6出栈  
检测到6右孩子为空，左孩子8不空，8入栈、8出栈  
7没有孩子结点，直接出栈

void preorderNonrecursion(BTNode *bt)
    {
        if (bt != NULL)						//根节点是否为空
        {
            BTNode *Stack[maxSize];
            int top = -1;						//创建栈
            BTNode *p = NULL;					//遍历指针
            Stack[++top] = bt;					//节点入栈
            while(top != -1)					//栈不空时循环
            {
                p = Stack[top--];					//出栈一个元素
                Visit(p);						//访问
                if(p->rChild != NULL)				//右孩子不为空就入栈
                    Stack[++top] = p->rChild;
                if(p->lChild != NULL)				//左孩子不为空就入栈
                    Stack[++top] = p->lChild;
            }
        }
    }

**2. 后序遍历非递归化：**

![format_png][]

根结点：白色  
左子树：黄色  
右子树：红色

先把黄色245（左子树）与红色3687（右子树）交换得到第二条，然后把黄色68和红色7交换、黄色4和红色5交换得到第三条，即逆后序。

// 先序（根左右），而后序（左右根），将后序逆转为逆后序（根右左），逆后序的左右交换即可成为前序（根左右）  
// 在这我们可以使用逆后序（根右左），把逆后序的结果压入一个新栈，出栈就得到后序遍历序列

**1）**将根节点入辅助栈（栈1），出栈操作，将出栈后的该元素入逆序栈（栈2），将其左、右孩子分别入辅助栈，保证右孩子先出栈（每次对其左、右孩子需要做一个检测，为空的孩子无需入栈）；  
**2）**右孩子出辅助栈（栈1），将出栈后的该元素入逆序栈（栈2），将其左、右孩子分别入辅助栈（栈1），多次操作；  
**3）**直至辅助栈空为止，出栈是在循环之内执行，即使栈空也会执行左右孩子入栈操作；  
**4）**逆序栈（栈2）中元素逐个出栈并访问

void postorderNonrecursion(BTNode *bt)
    {
        if (bt != NULL)					        //根节点不为空
        {
            BTNode *Stack1[maxSize];
            int top1= -1;	//创建栈1（辅助遍历的栈）
            BTNode *Stack2[maxSize];
            int top2= -1;	//创建栈2（结果逆序的栈）
            BTNode *p = NULL;				        //遍历指针
            Stack1[++top1] = bt;					//节点入栈1
            while(top1 != -1)					//栈不空时循环
            {
                p = Stack1[top1--];					//栈1出栈一个元素
                Stack2[++top2] = p;					//出栈元素入栈2
                if(p->lChild != NULL)				//左孩子不为空就入栈
                    Stack[++top] = p->lChild;
                if(p->rChild != NULL)				//右孩子不为空就入栈
                    Stack[++top] = p->rChild;
            }
            while(top2 != -1)
            {
                p = Stack2[top2--];					//栈2元素逐个出栈
                Visit(p);						//访问
            }
        }
    }

**3. 中序遍历非递归化：**

**1）**从根节点开始，一直左走，并把途径的左孩子节点入栈；  
**2）**遇到左孩子为空时，栈顶元素出栈，访问该节点，p指向该节点的右孩子；  
**3）**直到栈空或者P为NULL则遍历结束

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2][]

**栈辅助中序遍历过程：**

1入栈、2入栈、4入栈  
4左孩子为空，4出栈、2出栈  
取2的右孩子5入栈，5左孩子为空，5出栈  
1出栈，取其右孩子3入栈、其左孩子6入栈、8入栈  
8左孩子为空，8出栈、6出栈、3出栈  
最后取7入栈、7出栈

void inorderNonrecursion(BTNode *bt)
    {
        if(bt != NULL)                              //树不空
        {
            BTNode *Stack[maxSize];
            int top = -1;    //创建栈
            BTNode *p = NULL;                       //遍历指针
            p = bt;                                 //节点入栈1
            while(top != -1 || p != NULL)           //栈不空或者p不空
            {
                while(p != NULL)
                {
                    Stack[++top] = p;               //入栈
                    p = p->lChild;                   //左走
                }
                if(top != -1)
                {
                    p = Stack[top--];               //出栈
                    Visit(p);                       //访问该节点
                    p = p->rChild;                   //右走
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70]: /images/20230528/56b2ccce982847b8b1c9810fbdbaaca2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1]: /images/20230528/2ff7a448a78744c580b0bf644f3cdbb0.png
[format_png]: /images/20230528/b40a700c50e54259b951f8dd45e83354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2]: /images/20230528/b0868efb5647479981bf6873bf049a0e.png