精华内容
下载资源
问答
  • 小小学习,C语言数据结构,中序遍历二叉树递归算法
  • 二叉树中序遍历(非递归)算法实现--C语言

    千次阅读 多人点赞 2018-12-14 10:50:25
    昨天写了一遍二叉树的先序遍历(非递归算法,今天写一下二叉树二叉树中序遍历(非递归算法中序遍历的非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~ ...

    今天继续二叉树的学习。
    昨天写了一遍二叉树的先序遍历(非递归)算法,今天写一下二叉树的二叉树的中序遍历(非递归)算法。中序遍历的非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~

    首先给出今天的二叉树的示例图:
    在这里插入图片描述

    代码如下:

    
    #include "stdafx.h"
    #include <stdlib.h>
    #define STACKINITSIZE 20//栈初始空间大小
    #define INCREASEMENT 10//栈空间大小的增量
    
    typedef struct BiTNode
    {
    	char data;//二叉树节点数据
    	BiTNode *lchild,*rchild;//指向二叉树左子树和右子树的指针
    }BiTNode,*BiTree;//定义二叉树节点结构
    
    typedef struct SqStack
    {
    	BiTNode *base;//栈底指针
    	BiTNode *top;//栈顶指针
    	int stacksize;//顺序栈空间大小
    }SqStack;//定义顺序栈结构
    
    //建立一个空栈,建立成功,返回1,失败,返回0
    int InitStack(SqStack &S)
    {
    	S.base = (BiTNode*)malloc(STACKINITSIZE * sizeof(BiTNode));//20为栈的大小,可以更改
    	if(!S.base)
    		return 0;
    	S.top = S.base;
    	S.stacksize = STACKINITSIZE;
    	return 1;
    }
    
    //进栈操作
    int Push(SqStack &S,BiTNode e)
    {
    	if(S.top - S.base >= S.stacksize)
    	{
    		S.base = (BiTNode*)realloc(S.base,(STACKINITSIZE + INCREASEMENT) * sizeof(BiTNode));
    		if(!S.base)
    			return 0;
    		S.stacksize = 30;
    	}
    	*S.top = e;
    	S.top ++;
    	return 1;
    }
    
    //出栈操作,若栈为空,则返回0;栈不为空,则返回1
    int Pop(SqStack &S,BiTNode &e)
    {
    	if(S.base == S.top)
    		return 0;
    	S.top --;
    	e = *S.top;
    	return 1;
    }
    
    //判断栈是否为空,若栈为空,则返回true,栈不为空,则返回false
    bool StackEmpty(SqStack S)
    {
    	if(S.base == S.top)
    		return true;
    	else
    		return false;
    }
    
    //建立二叉树
    void CreateBiTree(BiTree &T)
    {
    	char ch;
    	scanf("%c",&ch);
    	if(ch == '#')
    		T = NULL;
    	else
    	{
    		T = (BiTNode *)malloc(sizeof(BiTNode));
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    //中序遍历二叉树
    int InOrderTraverse(BiTree T)
    {
    	if(!T)
    		return 0;
    	SqStack S;
    	int n = InitStack(S);//建立空栈
    	if(!n)
    		return 0;
    	BiTree p = T;
    	BiTNode e;//二叉树节点,用于存放从栈中取出的节点
    	while(p || !StackEmpty(S))
    	{
    		if(p)
    		{
    			Push(S,*p);
    			p = p->lchild;
    		}
    		else
    		{
    			Pop(S,e);
    			printf("%c ",e.data);
    			p = e.rchild;
    		}
    	}
    	printf("\n");
    	return 1;
    }
    
    int main(int argc, char* argv[])
    {
    	BiTree T = NULL;
    	printf("请输入二叉树-按照先序序列建立二叉树\n");
    	CreateBiTree(T);
    	printf("中序遍历二叉树结果为:\n");
    	InOrderTraverse(T);
    	return 0;
    }
    
    
    

    测试结果:
    在这里插入图片描述
    代码相对于先序遍历来说,几乎改动不大,只在遍历函数里有改动。但是,为了多练习,还是应该再敲一遍,说不定会有新的启发。对于C语言,自己可能还是刚入门阶段,但是不去多练习,又怎么会有提高呢!就像做数学题一样,自己觉得看着都会,却又不去动手去做,那在真正考试的时候,很可能的结果就是大部分题目都做不出来。究其原因当然是平时动手太少,觉得自己都会而懒于去做。
    写代码也是一样,之前看的时候觉得自己道理都懂,但是昨天自己心血来潮,想建立一个空栈竟然都成问题,当时内心感慨颇多,学了这么多年计算机,竟然到现在把最简单的东西都忘得差不多了。所以决定给自己定下小目标,每天至少更新一篇博客:博客上要附上自己今天敲的代码。无论自己是否从事这类的工作,都要坚持下去!虽然不能说自己有多么的喜欢这些内容,但是至少在敲代码的时候自己的内心是平静的!

    关于二叉树的一些原理什么的,在更新完相应的内容之后会做一个汇总,形成知识框架,不止为了记录在博客上,也是为了更好的印在脑海里!

    展开全文
  • 递归中序遍历二叉树算法详解

    万次阅读 多人点赞 2017-11-11 11:10:07
    我们如果不适用递归中序遍历二叉树即实现输出二叉树中的全部数据并且每个节点只访问一次的操作。那么在我们的算法中是通过单独开内存来保存节点数据,我们这个内存指的其实就是我们学过的栈数据结构S

    注意学习这个算法需要随时可以在脑海中输出二叉树的中序遍历的序列
    举例:

    这里写图片描述

    如上图,我们就看到一棵二叉树:那么我们是不是马上可以想到这棵二叉树的中序遍历序列是什么呢?

    我直接给出答案:D B EF A G H C I
    我们如果不适用递归中序遍历二叉树即实现输出二叉树中的全部数据并且每个节点只访问一次的操作。

    那么在我们的算法中是通过单独开内存来保存节点数据,我们这个内存指的其实就是我们学过的栈数据结构Stack.

    现在我们需要观察中序序列的规律来把栈数据结构应用到这个算法当中。

    首先我们的中序遍历是先遍历A节点的左孩子节点在A节点在A的右孩子节点。 然后对应A的左孩子节点也就是B为根的一棵子树, 我们还是先要访问B节点的左子节点也就是D.

    现在我们发现我们是访问的B,然后是A,但是输出结果确是DB, 那么我们就发现一个规律就是先访问的节点数据反而是后输出,是不是和我们的栈数据结构的先进后出相似呢。 因此我们就联系到了stack数据结构,。

    下面假如我们在访问的过程就把节点入栈,直到左子节点为null,说明我们已经找到了可以输出的数据起点,这个时候刚好我是把这个数据起点保存在了栈数据结构最后一个,那么这个时候我们入栈的次顺依次是ABD。那么我们出栈就等于是开始输出中序遍历的第一个数据,我们开始出栈D,由于是中序遍历那么我们接着出栈B,这个时候不能出栈了,因为我们需要输出B节点的右子全部节点。因此我们又开始入栈F,然后是E.

    然后我们在出栈栈首元素也就是E,我们用一个变量保存下来,然后输出E中的数据,接着出栈F,输出其中的数据。 这个时候我们到了A这里,我们在出栈A,在把右子树入栈。在出栈。

    大家发现了没有,其实不用递归的话,我们中序遍历输出数据,用的是栈先入栈在出栈就得到数据。

    现在我来贴上实现代码:

    //上的代码类似伪代码

    //非递归中序遍历算法 BT:保存了二叉树的地址 BT默认是根节点的地址
    void InorderTraversal(BTree BT)
    {
    //开辟临时变量保存
    BTree T =BT

    //申明栈数据结构对象
    Stack s = CreatStack(MaxSize);  //初始化栈,默认大小为MaxSize
    
    //使用循环中序遍历输出节点数据
    while(T)  //什么时候停止循环 假如T已经拿不到节点数据或者栈
    {
        //用一个循环来压栈
        while(T)  //我们需要T中保存了节点的地址才可以压栈
        {
            s.Push(T); //把当前节点入栈
            T->left;  //转向当前节点的左孩子节点
        }
    
        //在用一个循环来出栈输出数据
       while(!s.Empty)
       {
           temp = s.Pop();  //出栈保存当前栈顶节点
    
           //准备输出节点里的数据内容
           printf("%d",T->data);           
       }
    
       //转到右子树压栈
       T = T->right;
       if(s.Empty)  //当栈当中没有元素说明已经输出全部数据,那么就要跳出循环
       {
          break;
       }
    }
    

    }

    展开全文
  • 中序遍历递归算法在VC6.0环境下运行成功!
  • 二叉树中序遍历(非递归实现)

    万次阅读 多人点赞 2018-01-04 20:37:39
    一、递归实现前序,序,后序遍历;对于二叉树,前面已经采用...下面,以实现中序遍历二叉树为主题展开:二、非递归实现 中序遍历:1,结构: 首先,对于中序遍历,我们知道,原则是先走到的结点后访问,后走到的结点

    ####一、递归实现前序,序,后序遍历;

    对于二叉树,前面已经采用递归的方式实现的其前序,中序,后序遍历,具体请参见:

    http://blog.csdn.net/dai_wen/article/details/78955411

    那么,如何采用非递归的方式遍历树呢?

    下面,以实现中序遍历二叉树为主题展开:

    ####二、非递归实现 中序遍历:

    1,结构:
    首先,对于中序遍历,我们知道,原则是先走到的结点后访问,后走到的结点先访问,这显然是栈的结构;

    2,访问结点的具体步骤:

    结点的所有路径情况:
    step1: 如果当前结点有左子树,则该结点入栈;
    -----------如果没有左子树,则访问该结点;
    step2:如果结点有右子树,则重复step1;
    --------- 如果没有右子树,则回退,让此时的栈顶元素出栈,访问栈顶元素,并访问栈顶元素的右子树,重复step1,2
    strp3:如果栈为空,则表示遍历结束;


    注意:入栈结点本身没有被访问过,同时,其右子树也没有被访问过;
    3,流程图:

    那么,根据文字,画出如下流程图:

    //下面,举个例子:
    

    如下所示的五个结点的二叉树,其非递归中序遍历如下图所示:

    (1)实现思路图如下所示:

    (2)具体程序实现:

    #include <iostream>
    #include <stack>
    using namespace std;
    
    //二叉链表 
    typedef struct BiTNode
    {
    	int data;
    	struct BiTNode *lchild, *rchild; //左孩子 右孩子
    }BiTNode,*BiTree;
    
    /*树的形状
          1
    	2     3 
      4      5
     */
    
    BiTNode *GoFarLeft(BiTNode *T, stack<BiTNode *> &s)//一直向左走函数
    {
    	if (T == NULL)
    	{
    		return NULL;
    	}
    	//如果T有左孩子 入栈
    	while (T->lchild)
    	{
    		s.push(T);
    		T= T->lchild;//一直往左走
    	}
    	return T; //找到一个没有左孩子的节点,就是中序遍历的起点
    }
    
    void InOrder2(BiTNode *T)
    {
    	stack<BiTNode *>s;
    	BiTNode *t = GoFarLeft(T, s); //中序遍历的起点
    
    	while(t)
    	{
    		printf("%d ", t->data);
    		if (t->rchild) //如果有右孩子 重复12步骤
    		{
    			 t = GoFarLeft(T->rchild, s);
    		}
    		else if (!s.empty())  //如果没有右孩子,说明该节点的树放完毕,需要返回。
    		{
    			t  = s.top(); //非空就从栈顶拿元素
    			s.pop();
    		}
    		else //如果没有右孩子,并且栈为空 t = NULL;
    		{
    			t = NULL;
    		}
    	}
    }
    
    int  main()
    {
    	BiTNode b1, b2, b3, b4, b5;
    	BiTNode *pNewTree = NULL;
    	memset(&b1, 0, sizeof(BiTNode));
    	memset(&b2, 0, sizeof(BiTNode));
    	memset(&b3, 0, sizeof(BiTNode));
    	memset(&b4, 0, sizeof(BiTNode));
    	memset(&b5, 0, sizeof(BiTNode));
    	b1.data = 1;
    	b2.data = 2;
    	b3.data = 3;
    	b4.data = 4;
    	b5.data = 5;
    
    	//构建树关系
    	b1.lchild = &b2;
    	b1.rchild = &b3;
    	b2.lchild = &b4;
    	b3.lchild = &b5;
    	
    	InOrder2(&b1);
    
    return 0;
    }
    

    (3)程序实现结果:

    (4)总结,非递归实现中序遍历,其关键在于判断其左右子树存不存在,处理好压栈和出栈的顺序即可,只要仔细一些,就没什么问题了

    展开全文
  • 二叉树中序遍历的非递归算法

    千次阅读 2016-05-04 15:33:04
    用栈实现二叉树中序遍历的非递归算法

    用栈实现二叉树中序遍历的非递归算法微笑


    #include<stdio.h>
    #include<malloc.h>
    #define OK 1
    #define ERROR 0
    #define STACK_INIT_SIZE 100 
    /*预定义栈的长度为100
    【身无分文的你你找你老妈要了100块,实际上你可能只花了50块】
    【我们预先找电脑要了100个储存单元,实际上栈可能没有那么长】*/
    #define STACKINCREMENT 10


    typedef int Status;
    typedef char ElemType;

    typedef struct BiTNode
    {
     ElemType data;
     struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;              //定义二叉树


    typedef BiTree SElemType;  //定义SElemType是二叉树类型



    struct SqStack
    {
     SElemType *base;
     SElemType *top;
     int stacksize;
    };           //定义栈

    Status InitStack(SqStack &S) //构建栈
    {
     S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
     if(!S.base) //没有分配到内存返回ERROR
      return ERROR;
     S.top=S.base;
     S.stacksize=STACK_INIT_SIZE;
     return OK;
    }

    Status Push(SqStack &S,SElemType e) //将元素e入栈
    {
     if(S.top-S.base>=S.stacksize)
     {
      S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
      if(S.base)
       return ERROR;
      S.top=S.base+S.stacksize;
      S.stacksize+=STACKINCREMENT;
     }
     *S.top++=e;  //先自加后赋值
     return OK;
    }

    Status Pop(SqStack &S,SElemType &e)  //删除栈顶元素,用e返回其值
    {
     if(S.top==S.base)
      return ERROR;
     e=*--S.top;  //先取内容后自减再赋值
     return OK;
    }

    Status GetTop(SqStack S,SElemType &e)  //取栈顶元素
    {
     if(S.top==S.base)
      return ERROR;
     e=*(S.top-1);
     return OK;
    }


    BiTree CreateBiTree(BiTree &T)
    //将要构建的二叉树按照先序序列输入,当某节点左孩子(或者右孩子,或两者)为空时输入#代替
    {
     char ch;
     scanf("%c",&ch);
     if(ch=='#')
      T=NULL;
     else
     {
      if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
       return ERROR;
      T->data=ch;
      CreateBiTree(T->lchild);
      CreateBiTree(T->rchild);
     }
     return T;
    }

    Status Visit(ElemType e)
    {
     if(e!='#')
     {
      printf("%c",e);
      return OK;
     }
     else
      return ERROR;
    }


    Status InOrderTraverse(BiTree T)  //利用栈中序遍历二叉树
    {
        BiTNode *p=T;
     SqStack S;
     InitStack(S);
     Push(S,T);
     while(S.top!=S.base) //当栈不为空
        {
            while(GetTop(S,p)&&p)
            {
                Push(S,p->lchild);
            }
            Pop(S,p);
            if(S.top!=S.base)
            {
                Pop(S,p);
                if(!Visit(p->data))
                return ERROR;
                Push(S,p->rchild);
            }

        }
        return OK;
    }

    int main()
    {
        BiTree T;
        printf("先构造二叉树:\n");
        CreateBiTree(T);
        printf("该二叉树中序遍历如下:\n");
        InOrderTraverse(T);
    }


    展开全文
  • 二叉树中序遍历的非递归算法同样可以使用栈来实现,从根结点开始,将根结点的最左结点全部压栈,当结点p不再有最左结点时,说明结点p没有左孩子,将该结点 出栈,访问结点p,然后对其右孩子做同样的处理。 ...
  • 在此之前,我们已经学习了中序遍历二叉树递归算法,相信大家已经将其牢牢掌握了. 除了使用递归思想作为求解问题的钥匙,还可以借助栈来以非递归方式实现该问题的求解. 首先,我们要讨论存储二叉树结点信息的栈...
  • 二叉树递归遍历算法很简单,而非递归遍历算法中的先序和中序遍历相比于后序遍历更简单一点,在这先实现先序和中序遍历的非递归算法。 先序遍历代码如下: public static void preOrder(TreeNode root) { ...
  • 中序遍历二叉树

    2011-12-10 14:09:00
    数据结构实验(c++):中序遍历二叉树递归与非递归算法
  • 中序遍历二叉树,非递归实现
  • LeetCode 144 二叉树中序遍历 递归递归 通俗易懂的万能模板方法1.递归 二叉树中序遍历2.非递归 二叉树中序遍历 万能模板法 二叉树遍历方式作为面试热门考点,相信递归的方式大家都很容易能够写出来,但只掌握...
  • 今天我们来学习二叉树中序遍历算法二叉树有多种遍历方法,前中序遍历和层次遍历。我们今天的主角是中序遍历,它的遍历顺序为: 左子树 根节点 右子树 如下图所示: 我们知道树的定义本身就是递归式的,左...
  • C语言实现二叉树中序遍历(非递归),本人亲自写的!
  • 算法递归中序遍历二叉树总结(2种方法) @author:Jingdai @date:2020.12.03 方法1 先序遍历是第一次遇到该节点遍历;中序是第二次遇到该节点遍历;而后序是第三次遇到该节点遍历。非递归用栈进行遍历,第一次遇到...
  • 根据前序遍历中序遍历 重建二叉树 题目描述 输入某二叉树的前序遍历中序遍历的结果,请重建出该二叉树。假设输入的前序遍历中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序...
  • 二叉树中序遍历中,访问节点的操作发生在该节点的左子树遍历完毕并准备...中序遍历的非递归算法只需将前序遍历的非递归算法中的输出语句 cout << T->data ; 移到T=s[top–];之后即可。 具体实现如下:#include u
  • 二叉树中序遍历 ,非递归迭代实现。 思路: 因为中序遍历为左根右,所以先需要遍历以cur为根的二叉树最左侧的节点。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *...
  • import java.util.Stack; /** ... * 二叉树递归中序遍历 * @param binaryTree 二叉树 */ public static void inOrder(BinaryTree binaryTree){ if(binaryTree != null){ //先遍历左节点 in.
  • //算法5.2 中序遍历的非递归算法 #include <iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode { char data; //结点数据域 struct BiNode *lchild, *rchild; //左右孩子...
  • 中序遍历的非递归算法 C语言数据结构中序遍历的非递归算法
  • 原理:前序遍历的第一个为根结点,在中序遍历中找到对应的结点位置后,在该位置左侧为根结点的左子树,在该位置右侧的为右子树,并可以找到在前序遍历中根结点...还原算法以及前序、中序和后序遍历递归算法 pac...
  • 二叉树中序遍历递归算法 目标遍历二叉树: 1 / \ 2 4 / \ 3 5 待输出结果为3,2,5,1,4 1.首先得用上面定义的结构体把这颗树表示出来 2.表示出这颗树后在调用二叉树中序遍历递归算法 */...
  • 二叉树中序遍历的非递归算法

    千次阅读 2012-12-26 14:17:32
    先回顾二叉树中序遍历递归算法: 先遍历左子树 然后遍历根结点 最后遍历右子树 对于左子树和右子树使用同样的思想   二叉树中序遍历的非递归算法的思想: 中序遍历最先输出的结点是根结点的左子树中的...
  • 首先, 我们需要找到二叉树T中第一个被中序遍历的结点: 根据中序遍历算法逻辑, (※)也就是找到二叉树T的最左下结点. 下面的算法可定位到二叉树的最左下结点. BiTreeNode* FirstNode(BiTreeNode* T)//在以T为根...
  • 二叉树中序遍历 (非递归) /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} ...
  • 递归中序遍历二叉树 发表于 2013 年 9 月 12 日 由 herbertdai 非递归中序遍历二叉树的实现思考了好久,想出一个很麻烦的办法,大致思路是先走最左,再回中点,再向右一格,记录已经访问的节点,已经访问过...
  • 中序遍历二叉树 递归算法 def inorderTraversal(root): f = self.inorderTraversal return f(root.left)+[root.val]+f(root.right) if root else [] 非递归算法 def inorderTraversal(root): stack, res...
  • 中序遍历递归方法: ... 而在非递归调用中序遍历二叉树中,利用栈的LIFO的特点。因为中序遍历从二叉树最左的节点开始遍历,然后其父节点,最后父节点的右子树。因此算法为: 1.1.初始化当前指针cur指向

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,404
精华内容 28,161
关键字:

中序遍历二叉树算法递归