精华内容
下载资源
问答
  • 中序遍历二叉树算法递归
    2022-01-24 00:46:19

    //算法5.2 中序遍历的非递归算法

    #include<iostream>
    using namespace std;
    
    //二叉树的二叉链表存储表示
    typedef struct BiNode
    {				
    	char data;						//结点数据域
    	struct BiNode *lchild,*rchild;	//左右孩子指针
    }BiTNode,*BiTree;
    
    //链栈的定义
    typedef struct StackNode
    {
    	BiTNode data;
    	struct StackNode *next;
    }StackNode,*LinkStack;
    
    //用算法5.3 先序遍历的顺序建立二叉链表
    void CreateBiTree(BiTree &T)
    {	
    	//按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
    	char ch;
    	cin >> ch;
    	if(ch=='#')  T=NULL;			//递归结束,建空树
    	else{							
    		T=new BiTNode;
    		T->data=ch;					//生成根结点
    		CreateBiTree(T->lchild);	//递归创建左子树
    		CreateBiTree(T->rchild);	//递归创建右子树
    	}								//else
    }									//CreateBiTree
    
    void InitStack(LinkStack &S)
    {
    	//构造一个空栈S,栈顶指针置空
    	S=NULL;
    }
    
    bool StackEmpty(LinkStack S)
    {
    	if(!S)
    		return true;
    	return false;
    }
    
    void Push(LinkStack &S,BiTree e)
    {
    	//在栈顶插入元素*e
    	StackNode *p=new StackNode;
    	p->data=*e;
    	p->next=S;
    	S=p;
    }
    
    void Pop(LinkStack &S,BiTree e)
    {
    	if(S!=NULL)//原书上写的是if(S==NULL)return ERROR;
    	{	
    		*e=S->data;
    		StackNode *p=S;
    		S=S->next;
    		delete p;
    	}
    } 
      
    void InOrderTraverse1(BiTree T)
    { 
      // 中序遍历二叉树T的非递归算法
    	LinkStack S; BiTree p;
    	BiTree q=new BiTNode;
    	InitStack(S); p=T;
    	while(p||!StackEmpty(S))
    	{
    		if(p) 
    		{            				
    			Push(S,p);				//p非空根指针进栈,遍历左子树
    			p=p->lchild;
    		}       
    		else
    		{             				
    			Pop(S,q);               //p为空根指针退栈,访问根结点,遍历右子树
    			cout<<q->data;
    			p=q->rchild; 
    		}
    	}								// while
    }									// InOrderTraverse
    
    void main()
    {
    	BiTree tree;
    	cout<<"请输入建立二叉链表的序列:\n";
    	CreateBiTree(tree);
    	cout<<"中序遍历的结果为:\n";
    	InOrderTraverse1(tree);
    	cout<<endl;
    }

    更多相关内容
  • 二叉树中序遍历 题目描述: 解题思路: 第一种:递归。又是递归,可以发现很多题都可以用到递归的思路…。二叉树中序遍历,这里不太了解的可以看看这个博客:二叉树遍历,总结了二叉树的所有遍历情况。这道题所...
  • //二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; //当前...
  • 小小学习,C语言数据结构,中序遍历二叉树递归算法
  • 1、先序遍历二叉树 递归实现思想:若二叉树为空,返回。否则 1)遍历根节点;2)先序遍历左子树;3)先序遍历右子树; 代码: 代码如下:template<typename> void PreOrder(nodeType<elemType> *root) { if(root==...
  • 中序遍历递归算法在VC6.0环境下运行成功!
  • 利用栈的基本操作实现二叉树中序遍历递归算法
  • C语言实现二叉树中序遍历(非递归),本人亲自写的!
  • } } 中序遍历算法: /** * 中序遍历 */ public class MidOrder { public static void main(String[] args) { TreeNode head = new TreeNode(1, "宋江"); TreeNode node2 = new TreeNode(2, "吴用"); TreeNode node3...

    在这里插入图片描述


    【1】正确序列:

    应该为2-1-3-4


    【2】代码:

    • 树节点:
    public class TreeNode {
        int no;
        String name;
        TreeNode left;
        TreeNode right;
    
        public TreeNode(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "{" + "no=" + no + ", name='" + name + '\'' + '}';
        }
    }
    

    • 二叉树
    public class BinaryTree {
        //二叉树根节点
        TreeNode head;
    
        public BinaryTree(TreeNode head) {
            this.head = head;
        }
    }
    

    • 中序遍历算法:
    /**
     * 中序遍历
     */
    public class MidOrder {
        public static void main(String[] args) {
            TreeNode head = new TreeNode(1, "宋江");
            TreeNode node2 = new TreeNode(2, "吴用");
            TreeNode node3 = new TreeNode(3, "卢俊");
            TreeNode node4 = new TreeNode(4, "林冲");
            head.left = node2;
            head.right = node3;
            node3.right = node4;
            BinaryTree bt = new BinaryTree(head);
            mid(bt);
        }
    
        public static void mid(BinaryTree bt) {
            if (bt.head == null) {
                System.out.println("二叉树为空!");
                return;
            }
            //调用遍历算法
            order(bt.head);
        }
    
        public static void order(TreeNode node) {
    
            //左递归
            if (node.left != null)
                order(node.left);
    
            //打印二叉树
            System.out.println(node);
    
            //右递归
            if (node.right != null)
                order(node.right);
        }
    }
    

    【3】测试:

    在这里插入图片描述

    展开全文
  • C语言 中序遍历二叉树--非递归算法

    千次阅读 多人点赞 2020-10-22 20:52:26
    typedef struct BiTNode//二叉树的结构体 { char ch;//二叉树的数据域 struct BiTNode *lchild,*rchild;//二叉树的指针域 }BiTNode ,*BiTree; typedef struct StackNode //栈的结构体 { BiTree data;//栈

    完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct BiTNode//二叉树的结构体 
    {
    	char ch;//二叉树的数据域 
    	struct BiTNode *lchild,*rchild;//二叉树的指针域 
    }BiTNode ,*BiTree;
    
    typedef struct StackNode //栈的结构体 
    {
    	BiTree data;//栈的数据域,(数据域为二叉树的一个结点) 
    	struct StackNode *next; //栈的指针域 
    }SqStack,*LinkStack;
    
    void InitStack(LinkStack &S)//栈的初始化,只有创建一个栈顶结点这一步 
    {
    	S = (SqStack*)malloc(sizeof(SqStack));//创建一个野结点,使其为NULL,便成为栈顶结点。 
    	S = NULL;
    }
    
    int Push(LinkStack &S,BiTree T)//进栈 
    {
    	SqStack* p;//定义一个野结点 
    	p = (SqStack*)malloc(sizeof(SqStack));
    	p->data = T;//使该结点装上数据元素T,并使其next等于S,类似于链表的头插法 
    	p->next = S;
    	S = p;//栈顶结点S,一直在栈的最前方 
    	return 0; 
    }
    
    void Pop(LinkStack &S,BiTree &T)//使栈顶元素出栈,并返回栈顶元素 
    {
    	if(S==NULL)//判断栈是否为空 
    	{
    		printf("栈空!");
    	}
    	else
    	{
    		SqStack* p;//这里定义一个结点,方便后面对栈顶结点的释放 
    		T = S->data; // 
    		p = S;
    		S = S->next;//使栈顶结点指向下一个结点,类似于栈减一 
    		free(p);//释放栈顶元素 
    	}	
    }
    
    void CreateTree(BiTree &T)//创建二叉树,这里是先序遍历的顺序建立的二叉链表  递归形式 
    {
    	char ch,trmp;
    	scanf("%c",&ch);//输入链表数据 
    	if(ch == '#')//如果出现输入的是#,终止递归。终止递归条件 
    		T = NULL;
    	else
    	{
    		T = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 
    		T->ch = ch;//对根结点进行赋值 
    		CreateTree(T->lchild);//递归创建左子树 
    		CreateTree(T->rchild);//递归创建右子树 
    	}
    }
    
    void InOrderTraverse(BiTree T)//中序遍历二叉树T的非递归算法 
    {
    	LinkStack S;
    	InitStack(S);//创建一个栈,并初始化 
    	BiTree p = T;
    	BiTree q = (BiTNode*)malloc(sizeof(BiTNode));//创建结点q,并为其申请空间 
    	while(p || S!=NULL)//循环终止条件是p为NULL与S等于NULL,两个条件同时满足的情况下,循环终止 
    	{
    		if(p)//p非空 
    		{
    			Push(S,p);//根指针进栈 
    			p = p->lchild;//遍历左子树 
    		}
    		else
    		{
    			Pop(S,q);//出栈 
    			printf("%c ",q->ch);//访问根结点 
    			p = q->rchild;//遍历右子树 
    		}
    	}
    }
    
    int main()
    {
    	BiTree T;
    	CreateTree(T);//创建一个二叉树 
    	InOrderTraverse(T);//非递归中序遍历二叉树 
    	printf("\n");
    	return 0;
    }
    

    结果演示:
    在这里插入图片描述
    (完)

    展开全文
  • 二叉树遍历递归算法不常考,主要考察非递归❤ 先序、中序、后序遍历递归递归算法的区别在于visit()函数的位置❤,代码以先序遍历为例,其顺序为根左右,if判断语句中符合这一规律,中序、后序按其左根右和...

    二叉树(BiTree)的遍历分为:
    先序遍历(preorder):根左右
    中序遍历(inorder):左根右
    后序遍历(postorder):左右根
    其中,时间复杂度和空间复杂度都是O(n),
    二叉树的遍历递归算法不常考,主要考察非递归❤

    先序、中序、后序遍历(递归)

    递归算法的区别在于visit()函数的位置❤,代码以先序遍历为例,其顺序为根左右,if判断语句中符合这一规律,中序、后序按其左根右和左右根的规律改变这三句代码的顺序即可。

    void preorder(BiTree T){ // 先序遍历递归算法
    	if(T!=NULL){  // 当二叉树的根节点不为空时
    		visit(T); // 先访问根节点❤
    		preorder(T->lchild); // 再访问左孩子
    		preorder(T->rchild);  // 最后访问右孩子
    	}
    }
    

    中序遍历(非递归)

    算法思想:非递归需要借助栈来实现,沿着根的左孩子一直向左走,将左孩子依次入栈,直到左孩子为空,然后从栈顶开始出栈,出栈的同时访问出栈结点,若有右孩子则等该出栈元素出栈后把他的右孩子入栈。
    图解与分析
    p指向根节点,q指向栈底
    在这里插入图片描述
    然后沿着左孩子一直走,并依次入栈,当走到D结点时,没有左孩子了。这时开始从栈顶出栈,此时的遍历序列为D,B。
    在这里插入图片描述
    D,B出栈后,此时p指向B结点,发现B还有右孩子,所以将右孩子出栈。此时的序列为D,B,E,此时栈里只剩一个A结点了。
    在这里插入图片描述
    然后继续将栈顶元素进行出栈并访问,此时序列为D,B,E,A,此时p指向A结点,发现A结点有右孩子,将右孩子进栈并出栈。此时二叉树遍历完毕,栈也为空,最终中序遍历结果为:DBEAC。
    在这里插入图片描述
    代码

    void Inorder(BiTree T){
    	InitStack(s); // 初始化一个栈s
    	BiTree *p=T;  // 将二叉树的根节点赋给指针p
    	while(p!=NULL || !IsEmpty(s)){ 
    	//❤ 二叉树不为空或栈不为空
    	// 即二叉树遍历完了栈也为空,才是真正的遍历完了,要不就像上面最后一张图,
    	// 栈空了,C还没进栈呢,就退出循环了。
    		if(p!=NULL){
    			push(s,p); // 左孩子依次,入栈
    			p=p->lchild;  // 左孩子不为空,向左一直走
    		}
    		else{
    			pop(s,p);  // 栈顶元素,出栈 
    			visit(p);
    			p=p->rchild;  // 访问右子树
    		}
    	}
    	free(s); 
    }
    

    注解
    push(s,x) 表示x入栈
    pop(s,y) 表示y出栈
    IsEmpty(A) 表示判断数列是否为空的函数
    InitStack(s) 表示初始化栈s

    展开全文
  • 本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历中序遍历的结果,请重建出该二叉树。假设输入的前序遍历中序遍历的结果中都不含...
  • 详细图解二叉树中序遍历(非递归二叉树中序递归含义LeetCode题目94详细图解源代码运行结果 二叉树中序递归含义 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回,否则: (1)...
  • (※)中序遍历二叉树的非递归算法

    千次阅读 多人点赞 2020-05-06 17:31:32
    在此之前,我们已经学习了中序遍历二叉树递归算法,相信大家已经将其牢牢掌握了. 除了使用递归思想作为求解问题的钥匙,还可以借助栈来以非递归方式实现该问题的求解. 首先,我们要讨论存储二叉树结点信息的栈...
  • 力扣 二叉树中序遍历 (非递归) Python

    千次阅读 2022-02-05 22:38:12
    # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right 测试系统已经定义好了结点,...
  • 满意答案文件 main.cpp 代码如下:#include // malloc()等#include // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等#include // atoi(),exit()#include // 数学函数头文件,包括floor...清空二叉树和销毁二叉树的...
  • 原理:前序遍历的第一个为根结点,在中序遍历中找到对应的结点位置后,在该位置左侧为根结点的左子树,在该位置右侧的为右子树,并可以找到在前序遍历中根结点...还原算法以及前序、中序和后序遍历递归算法 pac...
  • 二叉树中序遍历的非递归算法实现[借鉴].pdf
  • 算法递归中序遍历二叉树总结(2种方法) @author:Jingdai @date:2020.12.03 方法1 先序遍历是第一次遇到该节点遍历;中序是第二次遇到该节点遍历;而后序是第三次遇到该节点遍历。非递归用栈进行遍历,第一次遇到...
  • 二叉树中序遍历的实现思想是: 访问当前节点的左子树; 访问根节点; 访问当前节点的右子树; 图 1 二叉树 以图 1 为例,采用中序遍历的思想遍历二叉树的过程为: 访问该二叉树的根节点,找到 1; 遍历节点 1...
  • 二叉树遍历满足递归的思路,无论是先序的根左右,中序的左根右,还是后续的左右跟都是从根结点开始,对每个结点进行先序/中序/后序的遍历,每个结点都是如此,假如是先序根左右的遍历,我们先访问根结点,然后再是...
  • 今天我们来学习二叉树中序遍历算法二叉树有多种遍历方法,前中序遍历和层次遍历。我们今天的主角是中序遍历,它的遍历顺序为: 左子树 根节点 右子树 如下图所示: 我们知道树的定义本身就是递归式的,左...
  • 二叉树中序遍历(非递归)算法实现--C语言

    万次阅读 多人点赞 2018-12-14 10:50:25
    昨天写了一遍二叉树的先序遍历(非递归算法,今天写一下二叉树二叉树中序遍历(非递归算法中序遍历的非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~ ...
  • 力扣热门100题——二叉树中序遍历,包含递归,迭代,Morris 中序遍历三种方式,全AC代码,并附带注释和总结
  • 1)递归序,3次见面,第一次见面打印叫先序遍历,第二次见面打印叫中序遍历,第三次见面打印叫后序遍历 2)非递归实现中,先序和后序是相反的,但是中序遍历挺难理解,但是核心思想也就是先去左树,再打印头,然后再...
  • 一、二叉树先序遍历 (1)递归算法 // 递归先序遍历 public static void recursionPreorderTraversal(TreeNode root) { if (root != null) { System.out.print(root.val + " "); recursionPreorderTraversal(root...
  • 根据一棵树的前序遍历中序遍历构造二叉树思路代码二.根据一棵树的中序遍历与后序遍历构造二叉树思路代码 一.根据一棵树的前序遍历中序遍历构造二叉树 输入某二叉树的前序遍历中序遍历的结果,请构建该二叉树并...
  • 根据前序遍历中序遍历 重建二叉树 题目描述 输入某二叉树的前序遍历中序遍历的结果,请重建出该二叉树。假设输入的前序遍历中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序...
  • C++实现二叉树中序遍历递归算法

    千次阅读 2020-08-22 10:09:05
    二叉树中序遍历递归算法 目标遍历二叉树: 1 / \ 2 4 / \ 3 5 待输出结果为3,2,5,1,4 1.首先得用上面定义的结构体把这颗树表示出来 2.表示出这颗树后在调用二叉树中序遍历递归算法 */...
  • 二叉树中序递归遍历算法实现 大家好,我是刚刚起步的萌新,最近在学数据结构,此次为大家分享二叉树中序递归遍历算法,实现及差错修改。 1.第一步呢我们需要创建二叉树,栈,基本栈方法这些我们就不一一说了,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,238
精华内容 36,895
关键字:

中序遍历二叉树算法递归