精华内容
下载资源
问答
  • 用递归先序算法建立二叉树。要求通过键盘输入二叉树的先序遍历顺序从而建立一棵二叉树。利用实现一棵二叉树的中序非递归遍历。要求显示遍历次序。
  • package tree; public class InorderTree ... * 不带的二叉树中序非递归遍历 * 1. Initialize current as root 2. While current is not NULL If current does not have left child a) Print current’s data
    package tree;
    
    public class InorderTree {
    
    	/**
    	 * 不带栈的二叉树中序非递归遍历
    	 * 1. Initialize current as root 
    2. While current is not NULL
       If current does not have left child
          a) Print current’s data
          b) Go to the right, i.e., current = current->right
       Else
          a) Make current as right child of the rightmost node in current's left subtree
          b) Go to this left child, i.e., current = current->left
    	 * @param args
    	 */
    	public static void printinorderTree(TreeNode root){
    		TreeNode current = root;
    		while(current!=null){
    			if(current.left==null){
    				System.out.print(current.value+" ");
    				current = current.right;
    			}else{
    				TreeNode node = current.left;
    				while(node.right!=null&&node.right!=current){
    					node = node.right;
    				}
    				if(node.right==null){
    					node.right = current;
    					current = current.left;
    				}else{
    					System.out.print(current.value+" ");
    					node.right = null;
    					current = current.right;
    				}
    			}
    		}
    	}
    	public static void main(String[] args) {
    		
    		TreeNode root = new TreeNode(1);
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(3);
    		root.left.left = new TreeNode(4);
    		root.left.right = new TreeNode(5);
    		printinorderTree(root);
    
    	}
    
    }
    

    展开全文
  • #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct treeNode { int data; struct treeNode* rChild; struct treeNode* lChild;...typedef stru...
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct treeNode
    {
    	int data;
    	struct treeNode* rChild;
    	struct treeNode* lChild;
    }tree, *BinTree;
    
    typedef struct 
    {
    	tree Tree[30];
    	int top;
    }stack;
    
    int creatTree(BinTree& pNode)
    {
    	int ch;
    	scanf("%d", &ch);
    	if (ch == 0)
    	{
    		pNode = NULL;
    	}
    	else
    	{
    		pNode = (BinTree)malloc(sizeof(tree));
    		pNode->data = ch;
    		creatTree(pNode->lChild);
    		creatTree(pNode->rChild);
    		return 0;
    	}
    }
    
    void initStack(stack& s)
    {
    	s.top = 0;
    }
    
    
    void push(stack& p, BinTree pNode)
    {
    	p.Tree[p.top] = *pNode;
    	p.top++;
    }
    
    BinTree pop(stack& p)
    {
    	BinTree temp = &p.Tree[p.top];
    	p.top--;
    	return temp;
    }
    
    bool isEmpty(stack p)
    {
    	if (p.top == 0)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    void inOrderTravelTree(BinTree p1,stack s)
    {
    	initStack(s);
    	while (p1 || !isEmpty(s))
    	{
    		while (p1 != NULL)
    		{
    			push(s, p1);
    			p1 = p1->lChild;
    		}
    		if (!isEmpty(s))
    		{
    			printf("%d", pop(s)->data);
    			p1 = pop(s)->rChild;
    		}
    	}
    }
    
    int main()
    {
    	stack s;
    	BinTree pHead=NULL;
    	creatTree(pHead);
    	inOrderTravelTree(pHead,s);
    	return 0;
    }
    
    展开全文
  • 二叉树中序非递归遍历与递归遍历 二叉树非递归遍历用到了,可能很多同学都知道算法原理,而真的去实现这一原理可能没有那么简单,所以同学们可以多下功夫,实践出真知。 #include<stdio.h> #include<...

    二叉树中序非递归遍历与递归遍历

    二叉树非递归遍历用到了栈,可能很多同学都知道算法原理,而真的去实现这一原理可能没有那么简单,所以同学们可以多下功夫,实践出真知。

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Tree {
    	int data;
    	Tree *lchild;
    	Tree *rchild;
    
    }Tree;
    
    
    Tree* create_binary_tree(Tree* T) {
    	
    	int t;
    	
    	scanf_s("%d", &t);
    	//T = (Tree*)malloc(sizeof(Tree));
    	if (t!= -1) {
    		
    		T->data = t;
    		T->lchild = (Tree*)malloc(sizeof(Tree));
    		T->lchild=create_binary_tree(T->lchild);
    		T->rchild = (Tree*)malloc(sizeof(Tree));
    		T->rchild=create_binary_tree(T->rchild);
    		
    	}
    	else { T = NULL; }
    	return T;
    	
    }
    
    void middle_order(Tree* T) {
    	if (T) {
    		middle_order(T->lchild);
    		printf("%d ", T->data);
    	
    		middle_order(T->rchild);
    	}
    }
    
    
    typedef struct stack {
    	Tree * a[50];
    	int top=0;
    	
    }stack;
    void instack(stack & s,Tree * data) {
    	s.a[s.top] = data;
    	s.top++;
    }
    int empty(stack &s) {
    	if (s.top == 0) {
    		return 1;
    	}
    	else return 0;
    }
    Tree* exstack(stack &s) {
    	if (!empty(s))
    		s.top--;
    	return s.a[s.top];
    }
    
    
    void middle_f(Tree* T) {
    	Tree* t = T;
    	stack s;
    	//instack(s,t);
    	//printf("%d", s.top);
    	//printf("%d", empty(s));
    	while (!empty(s))
    		if (t) {
    			instack(s, t);
    			t = t->lchild;
    		}
    		else {
    			t = exstack(s);
    			printf("%d ", t->data);
    			t = t->rchild;
    		}
    	}
    
    
    
    int main() {
    	Tree* T = NULL;
    	T = (Tree*)malloc(sizeof(Tree));
    	T=create_binary_tree(T);
    	//printf("%d ", T);
    	/*printf("%d ", T->lchild);
    	printf("%d ", T->rchild);*/
    	middle_order(T);
    	middle_f(T);
    	return 0;
    
    }
    
    
    
    
    展开全文
  • 中序非递归算法

    2020-10-26 20:06:16
    中序非递归算法 首先我们初始化一个,让根指针进栈。因为是中序遍历,所以我们首先要找到树的最左边结点,代码标记1完成的就是这个任务。那么代码标记1循环停止的条件不满足时,这个时候GetTop(S,p)得到的指针p是...

    中序非递归算法

    首先我们初始化一个栈,让根指针进栈。因为是中序遍历,所以我们首先要找到树的最左边结点,代码标记1完成的就是这个任务。那么代码标记1循环停止的条件不满足时,这个时候GetTop(S,p)得到的指针p是空的,因为到达最左边了,p->lchild是空,故我们需要把这个进栈的空指针给Pop掉,这是代码标记2的作用。

       下面是关键一步了,我们需要访问当前栈顶结点了。Pop(S,p)删除栈顶结点并赋给p,然后Visit函数代表我们要对这个结点进行的 操作,这是代码标记4的作用。至于代码标记5就很明显了,将右结点进栈,重新进行这个操作,即:先找最左边结点。。。。
    
       我们再用一个实例来捋一遍:
    

    根据咱们的代码,第一遍循环:首先会找到B结点,执行visit,然后C进栈,此时栈里有A,C两个结点,第二遍循环:然后找到C结点,C出栈执行visit,然后右结点为空,进栈,第三遍循环:然后由于这个栈顶元素是空的,Pop掉,此时栈不空,还剩A,出栈,执行visit,D进栈,然后第四遍循环:D出栈,E进栈,E的左结点为空,进栈,然后出栈,E再出栈,执行visit,然后E的右空结点进栈,第五次循环:空结点出栈然后为空,pop掉之后,再出栈D,执行visit,然后F进栈,第六次循环:F的空结点进栈,被pop掉,F出栈,然后执行visit,F的空结点进栈,第七次循环:然后因为两次栈不为空,循环结束。

    在这里插入图片描述

    方法一:

    //中序遍历
    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;             
                }  
            }  
                      
        }  
    
    展开全文
  • 那麽我们今天的中序非递归又是怎末做到的呢? 首先,我们先看看中序遍历的规律,分析思路才能更方便写代码 如上图所示的二叉树,我们都知道中序遍历是:左子树----根节点----右子树。遍历结果为:3 2 1 5 4 6 ...
  • 不借助非递归中序遍历算法) 三叉链表类型定义: typedef struct TriTNode { TElemType data; struct TriTNode *parent, *lchild, *rchild; } TriTNode, *TriTree; 思路为:1 先向左走到尽头,访问了最左结点 2 ...
  • 前序、中序、后序的非递归遍历中,要数后序最为麻烦,如果只在中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在中。 方法有很多,这里只举一种,先定义结点的数据结构 typedef struct{Node * p;...
  • \n中序非递归遍历:\n"); inorder(T,PrintElement); return 0;}</code></pre> <p><img alt="" height="1029" src="https://img-ask.csdnimg.cn/upload/1620907957837.png" width="1550" /></p>
  • 二叉树中序非递归

    2018-04-23 18:55:02
    创建2.创建一个指针p,辅助遍历3.左子树循环入栈,直到最后一个结点没有左孩子4.读栈顶,出栈5.p指向p的右孩子void InOrderUncursionTravere(BiTree T) { BiTNode *stack[Maxsize]; //定义一个 int top = -1; ...
  • 二叉树的递归算法虽然简单,但是会导致时间复杂度比较高,下面给大家带来用实现的二叉树非递归算法首先定义好二叉树,和元素类型为二叉树的typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, ...
  • 一,二叉树的中序非递归遍历(借助顺序实现) 1.完整代码 #include<iostream> #include<malloc.h> using namespace std; #define TElemType int #define TRUE 1 #define FALSE 0 #define OK 1 #...
  • void intraverse(tree t)//中序非递归遍历 { tree t1; stack *s; initstack(s); while(t||getTop1(s,t1)) { if(t) { push1(s,t); t=t->lch; } else { pop1(s,t); printf("%d ",t->data);...
  • 二叉树中序非递归遍历算法: 先将左子树放进中,无左子树时出栈,从右子树开始,继续对右子树循环。 代码如下: void inOrder2(BinTree *root) //非递归中序遍历 2 { 3 stack<BinTree*> s; 4 ...
  • 基本思路: 1. 开始根节点入栈 2. 循环执行如下操作:如果栈顶结点左孩子存在...3. 当空且遍历指针为空时算法结束 void inorderNonrecursion(BTNode *bt) { if (bt != NULL) { BTNode *Stack[maxsize]; ...
  • #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef char datatype; /*定义二叉树的数据结构*/ typedef struct BiTreeNode .../*定义一个用于非递归存储节点—的数据结构*/
  • //若使用非递归且不用来进行中序遍历,则需要parent指针作为辅助 node1->parent = node2; node2->parent = node4; node3->parent = node4; node5->parent = node6; node6->parent = node8; node7->...
  • 中序非递归遍历: 算法1:(1)从根结点开始,当前结点存在或者不为空进入循环  (2)当前结点进栈,进入其左子树,重复此操作,直到当前结点为空; (3)若不为空,则退,输出当前结点,进而访问退结点...
  • 之前写过二叉树的递归遍历的三种情况,很简单的讲解,很简单的代码就能实现,因为二叉树的很多操作都基于二叉树这个自然的递归...的空间通常也只有几兆大小而已,总有一天会用完,所以就需要通过非递归的方式来解决这
  • 需要使用,算法如下:1 若根节点为空,判断栈顶是否为空,非空出栈访问右子树。 为空则结束 向左走,如果左子树非空,则根节点入栈,访问左子树 如果左子树为空,打印,判断右子树2  右子树非空,访问右...
  • void InOrder(pBTNode pT)//中序遍历 { if (pT) { InOrder(pT->pLchild); Visit(pT); InOrder(pT->pRchild); } } void PostOrder(pBTNode pT)//后序遍历 { if (pT) { PostOrder(pT->pLchild); ...
  • 一、实验目的 ...3、采用非递归的编程方法,分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数,以及数据值的最大值和最小值。 4、(选作内容)试编写按层次顺序遍历二叉树的算法。参考算法思想:
  • cout元素按照中序非递归输出为"; InOrderTraverse_non(T); cout; break; case 5: cout元素按照后序递归输出为"; PostOrderTraverse(T); cout; break; case 6: cout二叉树的深度为"; d=Depth( ...
  • //void InOrder_NoUsingStack(Tree T)//三叉链表非递归栈中序遍历 //这个函数代码思想是看别人的,自己写不出来 #include<iostream> using namespace std; #define TElemType double typedef struct TNode {...
  • 利用的方法来遍历 先访问将根结点和左子树根结点压栈,然后不断访问左子树,直到NULL,再访问左子树下的右子树,遇到NULL,就出栈。大类的右子树和左子树差不多思路如下图: 代码#include #include typedef ...
  • 二叉树的中序非递归遍历c语言版

    千次阅读 2016-10-06 07:56:54
    由于c语言没有c++的STL库,我们无法借助c++的stack库实现二叉树的非递归遍历,但是,我们完全可以自己打造一个c语言版的stack库。本篇博文就是借助我们之前在的链式 存储这篇博文实现的程序。当然,你也可以把它...
  • 给定一个二叉树,返回它的中序遍历。...非递归算法:利用实现递归到非递归的转换 递归的本质:先调用的函数压栈,一层一层递归调用其实就是栈顶元素(函数)不断出栈的过程 1.非递归解法 # Defini...
  • 为了只用O(h)的空间,我们采用非递归迭代策略。 思路: 能往左走就往左走,边走边入栈,直到不能走,弹出里元素往右走,重复之前操作。 /** * Definition for a binary tree node. * struct TreeNode { * ...
  • 一、二叉树的遍历 二叉树的遍历分为先序遍历,... 递归方式比较简单和常见,非递归采用来实现 二、代码:  二叉树的定义:  /** * @author 作者 : xcy * @version 创建时间:2016年11月20日 下午8:21:03 *

空空如也

空空如也

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

栈中序非递归