二叉树的非递归遍历(递归和非递归)

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中, 前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。

一.前序遍历

   前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

  1.递归实现

void pre_order(BTree *root)    
{    
 if(root != NULL)//必不可少的条件,递归的出口   
     {    
        printf("%2c",root->key);    
        pre_order(root->lchild);    
        pre_order(root->rchild);    
 
     }    
}    

 2.非递归实现

    根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再访问它的右子树。因此其处理过程如下:

     对于任一结点P:

     1)访问结点P,并将结点P入栈;

     2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;

     3)直到P为NULL并且栈为空,则遍历结束。

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

二.中序遍历

    中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

    1.递归实现

void in_order(BTree* root)    
{    
 //必不可少的条件,递归的出口  
 if(root != NULL)   
     {    
        in_order(root->lchild);    
        printf("%2c",root->data);    
        in_order(root->rchild);      
     }    
}   

 2.非递归实现

    根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下:

   对于任一结点P,

  1)若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;

  2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;

  3)直到P为NULL并且栈为空则遍历结束

//非递归中序遍历  
void in_order(BTree *root)       
{  
    stack<BTree*> s;  
    BTree *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;  
        }  
    }  
}  

 三.后序遍历

      后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

      1.递归实现

void post_order(BTree* root)    
{    
 //必不可少的条件,递归的出口  
 if(root != NULL)   
    {    
        post_order(root->lchild);    
        post_order(root->rchild);    
        printf("%2c",root->data);    
    }    
}      

 2.非递归实现

       后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。下面介绍两种思路。

      第一种思路:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问, 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。

方 法:要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。如果P不存在左孩子和右孩子,则可以直接访问它;或者P存在左孩子 或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点。若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈 顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。

//非递归后序遍历 
void post_order(BTree* root)       
{  
    stack<BTree*> s;  
 //当前结点 
    BTree *cur = NULL;     
 //前一次访问的结点  
    BTree *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);  
        }  
    }      
}  

四、层次遍历

//采用STL中的queue处理

#include <queue> 
void layerOrder(BTree *tree)  
{  
 if (tree == NULL)  
 return;  
 
    queue<BTree *> q;  
    q.push(tree);  
 
    BTree *p = NULL;  
 while (!q.empty())  
    {  
        p = q.front();  
        visit(p);          
        q.pop();  
 if (p->lchild != NULL)  
            q.push(p->lchild);  
 if (p->rchild != NULL)  
            q.push(p->rchild);  
    }  
}  
/树的深度

int TreeDepth(BTree* root)  
{  
     int nLeft, nRight;  
     if(root == NULL)//必不可少的条件,递归的出口  
         return 0;    
     nLeft = TreeDepth(root->lchild);  
     nRight = TreeDepth(root->rchild);  
     return (nLeft > nRight) ? (nLeft + 1):(nRight + 1);  
}  
  

//总共节点

int totalnode(BTree* root)  
{  
     if(root != NULL)//必不可少的条件,递归的出口  
     {  
         ntotal ++;  
         totalnode(root->lchild);  
         totalnode(root->rchild);  
     }  
     return ntotal;  
}  
  

//叶子节点
int leafnode(BTree* root)  
{  
     if(root != NULL)//必不可少的条件,递归的出口  
     {  
          if((root->lchild == NULL) && (root->rchild == NULL) )  
          {  
              nleaf ++;  
          }  
          leafnode(root->lchild);  
          leafnode(root->rchild);  
     }  
     return nleaf;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二叉搜索树与双向链表(九度OJ1503)

题目描述: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 输入: 输入可能包含多个测试样例...

2637
来自专栏武培轩的专栏

剑指Offer-重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

3668
来自专栏有趣的Python

数据结构探险之树篇数据结构探险之树篇

数据结构探险之树篇 什么是树? 树是节点的有限结合。 ? 1正2倒 ? 概念 根节点:A 双亲:A 孩子:A :b,c,d 度:A的度为3,因为它接着三个节点...

2834
来自专栏有趣的Python

14-数据结构探险系列-树篇

遍历(具体是前中后是相对于二叉树的根来说的,左右一直是先左后右,前中后说的是根的遍历位置):

1394
来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3594
来自专栏Phoenix的Android之旅

Java 集合 Vector

List有三种实现,ArrayList, LinkedList, Vector, 它们的区别在于, ArrayList是非线程安全的, Vector则是线程安全...

772
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

8631
来自专栏desperate633

LeetCode 77. Combinations题目分析代码

组给出两个整数n和k,返回从1......n中选出的k个数的组合。 样例 例如 n = 4 且 k = 2 返回的解为: [[2,4],[3,4],[2...

842
来自专栏Ryan Miao

ArrayList源码阅读

前言 数组是我们最常用最简单的数据结构,Java里对数组做了一个简单的包装,就是ArrayList,提供自动扩容的功能。 最常用法 list在我们日常代码中最为...

2838
来自专栏尾尾部落

[剑指offer] 二叉搜索树的第k个结点

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为4。

912

扫码关注云+社区

领取腾讯云代金券