精华内容
下载资源
问答
  • int NInorderTraverse(BiTree &Tint*visit(char e) { InitStack(S;...StackEmpty(S)//在不空情况下 { while(GetTop(S,p&p) Push(S,p->lchild;//向左走到头 Pop(S,p;//空指针退栈 if!StackEmpty(S) { Pop(S,p;
  • 二叉树中序遍历非递归算法

    万次阅读 多人点赞 2019-01-10 14:10:41
    *非递归算法思想:  (1)设置一个栈S存放所经过根结点(指针)信息;初始化S;  (2)第一次访问到根结点并不访问,而是入栈;  (3)中序遍历左子树,左子树遍历结束后,第二次遇到根结点,就将根结点...

    *非递归算法思想:

       (1)设置一个栈S存放所经过的根结点(指针)信息;初始化S;

      (2)第一次访问到根结点并不访问,而是入栈;

       (3)中序遍历它的左子树,左子树遍历结束后,第二次遇到根结点,就将根结点(指针)退栈,并且访问根结点;然后中序遍历它的右子树。

      (4) 当需要退栈时,如果栈为空则结束。

     

     

     

     

     

    代码实现:

    void Midorder(struct BiTNode *t)      //t为根指针 
    { struct BiTNode *st[maxleng];//定义指针栈
      int top=0;                  //置空栈
      do{            
        while(t)               //根指针t表示的为非空二叉树 
        { if (top==maxleng) exit(OVERFLOW);//栈已满,退出
          st[top++]=t;             //根指针进栈
          t=t->lchild;             //t移向左子树
         }   //循环结束表示以栈顶元素的指向为根结点的二叉树
             //的左子树遍历结束
        if (top)                    //为非空栈   
        { t=st[--top];             //弹出根指针
          printf("%c",t->data);    //访问根结点
          t=t->rchild;             //遍历右子树
         }
       } while(top||t); //父结点未访问,或右子树未遍历
     }
    

     

     

    依照同样的思维,写的先序遍历非递归模式

    void Preorder(struct BiTNode * t){
      struct BiTNode * St[MaxSize], *p;
      int top = 0; 			//置空栈
      if (t! = NULL){
    	  St[top++] = t;
        while(top){
    	   p = St[--top]; printf("%c ", p->data);
    	   if(p->rchild != NULL)
    	      St[top++] = p->rchild;
    	   if(p->lchild != NULL)
    	      St[top++] = p->lchild;
        }
        printf("\n");
      }
    }

     

    后序遍历

    void Postorder(struct BiTNode * t){
      struct BiTNode * St[MaxSize], *pre;
      int flag, top = 0;
      if (t != NULL){
    	  do{
    		 while(t != NULL){
    		   St[top++] = t; t = t->lchild;
            }
    		 pre = NULL; flag = 1;
    		 while(top && flag){
              t = St[top-1];
    		   if(t->rchild == pre){
    		   	printf(“%c ”, t->data); top--;  pre = t;
    		   }
    		   else{ t=t->rchild; flag = 0;}
    	     }
    	   }while(top);
    	  printf(“\n”); 
    	}
    }
    

     

    展开全文
  • 表示出这颗后在调用二叉树中序遍历非递归算法 */ #include <iostream> using namespace std; # define maxSize 10 //结点结构体,存储是int整型数据 typedef struct BTNode{ int
    /*
    	二叉树的中序遍历非递归算法
    	目标遍历的二叉树:
    		 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;
    }
    
    
    展开全文
  • 二叉树后序遍历非递归算法

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

    1. 对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用的方法是深度优先遍历树的每一个节点,这些遍历方法都是使用递归函数来进行实现的,在数据量大的情况下是比较低效的,原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作,才使得遍历可以使用非常简单的代码来实现,所以我们可以模仿系统中调用的栈自己可以来写一下栈,模仿其中的过程就可以完成对于三种遍历算法的实现,使用自定义的栈来代替系统栈可以得到效率上的提升,下面是对于后序遍历的非递归算法的实现

    2. 首先模仿这个系统栈我们需要清楚的是系统栈为我们做了什么事情,下面以一棵二叉树为例来模仿其中的节点入栈与出栈的过程

    创建的二叉树如下:

     

    后序遍历为:5 3 2 4 1

    先序遍历为:1 2 5 3 4

    逆后序遍历为:1 4 2 3 5

    从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的,所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了,所以需要两个栈,第一个栈用来存储先序遍历交换左右子树的遍历的中介结果,第二个是存储后序遍历的结果(逆序也就是可以理解为先进后出的意思)

    下面是模仿元素进栈与出栈的过程:

    ① 1节点进栈,在循环中弹出1节点压入到第二个栈中,发现左右节点不为空那么将左右节点压入栈1,这个与先序遍历中将左右子树压入到栈顶的顺序是相反的

    ② 弹出4节点压入到第二个栈中,发现左右孩子都为空那么不进行任何的操作

    ③ 弹出2节点压入到第二个栈中,发现左右节点不为空那么将左右节点压入到栈1中

    ④ 弹出3节点压入到第二个栈中,发现左右孩子都为空不进行任何操作

    ⑤ 弹出5节点压入到第二个栈中,发现左右孩子都为空不进行任何操作

    最后栈为空那么退出循环结束

    3. 具体的代码如下:

    import java.util.Stack;
    public class Main {
    	public static void main(String[] args) {
    		TreeNode<Integer> root = new TreeNode<Integer>(1);
    		TreeNode<Integer> l = new TreeNode<Integer>(2);
    		TreeNode<Integer> r = new TreeNode<Integer>(4);
    		TreeNode<Integer> ll = new TreeNode<Integer>(5);
    		TreeNode<Integer> lr = new TreeNode<Integer>(3);
    		root.left = l;
    		root.right = r;
    		l.left = ll;
    		l.right = lr;
    		postOrder(root);
    	}
    	
    	@SuppressWarnings({ "rawtypes", "unchecked" })
    	private static void postOrder(TreeNode<Integer> root) {
    		Stack<TreeNode> src = new Stack<TreeNode>();
    		Stack<TreeNode> res = new Stack<TreeNode>();
    		src.push(root);
    		while(!src.isEmpty()){
    			TreeNode<Integer> p = src.pop();
    			res.push(p);
    			if(p.left != null){
    				src.push(p.left);
    			}
    			if(p.right != null){
    				src.push(p.right);
    			}
    		}
    		//输出最终后序遍历的结果
    		while(!res.isEmpty()){
    			System.out.print(res.pop().val + " ");
    		}	
    	}
    
    	public static class TreeNode<T>{
    		T val;
    		TreeNode<T> left;
    		TreeNode <T> right;
    		public TreeNode(T val) {
    			super();
    			this.val = val;
    		}
    	}
    }
    

     

    展开全文
  • DS二叉树–后序遍历非递归算法 题目描述 求一颗树的后序遍历的非递归算法 要求:必须是非递归算法,使用堆栈对象来实现 建树方法采用“先序遍历+空树用0表示”的方法 算法流程: 输入 第一行输入一个整数t,表示有t...

    DS二叉树–后序遍历非递归算法

    题目描述

    求一颗树的后序遍历的非递归算法
    要求:必须是非递归算法,使用堆栈对象来实现
    建树方法采用“先序遍历+空树用0表示”的方法
    算法流程:
    在这里插入图片描述

    输入

    第一行输入一个整数t,表示有t个测试数据

    第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

    输出

    逐行输出每个二叉树的后序遍历结果

    样例输入

    3
    AB0C00D00
    ABC00D00EF000
    ABCD0000E0F00

    样例输出

    CBDA
    CDBFEA
    DCBFEA

    #include <iostream>
    #include <stack>
    using namespace std;
    
    class BiNode{
        char data;
        int tag;
        BiNode *lChild;
        BiNode *rChild;
        BiNode():lChild(NULL),rChild(NULL){}
        BiNode(char e):data(e),lChild(NULL),rChild(NULL){}
        friend class BiTree;
    };
    
    class BiTree{
        BiNode *root;
        void createTree(BiNode *&r);
    public:
        BiTree():root(NULL){}
        void createTree();
        void postOrder();
    };
    
    void BiTree::createTree(BiNode *&r) {
        char ch;
        cin>>ch;
        if(ch != '0')
        {
            r = new BiNode(ch);
            createTree(r->lChild);
            createTree(r->rChild);
        }
        else
            r = NULL;
    }
    
    void BiTree::createTree() {
        createTree(root);
    }
    
    void BiTree::postOrder() {
        stack<BiNode*> s1;
        stack<int> s2;
        if(!root)
            return;
        BiNode *p=root;
        do{
            while (p) {
                s1.push(p);
                s2.push(p->tag);
                p = p->lChild;
                if(s1.empty())
                    break;
            }
            if(!p)
            {
                int tag=s2.top();
                if(tag == 0)
                {
                    s2.top()=1;
                    p=s1.top()->rChild;
                }
                else if(tag==1)
                {
                    p=s1.top();
                    s1.pop();
                    s2.pop();
                    cout<<p->data;
                    p=NULL;
                }
            }
    
    
        }while (!s1.empty());
    
        cout<<endl;
    }
    
    
    int main()
    {
        int t;
        cin>>t;
        while (t--)
        {
            BiTree myTree;
            myTree.createTree();
            myTree.postOrder();
        }
        return 0;
    }
    
    展开全文
  • 二叉树前序遍历非递归算法

    千次阅读 2019-06-03 11:06:10
    1. 对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用的方法是深度优先遍历树的每一个节点,这些遍历方法都是使用递归函数来进行实现的,在数据量大的情况下是比较低效的,原因在于...
  • 【写在前面】 二叉树是一种非常重要的...而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历 中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍...
  • 递归遍历算法比较简单,因为二叉树本身建立也是通过递归进行建立。所以二叉树子树也是二叉树,根据这个思想,遍历算法如下: 1)访问二叉树左子树 2)访问根节点 3)访问二叉树右子 伪代码如下: mid_...
  • void inOrder(BiTree T,visit func){stack > s;BiNodePtr p=T,q=NULL;if(!p)return;while(p){s.push(p);p=p->l;}while(!s.empty()){p=s.top();s.pop();func(p);q=p->r;while(q){s.push(q);q=q
  • 中序 遍历的几种情况分析1:什么时候访问根、什么时候访问左子树、什么访问右子 当左子树为空或者左子树已经访问完毕以后,再访问根 访问完毕根以后,再访问右子。分析2:为什么是栈,而不是其他队列。 先走...
  • 中序遍历非递归遍历算法 遇到一个结点,就把它压栈,并去遍历它左子树; 当左子树遍历结束后,从栈顶弹出这个结点并访问它; 然后按其右指针再去中序遍历该结点右子。 伪码如下: void InOrderTraversal( ...
  • 二叉树三种遍历非递归算法

    千次阅读 2018-10-11 16:27:20
    二叉树先序遍历顺序为:根左右(NLR),即先遍历根节点,再遍历左子树,最后遍历右子。 using namespace std; void PreorderTraversal(TreeNode BT) { TreeNode T; stack&lt;TreeNode&gt; BtStack; ...
  • #include <iostream> #include <stack> using namespace std; typedef struct TreeNode* BinTree; //typedef BinTree Position;.../*以前序遍历的形式输入来创建*/ void CreatBinTree(Bin...
  • 求一颗树的后序遍历非递归算法 要求:必须是非递归算法,使用堆栈对象来实现 建树方法采用“先序遍历+空树用0表示”的方法 算法流程: 输入 第一行输入一个整数t,表示有t个测试数据 第二行起输入二叉树...
  • 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子...
  • 首先是二叉树数据结构定义: typedef struct TNode *Position; ...struct TNode{ /* 结点定义 */ int Data; /* 结点数据 */ BinTree Left; /* 指向左子树 */ BinTree Right; /* 指向右...
  •  后序遍历的非递归算法。思路参考来自这里。思路是当当前结点没有左孩子或右孩子或左孩子和右孩子已经被访问情况下,访问该结点。 具体思路如下: 当前结点左子树不为空且左孩子和右孩子没有被访问过情况下,...
  • void preOrderRecursive(TreeNode* tree){//前序递归算法 if(tree==null) return; visit(tree->value); preOrderRecursive(tree->left); preOrderRecursive(tree->right); } void preOrderNoRecursive
  • 先序遍历右子。 中序遍历:若二叉树为空,则空操作;否则中序遍历左子树;访问根节点;中序遍历右子。 后序遍历:若二叉树为空,则空操作;否则后序遍历左子树;后序遍历右子;访问根节点。 二叉链表:链表...
  • 二叉树具有一些特定性质,如 n0 = n2+1,在一些应用中,常常要求在中查找具有某些特征节点,或者对中节点进行处理,即遍历二叉树问题,其递归算法非常容易实现,非递归算法也有两种思路,本文将在程序中...
  • 1.先序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack;void PreOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=...
  • 二叉树的遍历主要有三种:前序遍历、中序遍历、后序遍历 下面以遍历下颗为例: 前序遍历:-+a*b-cd/ef 中序遍历:a+b*c-d-e/f 后序遍历:abcd-*+ef/- 递归实现 public: //前序遍历 ... //递归算法 p
  • 按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法,其中“序”指的是根结点在何时被访问。 先序遍历  先序遍历(PreOrder)的操作过程如下: ...
  • 算法列表 递归算法: ... 非递归算法 中序遍历 先序遍历 //先序遍历二叉树 bool PreOrder(PBitNode B) { if (B != NULL) { printf("%d ", B->da...
  • 用图形的方式来表现二叉树的结构,非常直观,也容易理解。但是,对于计算机来说,只能处理线性序列,因此需要通过遍历将中的结点变成某种意义的...可以通过递归和迭代来实现二叉树各种次序的遍历,  迭代有两方法:
  • 中序非递归遍历算法: 遇到一个节点,就把它压栈,并去遍历左子树; 当左子树遍历结束后,从栈顶弹出这个节点并访问它; 然后按其右指针再去中序遍历该节点右子。 中序非递归遍历代码: 1 void ...
  • 二叉树后序遍历非递归算法(有问题) 分析: a(flag=1),只遍历完左子树,右子尚未遍历,则该结点不出栈,利用栈顶结点找到它右子,准备遍历 b(flag=2),遍历完右子,将该结点出栈,并访问它 */ struct ...
  • 主要介绍了JavaScript实现多叉树的递归遍历非递归遍历算法,结合实例形式详细分析了JavaScript多叉树针对json节点的递归与非递归遍历相关操作技巧,需要的朋友可以参考下

空空如也

空空如也

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

树的遍历非递归算法