精华内容
下载资源
问答
  • 树的先根遍历
    千次阅读
    2020-09-02 09:23:17

    二叉树

    在这里插入图片描述

    先根、中根、后根遍历

    三种遍历都是递归遍历

    1. 先根遍历
      结果:ABCDEFGH
      原理:先遍历节点,再遍历子树,最后遍历子树;
    2. 中根遍历
      结果:CBEDFAGH
      原理:先遍历子树,再遍历节点,最后遍历子树;
    3. 后根遍历
      结果:CEFDBHGA
      原理:遍历子树,再遍历子树,最后遍历节点;
    更多相关内容
  • 二叉树的根,中根,后根遍历

    千次阅读 2021-11-16 17:10:01
    二叉树(Binary tree)是形结构的一个重要类型 在java中,可以把数的一个节点看成一个对象,每个节点都有data和最多两个字节点 class TreeNode { int data; TreeNode left; TreeNode right; } 首先先生成一颗...

    二叉树(Binary tree)是树形结构的一个重要类型

    在java中,可以把数的一个节点看成一个对象,每个节点都有data和最多两个字节点

        class TreeNode {
            int data;
            TreeNode left;
            TreeNode right;
        }
    

    首先先生成一颗二叉树

    public void add(TreeNode node) {
            if (node.data < this.data) {
                if (left == null) left = node;
                else left.add(node);
            }
            if (node.data > this.data) {
                if (right == null) right = node;
                else right.add(node);
            }
        }
    
    public static void main(String[] args) {
            Tree tree = new Tree();
            tree.add(8);
            tree.add(4);
            tree.add(2);
            tree.add(3);
            tree.add(1);
            tree.add(6);
            tree.add(6);
            tree.add(7);
            tree.add(12);
            tree.add(10);
            tree.add(9);
            tree.add(11);
            tree.add(14);
            tree.add(13);
            tree.add(15);
        }
    

    创建的二叉树如下图所示
    在这里插入图片描述

    先根遍历:先根遍历就是先遍历根节点,然后遍历左子树,再然后右子树
    即输出8->4->2->1->3->6->7->12->10->9->11->14->13->15

        public void firstRoot() {
            System.out.print(data + " ");
            if (left != null) left.firstRoot();
            if (right != null) right.firstRoot();
        }
    

    中根遍历,先遍历左子树,然后遍历根,再然后遍历右子树
    即输出1->2->3->4->6->7->8->9->10->11->12->13->14->15

    public void midRoot() {
            if (left != null) left.midRoot();
            System.out.print(data + " ");
            if (right != null) right.midRoot();
        }
    

    后根遍历:先遍历左子树,然后再遍历右子树,最后再遍历根;
    即输出:1->3->2->7->6->4->9->11->10->13->15->14->12->8

    public void afterRoot() {
            if (left != null) left.afterRoot();
            if (right != null) right.afterRoot();
            System.out.print(data + " ");
        }
    

    完整代码

    public class TreeNode {
        public int data;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int data) {
            this.data = data;
        }
    
        //中序存
        public void add(TreeNode node) {
            if (node.data < this.data) {
                if (left == null) left = node;
                else left.add(node);
            }
            if (node.data > this.data) {
                if (right == null) right = node;
                else right.add(node);
            }
        }
    
        public void firstRoot() {
            System.out.print(data + " ");
            if (left != null) left.firstRoot();
            if (right != null) right.firstRoot();
        }
    
        public void midRoot() {
            if (left != null) left.midRoot();
            System.out.print(data + "->");
            if (right != null) right.midRoot();
        }
    
        public void afterRoot() {
            if (left != null) left.afterRoot();
            if (right != null) right.afterRoot();
            System.out.print(data + "->");
        }
    }
    
    public class Tree {
        TreeNode root;
        public void add(int n) {
            TreeNode node = new TreeNode(n);
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        public void first() {
            root.firstRoot();
            System.out.println();
        }
    
        public void mid() {
            root.midRoot();
            System.out.println();
        }
    
        public void after() {
            root.afterRoot();
            System.out.println();
        }
    }
    
    展开全文
  • 先根遍历

    千次阅读 2015-03-28 22:44:14
    /*先根遍历兄弟*/ } } /* void RootFirst(CSTree root) { CSNode *p; if (root!=NULL) { printf("%c ",root->data); / * 访问根结点 * / p= root->FirstChild; while (p!=NULL) { RootFirst(p)...
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char DataType;
    
    typedef struct CSNode
    {
    	DataType  data;                  /*结点信息*/
    	struct CSNode  *FirstChild;      /*第一个孩子*/
    	struct CSNode  *Nextsibling;     /*下一个兄弟*/
    }CSNode, *CSTree;
    
    CSNode *find(CSNode *root, char value)
    {
    	CSNode *q;
    	if(root == NULL)
    		return (NULL);
    	else
    		if(root->data == value)
    			q=root;
    		else
    		{
    			q = find(root->FirstChild,value);
    			if(q == NULL)
    				q = find(root->Nextsibling,value);	
    		}
    	return q;
    }
    
    CSNode * create()
    {
    	char pvalue,cvalue;
    	int i;
    	int type;
    	CSNode *p,*q,*s,*head;
    	i=1;
    	printf("请输入建立树序列(以$表示结束)!\n");
    	printf("第%d个结点=>根结点值:",i);
    	i++;
    	scanf("%c",&cvalue);
    	if(cvalue != '$')
    	{
    		head=(CSNode *)malloc(sizeof(CSNode));
    		head->data = cvalue;
    		head->FirstChild = NULL;
    		head->Nextsibling = NULL;
    	}
    	else
    		return (NULL);
    	do
    	{
    		printf("第%d个结点=>结构关联父结点值:",i);
    		i++;
    		fflush(stdin);
    		scanf("%c",&pvalue);
    		if(pvalue != '$')
    		{
    			do 
    			{
    				printf("   孩子(0)或兄弟(1)结点:");
    				fflush(stdin);
    				scanf("%d",&type);				
    			} while(type!=0 && type!=1);
    			printf("        当前结点值为:");
    			fflush(stdin);
    			scanf("%c",&cvalue);
    			
    			p = head;
    			q = find(p,pvalue);
    			if (q!=NULL)
    			{
    				s=(CSNode *)malloc(sizeof(CSNode));
    				s->data = cvalue;
    				s->FirstChild = NULL;
    				s->Nextsibling = NULL;
    				if(type == 0)
    					q->FirstChild = s;
    				if(type == 1)
    					q->Nextsibling = s;
    			}
    			else
    			{
    				printf("已建立的树中没有此结点!\n");
    				i--;
    			}			
    		}
    	}while(pvalue != '$');
    	return (head);
    }
    
    void  RootFirst(CSTree  root) 
    {
    	if (root!=NULL)
    	{
    		printf("%c  ",root->data);           /*访问根结点*/
    		RootFirst (root->FirstChild);   /*先根遍历首子树*/
    		RootFirst (root->Nextsibling);  /*先根遍历兄弟树*/
    	}
    }
    
    /*
    void  RootFirst(CSTree  root) 
    { 
    	CSNode *p;
    	if (root!=NULL)
    	{
    		printf("%c  ",root->data);        / * 访问根结点 * /
    		p= root->FirstChild;
    		while (p!=NULL)
    		{
    			RootFirst(p);      / * 访问以p为根的子树 * /
    			p = p->Nextsibling;
    		}
    	}
    }*/
    
    
    int main()
    {
    	CSTree ct;
    	int layer;
    	layer = 0;
    	ct = create();
    	RootFirst(ct);
    	printf("\n");
    }

    展开全文
  • 数据结构中最爱考的题型已知后、中先根或已知先根、中求后

    题一:

    已知一棵树二叉树的 后根遍历 和 中根遍历 的序列分别为: ACDBGIHFE 和 ABCDEFGHI,

    请画出该二叉树,并写出它的先根遍历的序列

    答:

    先根遍历序列:EBADCFHGI

    解题思路:

    我们先找到根

      后根:左  右  根                                         中跟:左  根   

     ACDB    GIHF   E                                           ABCD   E    FGHI

    我们先从后根去找,这个根一定是在这个遍历的后面,我们就可以确定E是根

    然后我们在中根遍历中找到E的位置,所以E的左边就是左指数节点,右边是右指数节点

    现在最上面的数E确定了,那谁是E左指数上的根呢,谁在后面谁是根:是B

    然后再看中根遍历,谁在B的左边谁是左指数:是A;于是:

    现在在左指数上只有C和D没有画出来,

    看中根遍历得到:C和D在B的右边,看后根遍历知道D在后面,所以D是根,

    在中根遍历中,C在D的左边,所以C是D的左指数;

    于是:以E为根节点的左指数画完

    接下来看看以E为根节点的右指数,先在后根遍历中找根节点,谁在后面谁是根节点:是F

    再到中根遍历中找到F位置,F左边画完了,所以没有左指数,再看右边:GHI

    回到后根遍历看GHI,得知H是根节点,所以:

    现在只剩G、I 没有画了,所以回到中根遍历中看到G在H左,I 在H右,所以:

    如果想知道画的对不对,带进题干,看看他的后根遍历和中根遍历对不对就行了

    题二:

    已知一棵树二叉树的先根遍历和中根遍历的序列分别为:ABDGHCEFI和GDHBAECIF,

    请画出此二叉树,并写出它的后根遍的序列

    构造的二叉树如下

    后根遍历序列: GHDBEIFCA

    解题思路:
    首先先找根

    先根: 根      右                              中根: 左  根   

            A    BDGH    CEFI                          GDHB   A   ECIF

    看先根遍历得知A是根,然后在中根遍历中找到A的位置

    所以得知GDHB在A的左边,ECIF在A的右边

    那GDHB是谁根呢?回到先根遍历中,谁在前面谁是根,得知是B

    再看中根,GDH在B的左边,那就是B的左指数

    那GDH种谁是根呢?看先根中,D在前,那D就是根

    再去中根遍历中找D的位置,得知左是G,右是H

    现在以A为根节点的左指数已全部找到,那右指数就是ECIF

    回到先根遍历中,那这四个谁在前面谁是根,是C

    再去中根遍历中找C的位置,E在C的左边(左指数),I F在C的右边(右指数)

    那 I F谁是根呢?去先根遍历中找:F在前,F是根

    中根遍历中 I 在 F 左,于是 I 是F的左指数 

    展开全文
  • 非递归先根遍历二叉树 当栈不为空或者当前节点为不为空,执行操作: 从根节点开始,依次访问中最左端的节点并入栈,当节点为空停止入栈。 取栈顶元素为当前节点并出栈,如果当前节点有右子,则遍历其右子。 ...
  • 森林()的括号表示法←→森林()←→二叉树←→遍历序列 ↓ 遍历序列
  • 答: 能确定,先根遍历和后根遍历对应二叉树的先序遍历和中序遍历。由二叉树的先序遍历和中序遍历可唯一确定一颗二叉树,二叉树可唯一变换为
  • 二叉树先根次序遍历、中次序遍历、后次序遍历
  • 根遍历先根遍历/后根遍历构建二叉树

    万次阅读 多人点赞 2017-04-12 22:34:34
    1问题 给定二叉树的2个遍历序列(如先根+中先根+后,中...因为先根/后可以确定二叉树根节点是哪个,而中可以将二叉树分为节点和其左子树和其右子,进而可以将先根/后分成"+左子树先根+右子树先根
  • //先根遍历右子 } } //中根遍历二叉树的递归算法 public void inRootTraverse(BiTreeNode T) { if(T!=null) { inRootTraverse(T.lchild); //中根遍历左子树 System.out.print(T.data); //访问根...
  • 经典的二叉树的根、中根和后根遍历序列题

    千次阅读 热门讨论 2022-04-06 17:16:37
    根、中根和后序根遍历序列
  • 二叉树的先根遍历

    千次阅读 2017-03-03 11:00:28
    二叉树的先根遍历面试时,经常问道类似与,获取某一文件夹下所有文件和文件夹;二叉树遍历等问题。 这是一类问题,以二叉树的先根遍历举例:递归实现public class Test { /** * 二叉树节点类 */ public static ...
  • 多叉遍历

    千次阅读 2020-06-22 21:28:17
    429. N叉的层序遍历 给定一个 N 叉,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明: 的深度不会超过 1000。 的节点总数不会超过 5000。 class ...
  • 遍历

    2021-01-06 22:46:13
    目录的静态写法先根遍历树的层次遍历从的遍历看DFS和BFS深度优先搜索(DFS)与先根遍历广度优先搜索(BFS)与层序遍历题型训练参考文档 的静态写法 一般意义上的“”与“二叉树”不太一样,它的子结点的...
  • 根,中根,后根遍历

    万次阅读 多人点赞 2018-06-08 16:17:00
    先序遍历(根)是访问当前节点,然后再...一棵二叉树的先根遍历为ABCDEFG,中根遍历为CBDEAGF,则其后根遍历为多少? 方法:(层层解剖,集合从大到小,递归分析) (无论如何必须分析根,确定父节点,再...
  • 二叉树根、中根、后根遍历

    万次阅读 多人点赞 2017-10-14 17:39:19
    二叉树根、中根、后根遍历 先根遍历: ABCDEFGH 中根遍历:CBEDFAGH 后根遍历 : CEFDBHGA
  • 解题 来解题 这题 其实用试的是很快的~ 还是用这个例子 【1】普通的后序遍历 后序遍历 左右中(左后 右后 )—— 翻译得详细些就是—— 最开始 遍历到(还有左子树的)最深处的节点 【1】访问该节点的左子树 2...
  • 文章目录[总结] 二叉树、、森林三者遍历...从左到右对森林中的每一棵进行【先根遍历】 中序遍历 第二次经过结点的时候访问 的度不一定,一般不说中序遍历,但非要谈,请看下面的分析 森林的中序、后序,只...
  • //由根和中根遍历建立二叉树 public class bitree{  public bitree(String preorder,String inorder,int preindex,int inindex,int count){  if(count>0){ //根中根为空  char r=preorder.char
  • -遍历(先序、中序、后序)

    千次阅读 2022-03-11 21:25:34
    先序遍历,也叫先根遍历、前序遍历,首先访问根结点然后遍历左子树,最后遍历右子。在遍历左、右子时,仍然访问根结点,然后遍历左子树,最后遍历右子,如果二叉树为空则返回。可以简记为根左右。 以上图为...
  • 1、 构建二叉排序,并进行中序和后遍历 【问题描述】 构建二叉排序,并进行中序和后遍历。1,结点的权值为int型 【输入形式】 输入n个结点,其为整数 【输出形式】 二叉排序的中序和后遍历...
  • 访问左子树A,那么接下来要访问的点是B,还是R,是有歧义的,所以普通没有中序遍历 2.为什么为什么森林没有后序遍历 以下图为例: 森林的先序遍历规则: (森林非空) 1.访问森林中第一颗结点 2.先序遍历...
  • 【数据结构】遍历、森林的遍历

    多人点赞 热门讨论 2022-05-20 21:30:25
    遍历的一种重要的运算。所谓遍历是指对中所有结点的信息的访问,即依次对中每个结点访问一次且仅访问一次。...可被看成是由结点和结点的所有子树所构成的森林两部分组成。 ​
  • 递归,循环-先根遍历

    千次阅读 2019-08-30 02:56:53
    递归可以用栈存储,转化为循环 非递归: 递归:
  • 由标明空子的先序遍历序列创建二叉树 i=0 def createBiTree2(preOrder): # i为常数0 global i c = preOrder[i] # 取字符 if c != '#': root = BiTreeNode(c) i += 1 root.lchild = createBiTree2...
  • 首先我们要清楚基本概念,前、中、后序遍历中的前、中、后指代的是、左节点、右节点之间的遍历顺序。 前序遍历遍历顺序为左右 中序遍历遍历顺序为左右 后序遍历遍历顺序为左右 那么对下图而言,...
  • 和森林的遍历

    千次阅读 2020-02-20 09:56:24
    先根遍历访问的根结点,然后再依次先根遍历根的每棵子树。 后根遍历依次遍历每棵子树,然后再访问根结点。 先根遍历结果:ABEFCGDHIJ 后根遍历结果:EFBGCHIJDA 2.森林的遍历 森林的遍历也分为前序遍历和...
  • c语言——遍历

    千次阅读 2022-03-19 20:07:32
    的三种遍历方式,分别是,先序遍历左右,中序遍历:左右,后序遍历:左右。然后需要创建链表,存放结点和左右孩子。 递归遍历: #include<stdio.h> #include<stdlib.h> struct bitnode {...
  • 1.先根遍历(若非空) 访问根结点,再依次访问根结点的每棵子树。遍历的时候也需要遵循根后子树的规则。相当于二叉树的先序遍历。 2.后根遍历(若非空) 依次访问根结点的每棵子树,再访问根结点。遍历...
  • 数据结构——和森林的遍历方法

    千次阅读 多人点赞 2017-10-15 12:22:51
    的遍历主要有先根遍历和后根遍历。 2、(1)先根遍历:若非空,则访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵对应的二叉树的先序遍历顺序相同。 (2)后根遍历:若非空...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 260,141
精华内容 104,056
关键字:

树的先根遍历