数据结构与算法之树的遍历

树的 “前” “中” “后” 遍历

//如果要再写一个树太费时间了,所以博主在这篇博客只给出核心代码并赋予GIF演示动画,望大家好好理解以对树的三种遍历方式有更为深刻的理解

  因为递归调用函数是有开销的,而且递归的次数受堆栈大小的限制,所以本篇博客不会
介绍用递归的方式来遍历树.  而是使用 栈 来遍历树.
首先让我们来了解什么是栈?

栈是存放数据对象的一种特殊容器，栈中的元素始终遵循后进先出的顺序

前序遍历(博主上篇已经写过了,所以直接套用上篇的代码):

前序遍历的主要思想就是:

根节点最先入栈,最先出栈

右子节点先入栈后处理;

左子节点后入栈先处理.

  Btree tmp;
  SqStack stack;
  InitStack(stack);
  PushStack(stack, *root);  //根节点进栈
  while (!(IsEmpty(stack))) { //栈为空，所有节点均已处理 
    PopStack(stack, tmp);   //要遍历的节点  
    printf("- %d -", tmp.data);   //打印要便利的节点的值
    if (tmp.rchild != NULL) {
      PushStack(stack, *(tmp.rchild)); //右子节点先入栈，后处理  
    }
    if (tmp.lchild != NULL) {
      PushStack(stack, *(tmp.lchild)); //左子节点后入栈，接下来先 处理  
    }
  }

前序遍历演示

void inOrder(BinTree *root)  //非递归中序遍历
{
     stack<BinTree*> s;
     BinTree *p=root;
     while(p!=NULL||!s.empty())
     {
         while(p!=NULL)
         {
             s.push(p);
             p=p->lchild;
         }
         if(!s.empty())
         {
             p=s.top();
             cout<<p->data<<"";
             s.pop();
             p=p->rchild;
         }
     }   
}

一开始我们 BinTree *p=root;这样就能执行我们的第一个while循环

当跳出第一个while()循环时,就代表我们的中序遍历已经结束了。

1.第二个while在p不为空时执行: 在while循环下,将根节点先入栈，左子节点后入栈，然后继续判断p是否为空再决定是否继续如果满足那么左子节点再继续入栈(因为根节点在最前面所以现在入栈的就只有左子节点了,不会存在根节点反复入栈的情况)。那么while循环完的时候，我们的节点p此时一定为NULL; 如果现在出栈的话我们一定能保证出战的元素使我们要出的第一个节点！！！

2.出栈以及后续操作 if 语句 : 在步骤1操作之后,根节点以及最左边的节点将会全部入栈。此时我们现在的p为NULL;这样我们是无法进行后续操作的,那么我们应该如何做呢???

其实很简单只需要让我们的 p 只想现在的栈顶元素,再将数据输出到控制台，再将这个元素在栈中出栈即可。因为左子节点以及用过了，所以现在我们就执行 p=p->rchile 那么此时又会存在两种情况

（1）存在右子节点------->即p不为空，那么又会进入到步骤1；知道变成第二种情况。

（2）不存在右子节点--------> 那么在执行操作2（即继续出栈，向上查找）

gif演示:

后序遍历:

void postOrder3(BinTree *root)     //非递归后序遍历
{
     stack<BinTree*> s;
     BinTree *cur;                      //当前结点
     BinTree *pre=NULL;                 //前一次访问的结点
     s.push(root);
     while(!s.empty())
     {
         cur=s.top();
         if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
         {
             cout<<cur->data<<"";  //如果当前结点没有孩子结点或者孩子节点都已被访问过
             s.pop();
             pre=cur;
         }
         else
         {
             if(cur->rchild!=NULL)
                 s.push(cur->rchild);
             if(cur->lchild!=NULL)   
                 s.push(cur->lchild);
         }
     }   
} 

对于后序遍历的理解:

首先定义两个可以指向树的指针

cur :指向当前节点

pre 指向上一个节点

现将根节点入栈(这一个会实现根节点最后出栈)

如果打while都已经跳出来了的话那么就说明已经完成后序遍历(因为我们先把根节点压进了栈,所以第一次是不会跳出我们的大循环的)

cur=s.top();将cur指向我们的栈顶(随着栈顶元素不断出栈,cur的指向会不断更改)

if(…) //如果当前结点没有孩子结点或者孩子节点都已被访问过(第一次循环的时候是不会进入这条语句的所以不要纠结最 孩子节点都已被访问过这句话!!!)

cout 想控制台打印元素,然后出栈

pre =cur; 这样就能实现pre指向上一个结点的功能了(也许会有人问,现在不是 pre=cur他们应该是指向一个结点的啊!!! 为什么要说 cur是指向当前节点 pre 是指向上一个结点啊? 因为在if结束了之后 cur就会指向新的栈顶元素!!!)

else(即在if判断不成立时进入else语句!!) 即当前节点存在孩子节点或者孩子节点还未被访问完!!

这里的思想就类似于前序遍历的思想了,只是没有前序遍历的 右节点存在,右节点入栈之后,左节点存在,左节点入栈,接着先入栈的后处理,后入栈的先处理的思想马上出站,而是要在满足我们的if条件才会进行出栈

gif演示:

希望大家能通过本篇博客掌握 树的三中遍历方式.

谢谢观看。?