Java教程

二叉树先序,中序,后序遍历的非递归算法(一)

本文主要是介绍二叉树先序,中序,后序遍历的非递归算法(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前序遍历的非递归算法

<法一>

思路:

二叉树的前序遍历过程:

  1. 从树根开始沿着左子树一直深入,直到最左端无法深入时,返回;
  2. 进入最近深入时遇到结点的右子树,再进行如此的深入和返回;
  3. 直到最后从根节点的右子树返回到根节点为止;

由其深入返回的过程我们知道可以用一个栈来帮助我们消除递归

1.存入根结点:首先判断root(根节点)是否为空,如果为空则直接return,不为空就将根节点压入栈中。这里我随机生成一个树作为例子,

2.进行非递归前序遍历:将A弹出,打印出A结点存入的值,接着再依次检查A是否有右孩子(Rson)和左孩子(Lson)(因为是前序遍历,而栈的特点是先进后出,我们需要优先打印左孩子的值,所以先检查是否有右孩子,如果有的话将右孩子优先压入栈中,如果有的话依次存入栈中,此时栈中全是第二层的元素

随后我们再弹出栈顶结点B,打印他的值,接着依葫芦画瓢,分别再次检查B的右孩子和左孩子,如果有的话分别存入,因为B没有左孩子,所以第三次压栈存入D结点

再次弹出D结点,存入其右孩子和左孩子,栈更新为:

因为G,F为叶子结点,没有孩子,所以分别弹出F,G并打印值,目前为止打印出:ABDFG;

当栈中只剩C时,弹出C,打印值,因为C有右孩子,所以存入其右孩子E,栈更新为:

最后,弹出E,存入其右孩子H:

因为G是叶子结点,所以弹出G后栈为空,整个树也遍历完毕,由此可以得到循环的条件是当且仅当栈不为空时

3.观察特点进行总结:只要左子树还没有遍历完,就会弹出元素的同时,存入新的元素,直到左子树全部被遍历完没有新的元素存入,才会开始遍历右子树,这也构成我们的中序遍历。

代码实现如下:

typedef struct BiTNode
{
  char data;
  struct BiTNode *lson, *rson;
} BiTNode, *BiTree;  //二叉树的结构体

// 二叉树的前序遍历算法1基于STL stack
void PreOrder1(BiTree bt)
{
  stack<BiTree> Stack;
  if (bt == NULL)    //如果根结点为空,直接return
    return;
  Stack.push(bt);    //根结点不为空将其压入栈中
  while (!Stack.empty())  //循环条件:当栈不为空时
  {
    BiTree Cur = Stack.top();  
    cout << Cur->data << endl; 
    Stack.pop();           //取出并打印栈顶元素
    if (Cur->rson)             
      Stack.push(Cur->rson);
    if (Cur->lson)
      Stack.push(Cur->lson);   //分别将栈顶元素的右孩子和左孩子压入栈中
  }
}

<法二>

思路:

1.连续将结点的左孩子压入栈中:此处我仍用这个生成的树进行演示,法二的主要思路是只要当前节点指向左孩子的指针不为NULL,就一直打印当前节点值并压入栈中。

打印:AB

2.弹出栈顶元组:直到一个结点没有左孩子时,此时退出循环,此时只有从B的右孩子D进行入手,所以我们弹出栈顶元素B,并将指针指向该节点的右孩子D,重复第一步的操作:

3.重复1,2步:循环到F时又退出了,我们再重复第二步的操作,弹出F,而F也没有右孩子,所以继续弹出D,将节点指针指向D的右孩子G,继续循环:

注意:由于C,E,H只有右孩子没有左孩子所以只能弹出C后E才能进栈,弹出E后C才能进栈

3.循环结束条件:如果初始的根结点为空,则循环直接退出,进入循环后如果栈中没有新增元素,并且没有新增元素即将入栈(即当前指向的结点为空),代表遍历完成,此时退出循环。

代码实现如下:

// 二叉树的前序遍历算法2基于STL stack
void PreOrder2(BiTree bt)
{
  stack<BiTree> Stack;
  BiTree Cur;
  while (!Stack.empty() || bt != NULL)  //循环终止条件
  {
    while (bt != NULL)   
    {
      cout << bt->data << endl;
      Stack.push(bt);
      bt = bt->lson;
    }
    if (!Stack.empty())   
    {
      Cur = Stack.top();
      Stack.pop();
      bt = Cur->rson;
    }
  }
}

 

这篇关于二叉树先序,中序,后序遍历的非递归算法(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!