精华内容
下载资源
问答
  • 中序遍历非递归算法

    万次阅读 2018-05-15 11:00:24
    中序遍历: 方法一: //中序遍历 void InOrderWithoutRecursion1(BTNode* root) { //空树 if (root == NULL) return; //树非空 BTNode* p = root; stack<btnode*> s; while (!s.empty() || p...

    中序遍历:

    方法一:

    //中序遍历
    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;
            }
        }
    }</btnode*>

    方法二:

    //中序遍历
    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;
            }
        }
    }</btnode*>

    方法三:

    public void InOrderWithoutRecursion(TreeNode T){  
              
            Stack<TreeNode> stack = new Stack<TreeNode>();  
            TreeNode p;  
            while(T!=null||!stack.empty()){  
                  
                while(T!=null){             //将结点压进栈中  
                    stack.push(T);  
                    T = T.lchild;  
                }  
                  
                if(!stack.empty()){         //将栈中的结点弹出  
                    p = stack.peek();    
                    stack.pop();  
                    System.out.println(p.data);                   
                    T = p.rchild;             
                }  
            }  
                      
        }  

     

    展开全文
  • 中序遍历非递归算法 1)后置订单算法 (1) Algorithm for Postorder) In this traversal first, traverse the leftmost subtree at the external node then visit the root node and lastly traverse the right ...

    树中序遍历非递归算法

    1)后置订单算法 (1) Algorithm for Postorder)

    In this traversal first, traverse the leftmost subtree at the external node then visit the root node and lastly traverse the right subtree starting at the left external node.

    在此遍历中,首先遍历外部节点上最左侧的子树,然后访问根节点,最后遍历从左侧外部节点开始的右侧子树。

    POSTORD(INFO, LEFT, RIGHT, ROOT)
    Step-1 [Push NULL onto STACK and initialize PTR]
       Set TOP=1, STACK[1]=NULL and PTR=ROOT.
    
    Step-2 [Push left-most path onto STACK] repeat step 3 to 5 while PTR not equal NULL.
    
    Step-3 set TOP=TOP+1 and STACK[TOP]=PTR. [Pushes PTR on STACK].
    
    Step-4 if RIGHT[PTR] not equal NULL then [push on STACK.]
       Set TOP=TOP+1 and STACK[TOP]= RIGHT[PTR]
      [End of if structure]
    
    Step-5 set PTR = LEFT[PTR].[Update pointer PTR]
        [End of step 2 loop].
    
    Step-6 set PTR= STACK[TOP] and TOP=TOP-1.
      [Pops node from STACK].
    
    Step-7 Repeat while PTR>0;
      Apply PROCESS TO INFO[PTR].
    Set PTR= STACK[TOP] and TOP= TOP-1.
    [Pops node from STACK]
    [End of loop]
    
    Step-8 if PTR<0 then:
       Set PTR= -PTR
    Go to step 2
    [End of if structure]
    
    Step-9 Exit.
    
    

    2)排序算法 (2) Algorithm for Inorder)

    In this traversal first traverse, the root node then traverses the left subtree of the external node and lastly traverse the right subtree of the external node.

    在此遍历中,根节点然后遍历外部节点的左子树,最后遍历外部节点的右子树。

    INORD( INFO, LEFT, RIGHT, ROOT)
    Step-1 [Push NULL onto STACK and initialize PTR;]
        Set TOP=1 STACK[1]= NULL and PTR=ROOT.
    
    Step-2 Repeat while PTR not equal NULL[Pushes left most path onto STACK].
    a)	Set TOP=TOP+1 and STACK[TOP]=PTR [saves node]
    b)	Set PTR=LEFT[PTR] [updates PTR]
    [End of loop]
    
    Step-3  set PTR= STACK[TOP and TOP=TOP-1.[pops node from STACK].
    
    Step-4 Repeat step 5 to 7 while PTR is not equal to Null; [backtracking].
    
    Step-5 Apply PROCESS to INFO[PTR],
    
    Step-6 [RIGHT child?] if RIGHT[PTR] is not equal NULL then.
    a)	Set PTR=RIGHT[PTR]
    b)	Go to step 3.[End of if structure.]
    
    Step-7 set PTR= STACK[TOP] and TOP=TOP-1. [pops node]
    [End of step 4 loop]
    
    Step-8 Exit.
    
    

    3)预购算法 (3) Algorithm for Preorder)

    In this traversal first, traverse all the left external node starting with the leftmost subtree which is then followed by bubble-up all the external node and then traverse the right subtree starting at the left external node which is the followed by bubble-up all the internal nodes and lastly visit the root node.

    在此遍历中,首先遍历所有左外部节点,从最左边的子树开始,然后遍历所有外部节点,然后遍历右子树,从左侧外部节点开始,随后遍历所有内部节点,最后访问根节点。

    PREORDER(  INFO, LEFT,RIGHT, ROOT)
    Step-1 [initially push NULL onto stack and initialize PTR.]
      Set TOP=1 STACK[1]=NULL and PTR= ROOT.
    
    Step-2 Repeat step 3 to 5 while PTR not equal NULL.
    
    Step-3 Apply PROCESS to INFO[PTR].
    
    Step-4 [RIGHT child?]
      If RIGHT[PTR] not equal NULL then [PUSH on STACK]
     Set TOP= TOP+1 and STACK[TOP]= RIGHT[PTR]
    [End of if structure.]
    
    Step-5 [LEFT child?]
       If LEFT[PTR] not equal NULL then
      Set PTR= LEFT[PTR].
      Else [pop from STACK;]
    Set PTR= STACK[TOP] and TOP=TOP+!;
    [End of if structure]
    [End of step 2 loop]
    
    Step-6 Exit.
    
    
    

    翻译自: https://www.includehelp.com/algorithms/non-recursive-tree-traversal-algorithm.aspx

    树中序遍历非递归算法

    展开全文
  • 二叉树的中序遍历非递归算法 目标遍历的二叉树: 1 / \ 2 4 / \ 3 5 待输出结果为3,2,5,1,4 1.首先得用上面定义的结构体把这颗树表示出来 2.表示出这颗树后在调用二叉树的中序遍历非递归算法 */...
    /*
    	二叉树的中序遍历非递归算法
    	目标遍历的二叉树:
    		 1
    		/ \
    	   2   4
    	  / \
    	 3   5	
    	待输出结果为3,2,5,1,4
    	1.首先得用上面定义的结构体把这颗树表示出来
    	2.表示出这颗树后在调用二叉树的中序遍历非递归算法
    */
    

    在这里插入图片描述

    #include <iostream>
    using namespace std;
    # define maxSize 10
    //树结点的结构体,存储的是int整型的数据
    typedef struct BTNode{
    	int data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    
    /*
    	二叉树的中序遍历非递归算法
    	目标遍历的二叉树:
    		 1
    		/ \
    	   2   4
    	  / \
    	 3   5	
    	待输出结果为3,2,5,1,4
    	1.首先得用上面定义的结构体把这颗树表示出来
    	2.表示出这颗树后在调用二叉树的中序遍历非递归算法
    */
    
    void createBTree(BTNode *&p)
    {	
    	/*
    		生成这颗树,这里就是直接按照二叉树的样子来逐一生成
    		p做为根结点(root)
    	*/
    	p = (BTNode*)malloc(sizeof(BTNode));
    	p->data = 1;
    	BTNode *n2, *n3, *n4, *n5 ;//分别对应存储元素2,3,4,5的4个结点
    	n2 = (BTNode*)malloc(sizeof(BTNode));
    	n3 = (BTNode*)malloc(sizeof(BTNode));
    	n4 = (BTNode*)malloc(sizeof(BTNode));
    	n5 = (BTNode*)malloc(sizeof(BTNode));
    	n2->data = 2;
    	n3->data = 4;
    	n4->data = 3;
    	n5->data = 5;
    	p->lchild = n2;
    	p->rchild = n3;
    	n2->lchild = n4;
    	n2->rchild = n5;
    	n3->lchild = n3->rchild = NULL;
    	n4->lchild = n4->rchild = NULL;
    	n5->lchild = n5->rchild = NULL;
    }
    void inorderNonrecursion(BTNode *p){
    	
    	if (p != NULL){
    		BTNode *q;
    		BTNode *stack[maxSize];			//定义一个栈
    		int top = -1;					//初始栈
    		
    		q = p;
    		while (top != -1 || q != NULL)
    		{
    			while (q != NULL)
    			{
    				stack[++top] = q;
    				q = q->lchild;
    			}
    			
    			if (top != -1)
    			{
    				q = stack[top--];
    				cout << q->data << endl;
    				q = q->rchild;
    			}
    		}
    
    	}
    }
    
    int main()
    {
        BTNode *p;
    	createBTree(p);
    	inorderNonrecursion(p);
        return 0;
    }
    
    
    展开全文
  • 利用栈的基本操作实现二叉树的中序遍历非递归算法
  • 1.先序遍历非递归算法voidPreOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL||!StackEmpty(s)){while(p!=NULL)//遍历左子树{visite(p->data);push(s,p);p=p->lchild;}if(!StackEmpty(s))...

    1.先序遍历非递归算法

    voidPreOrderUnrec(Bitree *t)

    {

    Stack s;

    StackInit(s);

    Bitree *p=t;

    while(p!=NULL || !StackEmpty(s))

    {

    while(p!=NULL)//遍历左子树

    {

    visite(p->data);

    push(s,p);

    p=p->lchild;

    }

    if(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历

    {

    p=pop(s);

    p=p->rchild;

    }//endif

    }//endwhile

    }void PreOrderUnrec(Bitree *t)

    {

    Stack s;

    StackInit(s);

    Bitree *p=t;

    while (p!=NULL || !StackEmpty(s))

    {

    while (p!=NULL) //遍历左子树

    {

    visite(p->data);

    push(s,p);

    p=p->lchild;

    }

    if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历

    {

    p=pop(s);

    p=p->rchild;

    }//endif

    }//endwhile

    }

    2.中序遍历非递归算法

    voidInOrderUnrec(Bitree *t)

    {

    Stack s;

    StackInit(s);

    Bitree *p=t;

    while(p!=NULL || !StackEmpty(s))

    {

    while(p!=NULL)//遍历左子树

    {

    push(s,p);

    p=p->lchild;

    }

    if(!StackEmpty(s))

    {

    p=pop(s);

    visite(p->data);//访问根结点

    p=p->rchild;//通过下一次循环实现右子树遍历

    }//endif

    }//endwhile

    }void InOrderUnrec(Bitree *t)

    {

    Stack s;

    StackInit(s);

    Bitree *p=t;

    while (p!=NULL || !StackEmpty(s))

    {

    while (p!=NULL) //遍历左子树

    {

    push(s,p);

    p=p->lchild;

    }

    if (!StackEmpty(s))

    {

    p=pop(s);

    visite(p->data); //访问根结点

    p=p->rchild; //通过下一次循环实现右子树遍历

    }//endif

    }//endwhile

    }

    posted on 2013-11-20 11:02 ** 阅读(105) 评论(0)  编辑  收藏

    展开全文
  • * 二叉树中序遍历非递归算法。 * 主要思路: * 用一个栈维护所有有左孩子的节点。 * 1、当一个节点有左孩子时,就把这个节点进栈。 * 2、然后检查这个节点的左孩子节点是不是有左孩子,如果有,则这个左...
  • 二叉树前序遍历和中序遍历 非递归算法 #include #include #define MAX 100 struct BSTreeNode { int value; struct BSTreeNode *left; struct BSTreeNode *right; }; struct stack { struct ...
  • int NInorderTraverse(BiTree &Tint*visit(char e) { InitStack(S; Push(S,T;//根指针入栈 while!StackEmpty(S)//在树不空的情况下 { while(GetTop(S,p&p) Push(S,p->lchild;//向左走到头 Pop(S,p;...
  • 二叉树中序遍历非递归算法详解

    千次阅读 2013-04-25 14:36:04
    二叉树中序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的中序遍历的特性,该二叉树中序遍历顺序为:DBGEACHFI; 2. 一般遍历一颗二叉树,先序中序或者后序,...
  • 二叉链表中序遍历非递归算法

    千次阅读 2017-12-11 16:43:46
    过程初始指针指向根节点。1. 若此节点不为空,此节点入栈。2. 指针指向此节点的左孩子。3. 若此节点为空,指针指向...图示算法实现C语言实现核心代码void InOrderTraverse(BiTree T) { BiTree p = T;//二叉树遍历
  • 二叉树具有一些特定的性质,如 n0 = n2+1,在一些应用中,常常要求在树中查找具有某些特征的节点,或者对树中节点进行处理,即遍历二叉树的问题,其递归算法非常容易实现,非递归算法也有两种思路,本文将在程序中...
  • 二叉树中序遍历的非递归算法同样可以使用栈来实现,从根结点开始,将根结点的最左结点全部压栈,当...二叉树中序遍历非递归算法如下: struct TreeNode { int val; TreeNode *left; TreeNode * right; ...
  • 前序遍历 中序遍历 递归与非递归算法实现 前序遍历递归算法 public void preorder(TreeNode root){ if(root==null) return;...前序遍历非递归算法 public void preorder(TreeNode root){ if(ro
  • 二叉树中序遍历的非递归算法同样可以使用栈来实现,从根结点开始,将根结点的最左结点全部... 二叉树中序遍历非递归算法实现如下: #include <stdlib.h> #include <stdio.h> #define MAXSIZE 1...
  • 小小学习,C语言数据结构,中序遍历二叉树非递归算法
  • 用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
  • 中序遍历非递归算法 C语言数据结构中序遍历非递归算法
  • 中序遍历非递归算法(C语言版)

    千次阅读 2015-11-30 21:39:34
    #include #include ...//前序遍历:ABD#E##FG###C## typedef struct tree/*二叉树*/ { char data;  struct tree *lchild,*rchild; }bintree; typedef bintree *tree; tree createTree()/*前序遍历建树*
  • 用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法
  • 中序遍历的特点“左-根-右”,访问完一个节点之后,立刻转到其右子节点递归处理。 特别注意外层while循环的条件。 /* 二叉树节点结构 */ struct BinaryTreeNode { int data; BinaryTreeNode* lchild; ...
  • 二叉树的递归遍历算法很简单,而非递归遍历算法中的先序和中序遍历相比于后序遍历更简单一点,在这先实现先序和中序遍历非递归算法。 先序遍历代码如下: public static void preOrder(TreeNode root) { ...
  • 二叉树中序遍历非递归算法

    千次阅读 2016-05-04 15:33:04
    用栈实现二叉树中序遍历非递归算法
  • 昨天写的前序遍历的递归与非递归算法,在非递归算法中主要还是借用到了栈这一工具,其实在中序遍历和后序遍历中依旧可以理由栈的特性来进行非递归的遍历 操作。 1.中序遍历 1.1 中序遍历的递归算法 二叉树的构造以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,744
精华内容 8,697
关键字:

中序遍历非递归算法