精华内容
下载资源
问答
  • 根据前序遍历和中序遍历建立二叉树 1. 递归法: 先序遍历:根节点→左子树→右子树。 中序遍历:左子树→根节点→右子树。 后续遍历:左子树→右子树→根节点。 根据前序遍历和中序遍历建立二叉树,根据以上性质可知...

    根据前序遍历和中序遍历建立二叉树

    1. 递归法:
    先序遍历:根节点→左子树→右子树。
    中序遍历:左子树→根节点→右子树。
    后续遍历:左子树→右子树→根节点。

    根据前序遍历和中序遍历建立二叉树,根据以上性质可知:

    前序遍历首个元素为二叉树的根节点root;
    根据前序遍历找到中序遍历中的root的索引位置,可以将中序遍历分为【左子树|根节点|右子树】;
    根据中序遍历的左/右子树可以将前序遍历分为【根节点|左子树|右子树】。
    

    递推参数: 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right

    终止条件:left > right ,代表已经越过叶节点,此时返回 null

    递推工作:

    建立根节点 node : 节点值为 preorder[root]
    划分左右子树: 查找根节点在中序遍历 inorder 中的索引 i ;
    为了提升效率,本文使用哈希表 dic 存储中序遍历的值与索引的映射,查找操作的时间复杂度为 O(1);

    构建左右子树: 开启左右子树递归;

    根节点索引中序遍历左边界中序遍历右边界
    左子树root + 1lefti-1
    右子树root+i-left+1i+1right

    i - left + root + 1含义为 根节点索引 + 左子树长度 + 1

    返回值: 回溯返回 node ,作为上一层递归中根节点的左 / 右子节点;

    代码:

    class Solution {
        int[] preorder;
        HashMap<Integer, Integer> dic = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++)
                dic.put(inorder[i], i);
            return recur(0, 0, inorder.length - 1);
        }
        TreeNode recur(int root, int left, int right) {
            if(left > right) return null;                          // 递归终止
            TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
            int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
            node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
            return node;                                           // 回溯返回根节点
        }
    }
    
    展开全文
  • 题目: 根据先序遍历和中序遍历建立二叉树的二叉链表 并输出后序序列 思路: 根据先序序列确定根节点 在中序序列中找到根节点,将中序序列分成两段,前半段为根节点的左子树的中序序列,后半段为右子树的中序序列 ...

    题目: 根据先序遍历和中序遍历建立二叉树的二叉链表 并输出后序序列

    思路:

    1. 根据先序序列确定根节点
    2. 在中序序列中找到根节点,将中序序列分成两段,前半段为根节点的左子树的中序序列,后半段为右子树的中序序列
    3. 递归直到每颗子树只有一个结点。

    示例:

        	  A 
            /   \
           B     C		先序序列:'A','B','D','E','C','F'
          / \   /   	中序序列:'D','B','E','A','F','C'
         D   E F		
    //输出结果:
    D
    E
    B
    F
    C
    A
    

    代码实现:

    
    #include <iostream>
    using namespace std;
    
    typedef struct treenode{
        char data;
        struct treenode *lchild,*rchild;
    
    }treenode, *tree;
    
    int pos = 0;
    tree build(char a[],char b[],int s,int e){
        if(s<=e){
            treenode *root = (treenode *)malloc(sizeof(treenode));
            root->data=a[pos];
            pos++;
            int i;
            for(i = s;i<=e;i++) if(b[i]==root->data) break;
            root->lchild = build(a,b,s,i-1);
            root->rchild = build(a,b,i+1,e);
            return root;
        }
        return NULL;
    }
    
    void outs(tree t){
        if(t){
            outs(t->lchild);
            outs(t->rchild);
            cout<<t->data<<endl;
        }
    }
    int main()
    {
        char A[] = {'A','B','D','E','C','F'};
        char B[] = {'D','B','E','A','F','C'};
        tree root=build(A,B,0,5);
        cout<<"后序序列为:"<<endl;
        outs(root);
        return 0;
    }
    
    
    /*
              A 
            /   \
           B     C
          / \   /   
         D   E F
    */
    
    展开全文
  • title: 根据先序遍历和中序遍历建立二叉树 date: 2019-07-23 22:37:34 tags: 数据结构 问题 已知一棵二叉树的先序遍历以及中序遍历,重建二叉树。二叉树的每一个节点有三个属性,左子节点,右子节点,以及...
    title: 根据先序遍历和中序遍历建立二叉树
    date: 2019-07-23 22:37:34
    tags: 数据结构
    

    问题

    已知一棵二叉树的先序遍历以及中序遍历,重建二叉树。二叉树的每一个节点有三个属性,左子节点,右子节点,以及节点值。

     

    思路

    先序遍历服从规则“根左右”,所以由此可知,对于一个先序遍历得到的数组,第一个元素一定是根节点

    中序遍历服从规则”左根右“,所以由此可知,对于一个中序遍历得到的数组,根节点左边的元素都属于根节点的左子树,而根节点右边的元素都属于根节点的右子树

    所以,我们可以先通过先序遍历的第一个元素确定根节点,然后通过中序遍历结合根节点,获得当前根节点的左右子树,再将子树看成一棵独立的树,继续使用先序遍历判断根节点,中序遍历判断子树的方式,最终建立起整棵树;

     

    例子

    假设有一棵二叉树,先序遍历为{1,2,4,7,3,5,6,8},中序遍历为{4,7,2,1,5,3,8,6},则建树过程如下:

    首先,通过先序遍历可知树的根节点为1,则在中序遍历中,1左边的元素4,7,2即为根的左子树的元素,而1右边的元素5,3,8,6即为根节点的右子树;

    对于左子树4,7,2来说,在先序遍历中,这三个点的顺序为2,4,7,则2为根节点,而在中序遍历中,4,7均在2的左边,则4,7均为以2为根树的左子树,且没有右子树;

    对于4,7这两个节点来说,先序遍历中,4节点在7节点之前,所以4为根节点,而7作为子树,在中序遍历中,74之后,所以7为右子树;

    对于根节点1的右子树5,3,8,6来说,在先序遍历中,3在最前面,所以3为这棵子树的根节点,而在中序遍历中,53的左边,所以属于左子树,而8,63的右边,属于右子树;

    对于根节点3的右子树8,6,在先序遍历中,68之前,所以,6又为根节点,而在中序遍历中,86的左边,所以86的左子节点;

    至此,二叉树便重建完成;

     

    代码

    树的节点

    1 public class TreeNode {
    2     int val;        //当前节点的值
    3     TreeNode left;    //左子节点
    4     TreeNode right;    //右子节点
    5 
    6     TreeNode(int x) {
    7         val = x;
    8     }
    9 }

     

    建树方法

     1 /**
     2 * pre:线序遍历得到的数组
     3 * in:中序遍历得到的数组
     4 */
     5 public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
     6     if(pre.length == 0) {
     7         return null;
     8     }
     9 
    10     int root = pre[0];
    11     TreeNode node = new TreeNode(root);
    12 
    13     //寻找根节点在in中的索引
    14     int i = 0;
    15     for( ; i<in.length; ++i) {
    16         if(in[i] == root) {
    17             break;
    18         }
    19     }
    20 
    21     //建立左子树
    22     int[] leftIn = Arrays.copyOfRange(in, 0, i);
    23     int[] leftPre = Arrays.copyOfRange(pre, 1, i+1);
    24     node.left = reConstructBinaryTree(leftPre, leftIn);
    25 
    26     //建立右子树
    27     int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);
    28     int[] rightPre = Arrays.copyOfRange(pre, i+1, pre.length);
    29     node.right = reConstructBinaryTree(rightPre, rightIn);
    30 
    31     return node;
    32 }
     

    建树代码(优化)

     1 public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
     2     return getRootTreeNode(pre, 0, pre.length-1, in, 0, in.length-1);
     3 }
     4 
     5 /**
     6 * preL:当前子树在先序遍历的数组中的起始下标
     7 * preR:当前子树在先序遍历的数组中的结束下标
     8 * inL:当前子树在中序遍历的数组中的起始下标
     9 * inR:当前子树在中序遍历的数组中的起始下标
    10 */
    11 public TreeNode getRootTreeNode(int[] pre, int preL, 
    12                                 int preR, int[] in, int inL, int inR) {
    13     if(preL > preR) {
    14         return null;
    15     }
    16 
    17     TreeNode node = new TreeNode(pre[preL]);
    18 
    19     for(int i=inL; i<=inR; ++i) {
    20         if(in[i] == pre[preL]) {
    21 
    22             node.left = getRootTreeNode(pre, preL+1, preL+i-inL, in, inL, i-1);
    23             node.right = getRootTreeNode(pre, preL+i-inL+1, preR, in, i+1, inR);
    24             break;
    25         }
    26     }
    27 
    28     return node;
    29 }

     

    转载于:https://www.cnblogs.com/tuyang1129/p/11235173.html

    展开全文
  • 先序遍历和中序遍历建立二叉树,并且以后续遍历输出二叉树 假设先序遍历为:abcdefghi(根 左 右) 中序遍历为:bcaedghfi (左 根 右) 首先在先序遍历中可以确认a为根节点 在中续遍历中可以看到bc(初始位置为b...

    先序遍历和中序遍历建立二叉树,并且以后续遍历输出二叉树

    假设先序遍历为:abcdefghi(根 左 右)
    中序遍历为:bcaedghfi (左 根 右)

    1. 首先在先序遍历中可以确认a为根节点
    2. 在中续遍历中可以看到bc(初始位置为b(长度为2))a 的左子树 edghfi(初始位置为e长度为6)a的右子树
    3. 同时注意前序序列中a左子树的初始位置为b(长度为2),右子树的初始位置为e长度为6;
    4. 递归调用求a的左子树的全部,递归调用求a的右子树
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node{
    	char data;
        struct node *lchild,*rchild;
    }node,*tree;
    tree creat(char *a,char *b,int n)
    {
    	tree t;
    	//char a[0]=a;
    	int i=0,len;
    	if(n<=0) return;
    	 t=(tree)malloc(sizeof(node));
    	 t->data=a[0];
    	 while(b[i]!=a[0])
    	 {
    	 	i++;
    	 
    	 	
    	 }
    	 len=n-i-1;
    	 t->lchild=creat(a+1,b,i);
    	 t->rchild=creat(a+i+1,b+i+1,len);
    	 printf("%c",t->data);
    	 return t;
    	
    	
    	
    }
    int main()
    {
    	char a[20],b[20];
    	tree t;
    		int n;
    		printf("请先输入长度/n");
    		n=scanf("%d",&n);
    	printf("请先输入先序序列/n");
    	scanf("%s",a);
    	printf("请输入中序序列/n");
    	scanf("%s",b);
    	creat(a,b,n);
    	return 0;
    	
     } 
    
    展开全文
  • 假设现在有某二叉树的先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列 分别以左子树和右子树为新树进行第一步操作 直至没有子树为止 那么我们...
  • 根据前序遍历,我们可以确定该二叉树的根节点为A,再通过中序遍历中A的位置,可以确定DGB为该二叉树的左子树,ECF为右子树 根据这个逻辑,每次在前序遍历中读取一个节点,再在中序遍历中找到他所在的位置,便可以...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 ...
  • 题目描述 二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟... 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定 前序遍历与中序遍历能够唯一确定后序遍历)。 输入 两个
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。二叉树结点的定义如下: typedef struct BtNode { struct BtNode* leftchild; struct ...
  • 已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历? 对一棵二叉树进行遍历,我们可以采取3中顺序进行遍历,分别是前序遍历、中序遍历和后序遍历。这三种方式是以访问父节点的顺序来进行命名的。假设父节点是N...
  • 根据前序中序遍历建立二叉树(2009-03-20 20:15:28) 【前言】 这个选题源自课上的一个习题,题目提供了二叉树的前序遍历和中序遍历,要求出整个二叉树。刚一做这道题时,还有些迷惑。但是,既然答案是...
  • 学过数据结构的应该都知道,根据先序遍历和中序遍历可以唯一确定一颗二叉树二叉树是递归定义的数据结构,所以一般的操作都是递归完成的,所以建树的过程也不例外,先来看这样两道题 题目一 :...
  • 这里关注前序遍历和中序遍历中,左子树和右子树的切分点 #include <cstdio> #include <iostream> #include <string> #include <queue> using namespace std; void visit(char c){ cout&...
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数NN(\le 30≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。...
  • 不管是二叉树建立 求前遍历 后遍历 还是层次遍历,都是利用中序遍历的性质 和一个前序遍历或后序遍历,讲一个节点的左支所有的数,右支所有的数,和该节点的数分开,然后根据题目重新排序; 前序遍历:该节点的...
  • BinaryTreeNode * CreateBinaryTree(ElemType * pre, ElemType *in, int length)//此种建立二叉树的方法本质上是先建立根结点 再建立左子树,再建立右子树 { if (length || pre == NULL || in == NULL)////递归...
  • ``` #include #include #include #define maxsize 50 typedef struct Bnode { char data; struct Bnode *Lchild, *Rchild; }BTnode, *BTptr; BTptr CreateBT(char *pre_str, char *in_str) ...```
  • 建立二叉树,前后中序遍历二叉树,求二叉树的深度
  • (2)根据前序遍历和中序遍历建立二叉树的思路是:前序遍历依次每一个节点对应一个子树,这个节点在中序遍历中找到它相应的位置,它的左边(当然是在子树数组范围内)就是左子树的顶点,右边就是右子树的顶点。
  • 二叉树的遍历 我们知道知道 前序遍历 + 中序遍历 --------------- 可以确定唯一一棵二叉树 后序遍历 + 中序遍历 --------------- 可以确定唯一一颗二叉树 ...根据前序遍历和中序遍历重建二叉树 ...
  • https://www.cnblogs.com/grandyang/p/4296500.html
  • 已知后序序遍历序列和中序遍历序列建立二叉树。 例如输入后序遍历序列: FGDBCA, 再输入中序遍历序列: BFDGAC,则 输出该二叉树的先序遍历序列: ABDFGC。具体过程和上一个文章里的先序和中序确定二叉树一样不明白...
  • 中序遍历线索二叉树

    2018-11-18 19:35:41
    中序遍历线索二叉树的实现与操作二叉线索树的结构定义创建一棵二叉树创建一棵二叉树二叉树基本操作中序遍历二叉树线索化的递归算法通过中序遍历建立中序线索二叉树中序遍历主函数测试 二叉线索树的结构定义 ...
  • 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder =[3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / ...
  • 已知先序遍历序列和中序遍历序列建立二叉树。 例如输入先序遍历序列: ABDFGC, 再输入中序遍历序列: BFDGAC,则 输出该二叉树的后序遍历序列: FGDBCA。解析:函数中的三个参数,第一个是先序,第二个是后序,第三...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,466
精华内容 9,386
关键字:

中序遍历建立二叉树