精华内容
下载资源
问答
  • 数据结构试验报告用先序中序建立二叉树后序遍历非递归.doc
  • 前言 在前两篇文章二叉树和二叉搜索树中已经涉及到了二叉树的三种遍历。递归写法,只要理解思想,几行代码。可是非递归写法却很不容易。...其中,中序遍历的非递归写法最简单,后序遍历最难。我们的讨论基础是这样的:

    前言

    在前两篇文章二叉树二叉搜索树中已经涉及到了二叉树的三种遍历。递归写法,只要理解思想,几行代码。可是非递归写法却很不容易。这里特地总结下,透彻解析它们的非递归写法。其中,中序遍历的非递归写法最简单,后序遍历最难。我们的讨论基础是这样的:    

    //Binary Tree Node
    typedef struct node
    {
    	int data;
    	struct node* lchild;  //左孩子
    	struct node* rchild;  //右孩子
    }BTNode;

    首先,有一点是明确的:非递归写法一定会用到栈,这个应该不用太多的解释。我们先看中序遍历:

    中序遍历

    分析

    中序遍历的递归定义:先左子树,后根节点,再右子树。如何写非递归代码呢?一句话:让代码跟着思维走。我们的思维是什么?思维就是中序遍历的路径。假设,你面前有一棵二叉树,现要求你写出它的中序遍历序列。如果你对中序遍历理解透彻的话,你肯定先找到左子树的最下边的节点。那么下面的代码就是理所当然的:

    中序代码段(i)    

    BTNode* p = root;  //p指向树根
    stack<BTNode*> s;  //STL中的栈
    //一直遍历到左子树最下边,边遍历边保存根节点到栈中
    while (p)
    {
    	s.push(p);
    	p = p->lchild;
    }

    保存一路走过的根节点的理由是:中序遍历的需要,遍历完左子树后,需要借助根节点进入右子树。代码走到这里,指针p为空,此时无非两种情况:


    说明:

    1. 上图中只给出了必要的节点和边,其它的边和节点与讨论无关,不必画出。
    2. 你可能认为图a中最近保存节点算不得是根节点。如果你看过树、二叉树基础,使用扩充二叉树的概念,就可以解释。总之,不用纠结这个没有意义问题。
    3. 整个二叉树只有一个根节点的情况可以划到图a。
    仔细想想,二叉树的左子树,最下边是不是上图两种情况?不管怎样,此时都要出栈,并访问该节点。这个节点就是中序序列的第一个节点。根据我们的思维,代码应该是这样:   
    p = s.top();
    s.pop();
    cout << p->data;

    我们的思维接着走,两图情形不同得区别对待:
    1.图a中访问的是一个左孩子,按中序遍历顺序,接下来应访问它的根节点。也就是图a中的另一个节点,高兴的是它已被保存在栈中。我们只需这样的代码和上一步一样的代码:
    p = s.top();
    s.pop();
    cout << p->data;
      
    左孩子和根都访问完了,接着就是右孩子了,对吧。接下来只需一句代码:p=p->rchild;在右子树中,又会新一轮的代码段(i)、代码段(ii)……直到栈空且p空。

    2.再看图b,由于没有左孩子,根节点就是中序序列中第一个,然后直接是进入右子树:p=p->rchild;在右子树中,又会新一轮的代码段(i)、代码段(ii)……直到栈空且p空。
    思维到这里,似乎很不清晰,真的要区分吗?根据图a接下来的代码段(ii)这样的:
    p = s.top();
    s.pop();
    cout << p->data;
    p = s.top();
    s.pop();
    cout << p->data;
    p = p->rchild;

    根据图b,代码段(ii)又是这样的:
    p = s.top();
    s.pop();
    cout << p->data;
    p = p->rchild;

    我们可小结下:遍历过程是个循环,并且按代码段(i)、代码段(ii)构成一次循环体,循环直到栈空且p空为止。   
    不同的处理方法很让人抓狂,可统一处理吗?真的是可以的!回顾扩充二叉树,是不是每个节点都可以看成是根节点呢?那么,代码只需统一写成图b的这种形式。也就是说代码段(ii)统一是这样的:

    中序代码段(ii)   

    p = s.top();
    s.pop();
    cout << p->data;
    p = p->rchild;
    

    口说无凭,得经的过理论检验。
    图a的代码段(ii)也可写成图b的理由是:由于是叶子节点,p=-=p->rchild;之后p肯定为空。为空,还需经过新一轮的代码段(i)吗?显然不需。(因为不满足循环条件)那就直接进入代码段(ii)。看!最后还是一样的吧。还是连续出栈两次。看到这里,要仔细想想哦!相信你一定会明白的。

    这时写出遍历循环体就不难了:     
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
    	//代码段(i)一直遍历到左子树最下边,边遍历边保存根节点到栈中
    	while (p)
    	{
    		s.push(p);
    		p = p->lchild;
    	}
    	//代码段(ii)当p为空时,说明已经到达左子树最下边,这时需要出栈了
    	if (!s.empty())
    	{
    		p = s.top();
    		s.pop();
    		cout << setw(4) << p->data;
    		//进入右子树,开始新的一轮左子树遍历(这是递归的自我实现)
    		p = p->rchild;
    	}
    }

    仔细想想,上述代码是不是根据我们的思维走向而写出来的呢?再加上边界条件的检测,中序遍历非递归形式的完整代码是这样的:

    中序遍历代码一          

    //中序遍历
    void InOrderWithoutRecursion1(BTNode* root)
    {
    	//空树
    	if (root == NULL)
    		return;
    	//树非空
    	BTNode* p = root;
    	stack<BTNode*> s;
    	while (!s.empty() || p)
    	{
    		//一直遍历到左子树最下边,边遍历边保存根节点到栈中
    		while (p)
    		{
    			s.push(p);
    			p = p->lchild;
    		}
    		//当p为空时,说明已经到达左子树最下边,这时需要出栈了
    		if (!s.empty())
    		{
    			p = s.top();
    			s.pop();
    			cout << setw(4) << p->data;
    			//进入右子树,开始新的一轮左子树遍历(这是递归的自我实现)
    			p = p->rchild;
    		}
    	}
    }

    恭喜你,你已经完成了中序遍历非递归形式的代码了。回顾一下难吗?
    接下来的这份代码,本质上是一样的,相信不用我解释,你也能看懂的。

    中序遍历代码二   

    //中序遍历
    void InOrderWithoutRecursion2(BTNode* root)
    {
    	//空树
    	if (root == NULL)
    		return;
    	//树非空
    	BTNode* p = root;
    	stack<BTNode*> s;
    	while (!s.empty() || p)
    	{
    		if (p)
    		{
    			s.push(p);
    			p = p->lchild;
    		}
    		else
    		{
    			p = s.top();
    			s.pop();
    			cout << setw(4) << p->data;
    			p = p->rchild;
    		}
    	}
    }

    前序遍历

    分析

    前序遍历的递归定义:先根节点,后左子树,再右子树。有了中序遍历的基础,不用我再像中序遍历那样引导了吧。
    首先,我们遍历左子树,边遍历边打印,并把根节点存入栈中,以后需借助这些节点进入右子树开启新一轮的循环。还得重复一句:所有的节点都可看做是根节点。根据思维走向,写出代码段(i):

    前序代码段(i)

    //边遍历边打印,并存入栈中,以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
    while (p)
    {
    	cout << setw(4) << p->data;
    	s.push(p);
    	p = p->lchild;
    }

    接下来就是:出栈,根据栈顶节点进入右子树。

    前序代码段(ii)   

    //当p为空时,说明根和左子树都遍历完了,该进入右子树了
    if (!s.empty())
    {
    	p = s.top();
    	s.pop();
    	p = p->rchild;
    }

    同样地,代码段(i)(ii)构成了一次完整的循环体。至此,不难写出完整的前序遍历的非递归写法。

    前序遍历代码一   

    void PreOrderWithoutRecursion1(BTNode* root)
    {
    	if (root == NULL)
    		return;
    	BTNode* p = root;
    	stack<BTNode*> s;
    	while (!s.empty() || p)
    	{
    		//边遍历边打印,并存入栈中,以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
    		while (p)
    		{
    			cout << setw(4) << p->data;
    			s.push(p);
    			p = p->lchild;
    		}
    		//当p为空时,说明根和左子树都遍历完了,该进入右子树了
    		if (!s.empty())
    		{
    			p = s.top();
    			s.pop();
    			p = p->rchild;
    		}
    	}
    	cout << endl;
    }

    下面给出,本质是一样的另一段代码:

    前序遍历代码二    

    //前序遍历
    void PreOrderWithoutRecursion2(BTNode* root)
    {
    	if (root == NULL)
    		return;
    	BTNode* p = root;
    	stack<BTNode*> s;
    	while (!s.empty() || p)
    	{
    		if (p)
    		{
    			cout << setw(4) << p->data;
    			s.push(p);
    			p = p->lchild;
    		}
    		else
    		{
    			p = s.top();
    			s.pop();
    			p = p->rchild;
    		}
    	}
    	cout << endl;
    }

    二叉树中使用的是这样的写法,略有差别,本质上也是一样的:

    前序遍历代码三 

    void PreOrderWithoutRecursion3(BTNode* root)
    {
    	if (root == NULL)
    		return;
    	stack<BTNode*> s;
    	BTNode* p = root;
    	s.push(root);
    	while (!s.empty())  //循环结束条件与前两种不一样
    	{
    		//这句表明p在循环中总是非空的
    		cout << setw(4) << p->data;
    		/*
    		栈的特点:先进后出
    		先被访问的根节点的右子树后被访问
    		*/
    		if (p->rchild)
    			s.push(p->rchild);
    		if (p->lchild)
    			p = p->lchild;
    		else
    		{//左子树访问完了,访问右子树
    			p = s.top();
    			s.pop();
    		}
    	}
    	cout << endl;
    }

    最后进入最难的后序遍历:

    后序遍历

    分析

    后序遍历递归定义:先左子树,后右子树,再根节点。后序遍历的难点在于:需要判断上次访问的节点是位于左子树,还是右子树。若是位于左子树,则需跳过根节点,先进入右子树,再回头访问根节点;若是位于右子树,则直接访问根节点。直接看代码,代码中有详细的注释。

    后序遍历代码一   

    //后序遍历
    void PostOrderWithoutRecursion(BTNode* root)
    {
    	if (root == NULL)
    		return;
    	stack<BTNode*> s;
    	//pCur:当前访问节点,pLastVisit:上次访问节点
    	BTNode* pCur, *pLastVisit;
    	//pCur = root;
    	pCur = root;
    	pLastVisit = NULL;
    	//先把pCur移动到左子树最下边
    	while (pCur)
    	{
    		s.push(pCur);
    		pCur = pCur->lchild;
    	}
    	while (!s.empty())
    	{
    		//走到这里,pCur都是空,并已经遍历到左子树底端(看成扩充二叉树,则空,亦是某棵树的左孩子)
    		pCur = s.top();
    		s.pop();
    		//一个根节点被访问的前提是:无右子树或右子树已被访问过
    		if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
    		{
    			cout << setw(4) << pCur->data;
    			//修改最近被访问的节点
    			pLastVisit = pCur;
    		}
    		/*这里的else语句可换成带条件的else if:
    		else if (pCur->lchild == pLastVisit)//若左子树刚被访问过,则需先进入右子树(根节点需再次入栈)
    		因为:上面的条件没通过就一定是下面的条件满足。仔细想想!
    		*/
    		else
    		{
    			//根节点再次入栈
    			s.push(pCur);
    			//进入右子树,且可肯定右子树一定不为空
    			pCur = pCur->rchild;
    			while (pCur)
    			{
    				s.push(pCur);
    				pCur = pCur->lchild;
    			}
    		}
    	}
    	cout << endl;
    }

    下面给出另一种思路下的代码。它的想法是:给每个节点附加一个标记(left,right)。如果该节点的左子树已被访问过则置标记为left;若右子树被访问过,则置标记为right。显然,只有当节点的标记位是right时,才可访问该节点;否则,必须先进入它的右子树。详细细节看代码中的注释。

    后序遍历代码二

    //定义枚举类型:Tag
    enum Tag{left,right};
    //自定义新的类型,把二叉树节点和标记封装在一起
    typedef struct
    {
    	BTNode* node;
    	Tag tag;
    }TagNode;    
    //后序遍历  
    void PostOrderWithoutRecursion2(BTNode* root)
    {
    	if (root == NULL)
    		return;
    	stack<TagNode> s;
    	TagNode tagnode;
    	BTNode* p = root;
    	while (!s.empty() || p)
    	{
    		while (p)
    		{
    			tagnode.node = p;
    			//该节点的左子树被访问过
    			tagnode.tag = Tag::left;
    			s.push(tagnode);
    			p = p->lchild;
    		}
    		tagnode = s.top();
    		s.pop();
    		//左子树被访问过,则还需进入右子树
    		if (tagnode.tag == Tag::left)
    		{
    			//置换标记
    			tagnode.tag = Tag::right;
    			//再次入栈
    			s.push(tagnode);
    			p = tagnode.node;
    			//进入右子树
    			p = p->rchild;
    		}
    		else//右子树已被访问过,则可访问当前节点
    		{
    			cout << setw(4) << (tagnode.node)->data;
    			//置空,再次出栈(这一步是理解的难点)
    			p = NULL;
    		}
    	}
    	cout << endl;
    }<span style="font-family: 'Courier New'; ">  </span>

    总结

    思维和代码之间总是有巨大的鸿沟。通常是思维正确,清楚,但却不易写出正确的代码。要想越过这鸿沟,只有多尝试、多借鉴,别无它法。
    以下几点是理解上述代码的关键:
    1. 所有的节点都可看做是父节点(叶子节点可看做是两个孩子为空的父节点)。
    2. 把同一算法的代码对比着看。在差异中往往可看到算法的本质。
    3. 根据自己的理解,尝试修改代码。写出自己理解下的代码。写成了,那就是真的掌握了。

    专栏目录:



    展开全文
  • 后序遍历非递归

    2016-08-30 23:15:13
    leetcode中有这么一道题,递归来实现二叉树的后序遍历。 二叉树的后序遍历顺序为,root->left, root->right, root,因此需要保存根节点的状态。显然使用栈来模拟递归的过程,但是难点是怎么从root->right转换到...
    leetcode中有这么一道题,非递归来实现二叉树的后序遍历。

    二叉树的后序遍历顺序为,root->left, root->right, root,因此需要保存根节点的状态。显然使用栈来模拟递归的过程,但是难点是怎么从root->right转换到root。

                                    A

                             B             C

                       D        E                 H

                                       F

    后序序列:DFEBHCA
    对应代码里的栈s 入栈顺序: 自己对应代码进行模拟
    方法1:
    对于节点p可以分情况讨论
    1. p如果是叶子节点,直接输出
    2. p如果有孩子,且孩子没有被访问过,则按照右孩子,左孩子的顺序依次入栈
    3. p如果有孩子,而且孩子都已经访问过,则访问p节点
     
    如何来表示出p的孩子是否都已经访问过了呢?
    pre表示刚刚访问过的结点,如果等于当前访问结点的孩子,就表示p的孩子都已经都访问过了,因为在栈里边,父节点是先进后出的。
    pre!=NULL&&(pre==cur->lchild||pre==cur->rchild
    代码如下
    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);
            }
        }    
    }

    展开全文
  • 二叉树先序,中序,后序遍历非递归实现 二叉树先序,中序,后序遍历非递归实现
  • 自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现...2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历非递归算法思路 遍历过程:(如图所示) 图1 前序遍历和中序遍历流程图   ...
    
    

    二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言)

    1. 前序遍历和中序遍历非递归算法思路

    前序和中序非递归遍历的C代码

    2. 后序遍历非递归算法思路

    后序非递归遍历的C代码


    1. 前序遍历和中序遍历非递归算法思路

    遍历过程:(如图所示)

    图1 前序遍历和中序遍历流程图

     

    从当前节点开始遍历:(当入栈时访问节点内容,则为前序遍历;出栈时访问,则为中序遍历)

    1. 若当前节点存在,就存入栈中,并访问左子树;

    2. 直到当前节点不存在,就出栈,并通过栈顶节点访问右子树;

    3. 不断重复12,直到当前节点不存在且栈空。

     

    Tips:我们很容易发现,在理解并写好该非递归遍历代码后,只需要在入栈、出栈的时候,分别进行节点访问输出,即可分别得到前序、中序的非递归遍历代码!!!

     

    便于理解的伪代码:

    
     
    1. void preOrder(TreeNode *T){
    2.     p = T
    3.     while(p不空||栈不空){
    4.         if(p不空){       //两种情况:1.栈不空;2.栈空
    5.             p入栈;
    6.             (前序遍历,访问)
    7.             入p左子节点;
    8.         } else{             //一种情况:当前节点为空,但栈不空
    9.             p=出栈;
    10.             (中序遍历,访问)
    11.             入p右子节点;
    12.         }
    13.     }
    14. }

    前序和中序非递归遍历的C代码

    二叉树节点结构体:

    
     
    1. typedef struct TreeNode{
    2. int data;
    3. struct TreeNode *lChild;
    4. struct TreeNode *rChild;
    5. }TreeNode;

    前序遍历非递归:

    
     
    1. void preOrder(TreeNode *T){
    2. TreeNode * stack[ 15];
    3. int top = -1;
    4. TreeNode *p = T;
    5. while(p!= NULL||top!= -1){
    6. if(p!= NULL){
    7. stack[++ top] = p;
    8. printf( "%d\t",p->data); //入栈时,访问输出
    9. p = p->lChild;
    10. } else{
    11. p = stack[top --];
    12. p = p->rChild;
    13. }
    14. }
    15. }

    中序遍历非递归:

    
     
    1. void inOrder(TreeNode *T){
    2. TreeNode * stack[ 15];
    3. int top = -1;
    4. TreeNode *p = T;
    5. while(p!= NULL||top!= -1){
    6. if(p!= NULL){
    7. stack[++ top] = p;
    8. p = p->lChild;
    9. } else{
    10. p = stack[top --];
    11. printf( "%d\t",p->data); //出栈时,访问输出
    12. p = p->rChild;
    13. }
    14. }
    15. }

    2. 后序遍历非递归算法思路

    后序遍历整体与前中序遍历过程相似。但要注意,这时对于父节点的访问输出,需要在其右子树遍历完成的前提下进行。所以不能像前中序遍历一样,在遍历完左子树后,就直接出栈。我们需要利用这个未出栈的栈顶元素去获取右子树,在遍历完右子树后,就可以出栈,并对此节点进行访问输出。

    这里我们需要使用一个标记,以区分是从左子树取栈还是从右子树出栈:(如图所示)

    图2 后序遍历流程图

     

    从当前节点开始遍历:

    1. 若当前节点存在,就存入栈中,并且置节点flag为1(第一次访问),然后访问其左子树;

    2. 直到当前节点不存在,需要回退,这里有两种情况:

           1)当栈顶节点flag为1时,则表明是从左子树回退,这时需置栈顶节点flag为2(第二次访问),然后通过栈顶节点访问其右子树(取栈顶节点用,但不出栈)

           2)当栈顶节点flag为2时,则表明是从右子树回退,这时需出栈,并取出栈节点做访问输出。(需要注意的是,输出完毕需要置当前节点为空,以便继续回退。具体可参考代码中的p = NULL)

    3. 不断重复12,直到当前节点不存在且栈空。

     

    Tips:我们很容易发现,当理解并写好后序遍历非递归代码后,只需要在入栈、取栈、出栈的时候,分别进行节点访问输出,即可分别得到前序、中序、后序的非递归遍历代码,是不是非常简单!!!

     

    后序非递归遍历的C代码

    节点结构体:

    
     
    1. typedef struct TreeNode{
    2. int data;
    3. struct TreeNode *lChild;
    4. struct TreeNode *rChild;
    5. }TreeNode;

    后序遍历非递归:

    
     
    1. void postOrder(TreeNode *T){
    2. TreeNode * stack[ 15];
    3. int top = -1;
    4. int flagStack[ 15]; //记录每个节点访问次数栈
    5. TreeNode *p = T;
    6. while(p!= NULL||top!= -1){
    7. if(p!= NULL){ //第一次访问,flag置1,入栈
    8. stack[++ top] = p;
    9. flagStack[top] = 1;
    10. p = p->lChild;
    11. } else{ //(p == NULL)
    12. if(flagStack[top] == 1){ //第二次访问,flag置2,取栈顶元素但不出栈
    13. p = stack[top];
    14. flagStack[top] = 2;
    15. p = p->rChild;
    16. } else{ //第三次访问,出栈
    17. p = stack[top --];
    18. printf( "%d\t",p->data); //出栈时,访问输出
    19. p = NULL; //p置空,以便继续退栈
    20. }
    21. }
    22. }
    23. }

     

    展开全文
  • 用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
  • 后序遍历非递归 Java

    2020-04-04 16:05:13
    思路:借助先序遍历交换子树。...观察发现:交换左右子树的二叉树先序遍历=二叉树逆后序遍历=后序遍历反着来 因此,我们的目标是,想办法吧二叉树变成交换左右子树的二叉树,然后push进一个stack里,最后只要pop出...

    思路:借助先序遍历交换子树。

    创建二叉树

    原二叉树
    交换左右子树的二叉树

     

     得出:

    先序遍历: 1,2,4,5,3,6

    逆后序遍历:1,3,6,2,5,4

    后序遍历:4,5,2,6,3,1

    观察发现:交换左右子树的二叉树先序遍历=二叉树逆后序遍历=后序遍历反着来

    因此,我们的目标是,想办法吧二叉树变成交换左右子树的二叉树,然后push进一个stack里,最后只要pop出来。

    代码实现如下:

       /**
         * 通过后序遍历遍历二叉树
         *
         * @param
         */
        public static void postOrderTraversalWithStack(TreeNode root) {
            Stack<TreeNode> src = new Stack<TreeNode>();
            Stack<TreeNode> re = new Stack<TreeNode>();
            //将节点push进src
            src.push(root);
            while (!src.isEmpty()) {
                TreeNode p = src.pop();
                re.push(p);
                if (p.leftchild != null) {
                    src.push(p.leftchild);
                }
                if (p.rightchild != null) {
                    src.push(p.rightchild);
                }
            }
            //输出最终后序遍历的结果
            while (!re.isEmpty()) {
                System.out.print(re.pop().data + " ");
            }
        }

     

    展开全文
  • 二叉树的后序遍历非递归 算法思想:迭代写法,利用pre记录上一个访问过的结点,与当前结点比较,如果是当前结点的子节点,说明其左右结点均已访问,将当前结点出栈,更新pre记录的对象。** //结构体 typedef ...
  • 问题 G: DS二叉树--后序遍历非递归算法 时间限制: 1 Sec 内存限制: 128 MB 提交: 155 解决: 137 [提交][状态][讨论版] 题目描述 求一颗树的后序遍历的非递归算法 要求:必须是非递归算法,使用堆栈对象来实现 建树...
  • 关于前中后序遍历非递归算法的疑惑自答
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序或者后序...
  • 用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
  • 二叉树的后序遍历非递归算法 关于 (1)如何利用前序遍历创建二叉树 (2)二叉树的前序、中序、后序递归遍历 (3)二叉树的前序、中序非递归遍历 都已经在之前两篇文章中说过了 利用前序遍历创建二叉树,二叉树的...
  • 前几天面试过程中面试官让手写一下二叉树后序遍历的非递归写法,当时没有写出来,本想着可能是因为面试太紧张的原因,才这么简单的题都没写出来,后来特地去研究了一下,发现二叉树的后序遍历非递归实现还真的没我想...
  • 后序遍历非递归算法的实现

    千次阅读 2018-11-14 20:51:09
    后序遍历非递归算法的实现 这个是在前面的基础上,进行后序遍历非递归算法,这个算法是很多求二叉树路径的基础,比如求根结点到某点的路径,或求两个结点最近的公共祖先等。 代码: #include &lt;iostream&...
  • 今天刷后序遍历非递归实现时,因为以前看过借助一个栈和队列来实现,但始终模糊不清,不知道如何写,只好自己捋了一遍,然后查了下,发现和很多人写法有差异,故放出来,欢迎指正,如有知道用栈和队列方式实现的朋友...
  • 二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
  • 后序遍历非递归算法

    万次阅读 2018-05-15 11:02:33
    后序遍历 方法一: //后序遍历 void PostOrderWithoutRecursion(BTNode* root) { if (root == NULL) return; stack<btnode*> s; //pCur:当前访问节点,pLastVisit:上次访问节点 BTNode* pCur, *...
  • 今天复习了二叉搜索树的创建,二叉树的前、中、后序遍历递归与非递归的实现,按层遍历等等。其中较难的是二叉树的后序遍历过程 因此单独拿出来详细分析一下过程,以及在这个过程中我踩得一些坑 /** * 后序非递归...
  • 1. 树的先序遍历、中序遍历、后序遍历非递归实现
  • ***二叉树的前序、中序、后序遍历非递归写法 **非递归方法:栈空间更容易控制 **递归使用栈是系统调用栈,空间比较小,一般也比较固定大小(递归写法更简单) **自己用非递归,手头实现栈,栈的空间在堆上,...
  • 在上篇博客...# 中序遍历非递归实现: 思路: 1、从根节点开始遍历左子树,遇到的每个节点入栈,直到左子树遍历完毕 2、栈顶出栈 当前节点指向其右子...
  • 学习了这个作者的博客http://blog.csdn.net/hackbuteer1/article/details/6583988后序遍历是三种遍历中最难的一种(非递归)作者提供了一种非常简单的遍历方式,我稍作修改...// 后序遍历非递归 { stack<BiTree> s1;
  • 后序遍历非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左子节点和右子结点都已被访问并且左子节点在右子节点前访问才能访问根结点,这就为流程的控制带来了难题。 对于任一结点P,将其入栈,...
  • 二叉树的后序遍历非递归算法

    万次阅读 多人点赞 2019-06-03 11:51:45
    1. 对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用的方法是深度优先遍历树的每一个节点,这些遍历方法都是使用递归函数来进行实现的,在数据量大的情况下是比较低效的,原因在于...
  • 后序遍历非递归实现(转载)

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,217
精华内容 12,486
关键字:

后序遍历非递归