精华内容
下载资源
问答
  • 用堆栈实现二叉树的前序遍历/中序遍历/后序遍历的非递归算法算法思想中序遍历前序遍历后续遍历 算法思想 借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序...

    算法思想

    • 借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序遍历、中序遍历和后序遍历在递归函数执行时,结点(作为函数参数)的入栈和出栈过程是完全一样的。

    • 前序遍历是在结点入栈时输出结点信息,然后开始分别对该结点左右子树的遍历;而在中序遍历中,结点出栈时表明刚完成对该结点左子树的遍历,此时可输出该结点信息。

    • 后序遍历必须在左右子树均输出的情况下才能输出该结点。如果直接采用前序遍历、中序遍历的非递归程序,我们没法判别该结点的右子树什么时候遍历结束。为了能知道结点右子树什么时候遍历结束,可以在其左子树遍历结束时做个标记(暂不出栈),等到再次访问到它时说明其右子树刚刚遍历完毕,此时可以输出该结点。

    中序遍历

    • 遇到一个结点,就把它压栈 ,并去遍历它的左子树
    • 当左子树遍历结束 后,从栈顶弹出这个结点并访问它
    • 然后按其右指针再去中序遍历该结点的右子树
    // 中序遍历非递归算法
    void InOrderTraversal(BinTree BT)
    {
        BinTree T = BT;
        Stack S = CreatStack(MaxSize); // 创建并初始化堆栈S
        while (T || !IsEmpty(S))
        {
            while (T)
            {
                // 一直向左并将沿途结点压入堆栈
                Push(S, T);
                T = T->Left;
            }
            if (!IsEmpty(S))
            {
                T = Pop(S);   // 结点弹出堆栈
                printf(% 5d”, T->Data); // (访问) 打印结点
                T = T->Right; // 转向右子树
            }
        }
    }
    

    前序遍历

    // 前序遍历非递归算法
    void PreOrderTraversal(BinTree B )
    {
        BinTree T = BT;
        Stack S = CreatStack(MaxSize); // 创建并初始化堆栈S
        while (T || !IsEmpty(S))
        {
            while (T)
            {
                // 一直向左并将沿途结点压入堆栈
                Push(S, T);
                printf(% 5d”, T->Data); // (访问) 打印结点
                T = T->Left;
            }
            if (!IsEmpty(S))
            {
                T = Pop(S);   // 结点弹出堆栈
                T = T->Right; // 转向右子树
            }
        }
    }
    

    后续遍历

    void PostOrderTraversal(Bintree BT)
    {
        Bintree T = BT;
        Bintree flag = NULL;
        Bintree top;
        Stack S = CreateStack(MaxSize); // 创建并初始化堆栈S
        while (T || !IsEmpty(S))
        {
            while (T)
            {
                // 一直向左并将沿途结点压入堆栈
                push(S, T);
                T = T->Left;
            }
    
            // 获取栈顶元素,此时不出栈
            top = GetTop(S);
    
            // 此时top的左子树在上一个while循环中已访问过,当top的右子树为空或已访问过时打印top结点
            if (top->Right == NULL || top->Right == flag) 
            {
                printf("% 5d", top->Data);
                flag = pop(s);  // 用flag记录这个元素,表示已访问
            }
            else
            {
                T = top->Right;  // 若top的右子树没有被访问过,则将其当做一颗新二叉树访问
            }
        }
    }
    
    展开全文
  • 先序、中序、后序遍历的非递归算法先序遍历中序遍历后序遍历 先序遍历 第一次遇到该结点时输出 public void preOrder(TreeNode root){ if(root==null) return; TreeNode p = root; Stack<TreeNode> ...

    先序、中序、后序遍历的非递归算法

    先序遍历

    第一次遇到该结点时输出

    	public void preOrder(TreeNode root){
    		if(root==null) return;
    		TreeNode p = root;
    		Stack<TreeNode> stack = new Stack<>();
    		while(!stack.isEmpty()||p!=null){
    			//对每一棵树而言,都一直向左下走,直到走到最左下的叶子结点
    			while(p!=null){
    				System.out.print(p.val+"  ");	//先序遍历是第一次遇到该结点的时候输出,即结点入栈
    				stack.push(p);
    				p = p.left;
    			}
    			
    			if(!stack.isEmpty()){
    				p = stack.pop();
    				p = p.right;	//进入最左下叶子结点的右孩子
    			}
    			//进入新一轮循环
    		}
    		
    	}
    

    中序遍历

    第二次遇到该结点时输出

    	public void inOrder(TreeNode root){
    		if(root==null) return;
    		TreeNode p = root;
    		Stack<TreeNode> stack = new Stack<>();
    		while(!stack.isEmpty()||p!=null){
    			//对每一棵树而言,都一直向左下走,直到走到最左下的叶子结点
    			while(p!=null){
    				stack.push(p);
    				p = p.left;
    			}
    			
    			if(!stack.isEmpty()){
    				p = stack.pop();
    				System.out.print(p.val+"  ");	//中序遍历是第二次遇到该结点的时候输出,即结点出栈
    				p = p.right;	//进入最左下叶子结点的右孩子
    			}
    			//进入新一轮循环
    		}
    		
    	}
    

    后序遍历

    第三次遇到该结点时输出

    	public static void postOrder(TreeNode root){
    		if(root==null) return;
    		TreeNode p = root,lastVisted = root;
    		Stack<TreeNode> stack = new Stack<>();
    		boolean alreadyPushed = false;
    		while(!stack.isEmpty()||p!=null){
    			//根据alreadyPushed判断右子树是否已经被压入栈过
    			if(!alreadyPushed){
    				while(p!=null){		//未被压入栈过,则依次入栈
    					stack.push(p);
    					p = p.left;
    				}
    			}
    			
    			//后序遍历是第三次遇到该结点的时候输出,只有两种情况:
    			//①该结点的右孩子为空(这里也看作第二次遇到后,先去了空的右孩子,再回头,所以是第三次遇到)
    			//②该结点的右孩子已经访问过了(还可以肯定的是,被访问过的右孩子一定就是上一次访问的结点)
    			if(!stack.isEmpty()){
    				p = stack.pop();	//可能是第二或第三次遇到,要做进一步判断
    				if(p.right==null||p.right==lastVisted){		//第三次遇到:①右孩子为空||②上一次访问的结点是它的右孩子
    					System.out.print(p.val + " ");
    					lastVisted = p;		//更新上一个访问的结点
    					p = null;	//必须设空,否则最外层循环条件p!=null可能永远无法满足
    					alreadyPushed = true;	//右孩子已经访问过了(已被压入栈过),不需要再进入右孩子
    				}else{
    					stack.push(p);		//说明右孩子还没访问过,将该结点再次入栈
    					p = p.right;		//右孩子还没有访问过(未被压入栈过),先进入右孩子
    					alreadyPushed = false;
    				}
    			}
    		}
    	}
    
    展开全文
  •  后序遍历的非递归算法。思路参考来自这里。思路是当当前结点没有左孩子或右孩子或左孩子和右孩子已经被访问的情况下,访问该结点。 具体思路如下: 当前结点左子树不为空且左孩子和右孩子没有被访问过的情况下,...

    算法思路

            后序遍历的非递归算法。思路参考来自这里。思路是当当前结点没有左孩子或右孩子或左孩子和右孩子已经被访问的情况下,访问该结点。 具体思路如下:

    1. 当前结点左子树不为空且左孩子和右孩子没有被访问过的情况下,不断入栈左子树;
    2. 左子树访问结束,判断当前结点是否有右孩子且右孩子没有访问过的情况下,入栈右孩子,回到步骤1;
    3. 当最后一个右孩子被访问到时,开始出栈,并记录上一次 范围的结点。

    算法实现

    void PostOrder(BiTree T){	//入栈所有的左子树以及左子树的右子树直到没有可以访问的右子树后退栈。 
    	BiTNode *pre = T;	//记录上一次退栈的结点 
    	BiTNode *p=T;		//当前访问结点 
    	BiStack s ;             //保存结点用的栈
    	s.top=0;                //栈底预留,用于保存NULL结束算法。
    	s.data[s.top]=NULL;
    	while(p||s.top!=0){
    		if(p!=NULL&&pre!=p->lchild&&pre!=p->rchild){	//结点不为空且左孩子和右孩子没有访问过 ,入栈左子树 
    			s.data[++s.top]=p;
    			p=p->lchild;
    		}
    		else{					
    			p=s.data[s.top];						 
    			if(p->rchild!=NULL&&pre!=p->rchild){	//右子树不为空且右孩子没有访问过,入栈右子树结点 
    				p=p->rchild;
    			}
    			else{
    				printf("%d ",p->data);		//访问到最后的右子树的结点后,退栈。 
    				pre=s.data[s.top];
    				p=s.data[--s.top];
    			}
    		}
    	}
    }

    C编程实现

    #include<stdio.h>
    
    typedef struct BiTNode{
    	int data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    typedef struct{
    	BiTree data[100];
    	int top;
    }BiStack;
    
    void PostOrder(BiTree T);
    
    int main(){
    	BiTNode a,b,c,d,e,f,g;        //简单的测试数据
    	a.data=1;
    	b.data=2;
    	c.data=3;
    	d.data=4;
    	e.data=5;
    	f.data=6;
    	g.data=7;
    	a.lchild=&b;
    	a.rchild=&g;
    	b.lchild=&c;
    	b.rchild=NULL;
    	c.lchild=&d;
    	c.rchild=&e;
    	d.lchild=NULL;
    	d.rchild=NULL;
    	e.lchild=NULL;
    	e.rchild=&f;
    	f.lchild=NULL;
    	f.rchild=NULL;
    	g.lchild=NULL;
    	g.rchild=NULL;
    	
    	
    	PostOrder(&a);
    	
    	return 0;
    }
    
    void PostOrder(BiTree T){	//入栈所有的左子树以及左子树的右子树直到没有可以访问的右子树后退栈。 
    	BiTNode *pre = T;		//记录上一次退栈的结点 
    	BiTNode *p=T;			//当前访问结点 
    	BiStack s ;
    	s.top=0;
    	s.data[s.top]=NULL;
    	while(p||s.top!=0){
    		if(p!=NULL&&pre!=p->lchild&&pre!=p->rchild){	//结点不为空且左孩子和右孩子没有访问过 ,入栈左子树 
    			s.data[++s.top]=p;
    			p=p->lchild;
    		}
    		else{					
    			p=s.data[s.top];						 
    			if(p->rchild!=NULL&&pre!=p->rchild){	//右子树不为空且右孩子没有访问过,入栈右子树结点 
    				p=p->rchild;
    			}
    			else{
    				printf("%d ",p->data);			//访问到最后的右子树的结点后,退栈。 
    				pre=s.data[s.top];
    				p=s.data[--s.top];
    			}
    		}
    	}
    }

     

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

    千次阅读 2018-11-16 21:44:03
    void PostOrder2(BiTree T) { InitStack(S); BiTree p=T; BiTree r=NULL; while(p||!...//记录最近出栈结点 ...//该结点左右子树都已出栈,所以要继续出栈,访问其父结点 } } } }  
    void PostOrder2(BiTree T)
    {    
        InitStack(S);
        BiTree p=T;
        BiTree r=NULL;
        while(p||!IsEmpty(S))
        {
            if(p)
            {
                Push(S,p);
                p=p->lchild;
            }
            else
            {
                p=GetTop(S);//先不出栈,满足条件再出栈访问
                if(p->right && p->right!=r)
                    p=p->right;
                else//满足该结点没有右子树 或者 右儿子刚出栈,则出栈访问
                {
                    p=Pop(S);
                    visit(p);
                    r=p;//记录最近出栈的结点
                    p=NULL;//该结点的左右子树都已出栈,所以要继续出栈,访问其父结点
                }
            }
        }
    }
        

     

    展开全文
  • 设计并实现基于后序线索二叉树的后序遍历的非递归算法。 一、二叉树的创建 我们使用二叉链表得方式进行二叉树存数。每个结构有一个数据域,存放结点的数据,还有两个左右指针,以及两个标志。当标志为0时表示指向...
  • 二叉排序树的前中后序遍历的非递归算法 一棵树若为二叉排序树,需要满足以下条件: 为空树或者是二叉树 如果左子树不空,则左子树上所有节点的值都小于根节点的值。 如果右子树不空,则右子树上所有节点的值都大于...
  • 主要是前3种遍历的非递归写法。我们知道,用递归写这三种遍历是很简单也很容易理解的,但是非递归算法却有点难度,研究非递归的算法会加深我们对这一问题的理解。那么该怎么写非递归的程序呢,对于这个问题,我们...
  • 在二叉树的后序遍历的非递归算法(一)中使用的是一个堆栈,且加了一个额外的信息来说明右孩子是否已经访问 下面是使用两个堆栈来实现后序遍历的非递归算法,理解起来比第一个算法要好理解: ////////////////////...
  • 二叉树后序遍历的非递归算法

    千次阅读 2016-04-16 16:47:33
    二叉树的后续遍历的非递归算法与二叉树的先序和中序遍历的非递归算法相比稍微复杂一点。 大致思路是:如果当前结点左右子树均为空,则可以访问当前结点,或者左右子树不均为空,但是前一个访问的结点是当前结点的左...
  • 注:本文截图来自文都考研洪...补上先序遍历的非递归算法(C++): /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) ...
  • 首先非常感谢‘hicjiajia’博文:二叉树后序遍历(非递归) 这篇随笔开启我博客进程,成为万千程序员中一员,坚持走到更远! 折磨了我一下午的后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过...
  • 二叉树的前序建立递归算法以及前中后序遍历的递归...然而,有时我们也确实需要它们的非递归算法。将递归算法转化为非递归算法可以帮助我们深入了解函数的调用与栈的原理。这里总结一下二叉树的这些重要的非递归算法
  • 先序遍历:若二叉树为空,则空操作;...后序遍历:若二叉树为空,则空操作;否则后序遍历左子树;后序遍历右子树;访问根节点。/* * Created by Microsoft Visual Studio 2013 * @author: Teresa * @date: 20
  • 题目描述输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析所谓二叉搜索树,也称为二叉搜索树、有序二叉树(ordered ...
  • Binary Tree Postorder Traversal思路一:使用一个栈stack保存经过根结点,另一个栈flag保存每个结点右子树是否遍历;如果根结点存在,结点入栈,并把结点右子树遍历结果置为0,代表没遍历;把root指向左子树...
  • 二叉树各种非递归遍历中,要数后序比较麻烦了,因为即使左子树为空,也不能马上出栈,而是要判断右子树。以下就给出代码: typedef struct Tnode{ ElemType data; struct Tnode *lchild,*rchild;}BBTnode,*BBTree...
  • //非递归实现中序遍历 stack<BiTree*> bs; void preOrderTraversal(BiTree* t) { BiTree *p=t; while (p||!bs.empty()) { if (p) { bs.push(p); p=p->lc; } else { p=bs.top(); bs.pop...
  • 二叉树先序遍历的实现思想是:访问根节点;访问当前节点的左子树;若当前节点无左子树,则访问当前节点的右子树;图 1 二叉树以图 1 为例,采用先序遍历的思想遍历该二叉树的过程为:访问该二叉树的根节点,找到 1;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,630
精华内容 652
关键字:

后序遍历的非递归算法