二叉树的遍历（堆栈）

爱被打了一巴掌 2023-05-28 12:56 1阅读 0赞

# 二叉树的遍历（堆栈） #

**如何理解用堆栈方式代替递归去遍历二叉树，关键点在于了解每个结点输出时的顺序，以及理解前序中序后序是如何遍历的，这点很重要，可以自己画一个树图，熟练写出遍历的结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70]  
以上图为例，在进行先序遍历的时候，最先输出的是A，而在中序遍历的时候，A是在第四次时候才输出（DEBA）  
以中序遍历为例子，我们要先遍历所有的左子树，把每个左子树上的结点存入堆栈中，然后再pop出堆栈里的结点，输出该结点，然后在判断该结点是否还有右儿子  
下面的代码就是遍历所有的左子树上的结点存入堆栈中，然后依次pop出结点，判断当前结点是否存在右儿子  
以上图为例，D结点虽然没有左儿子和右儿子了，但是在以链表来看，实际上D存在着为NULL的左儿子和右儿子,所以所有的叶子结点都存在值为NULL的左儿子和右儿子，E结点,F结点同理。  
，在第二层循坏While§循坏完后，当前结点是D的左儿子NULL，对于A来说 B是它的左儿子，A是根节点，同理 D此时并不是叶子结点，而是 两个NULL的根节点，通过pop取出D这一个根节点  
然后判断D有没有右儿子，很明显是有一个NULL的右儿子，但是这只是对于链表的存储方式来说，在真正树状图上它是不存在右儿子的，你会发现最外层循坏语句 第二次循坏的时候，pop直接取出  
了B，然后p=p->right，p指向B的右儿子E，所以可以把 语句理解为判断当前结点是否有右儿子结点，没有则输出当前结点的根节点，如果有的话继续对右边的结点进行操作

void firstoder(Tree p)//传送过来的二叉树
    {
          PNode pile =createPNode();//创建一个堆栈pile
     while(p||!IsEmpty(pile))
     {
        while(p)//遍历左子树上的结点
       {
        push(pile,p);
        p=p->left;}
        if(!IsEmpty(pile))
          {
        p=pop(pile);
          printf("%d ",p->date);//输出结点的值
           p=p->right;
        }
      }
    }

先序遍历：看图可知，A B D都是相对于自己的左子树和右子树的根节点，比如 A就是 BDE的根节点，B就是DE的根节点，D就是NULL NULL的根节点，在先序遍历的时候，根节点是最先输出的  
其次是左节点和右结点，，所以在循坏的时候，就要在循坏… 遍历左子树把每个左节点存入的堆栈的时候就要输出当前的结点，也就是只用移动一下输出语句的位置就能从中序变为先序

--------------------

**接下来就是后序遍历**，后续遍历顺序是左 中 右，关键点在于 我们现在处于左结点，我们需要通过上一个头节点去访问跟我们现在的左节点同一层的右结点，去输出右节点，但此时头节点已经pop出来了，所以头节点无法再访问到了，所以我们需要把头节点的值保存下来，压栈进堆栈里。

void firstoder(Tree p)//传送过来的二叉树
    {
          PNode pile =createPNode();//创建一个堆栈pile
     while(p||!IsEmpty(pile))
     {
        while(p)//遍历左子树上的结点
       {
        push(pile,p);
        printf("%d ",p->date);
        p=p->left;}
        if(!IsEmpty(pile))
          {
        Tree temp=(Tree)malloc(sizeof(struct TreeNode));//创建临时指针存储头结点
           p=pop(pile);
           temp=pop;
           p=p->right;
           temp->right=NULL;//遍历的指针指向当前结点的右儿子，把当前结点的右儿子设置NULL，防止死循环
         if(p)
         push(pile,temp);//如果当前结点存在右儿子结点，那么存储当前结点，继续遍历右子树
         else
         printf("%d ",temp->date);//当前结点没有右儿子，那么直接输出当前结点
        }
      }
    }

--------------------

## 我是一个小萌新，第一次写博客，写的很渣，请见谅！— ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70]: /images/20230528/94bf15cee9de4d9682b59abc09d58515.png