精华内容
下载资源
问答
  • 根据给定的序列构建/判断二叉树
    2016-06-22 15:51:02

    1.输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

    思路:从最简单的树来想,建造一棵二叉树就是先找到根,然后建立左子树然后建立右子树,当给出的是遍历的数组时,可以根据遍历特点知道根节点,在先序遍历中,根节点总是第一个,然后在中序遍历中找到这个根节点,左边的是左子树,右边是右子树。对于复杂的二叉树这就是一个递归过程。

    由于先序遍历的数组我需要一直往后遍历,我用队列的方式每次弹出第一个已经找到的根节点,中序遍历的数组我需要保存每次划分的数组的子数组,但是java对数组时传址的,所以就用Arrays.copyOfRange(in,0,temp)这个函数。(还学习到:java中队列的实现类是linklist,将数组初始化到队列中有2个方法:①Queue<Integer>queue=new LinkedList<>(Arrays.asList(ppre));//这样的构造函数需要传入一个collection<?extends E> c,即c是y一个集合类,元 素继承E(这里是Integer
    ②Queue<Integer>queue=new LinkedList<>(); //分两步构造,如果不是实现类不是链表而是数组,则需要传入一个长度

    Collections.addAll(queue, ppre)

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    import java.util.*;
    public class Solution {
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
           Queue<Integer>queue=new LinkedList<>();
    		Integer[] ppre=new Integer[pre.length];
    		for(int i=0;i<ppre.length;i++){
    			ppre[i]=pre[i];
    		}
    		
    		Collections.addAll(queue, ppre);
            return reConstructBinary(queue,in);
        }
        public TreeNode reConstructBinary(Queue<Integer>pre,int []in) {
        	
           int val=0;
           if(pre.size()>0){
        	  val =pre.poll();
           }
           
           if(in.length<1||in==null) return null;
           
            TreeNode root=new TreeNode(val);
            
            root.left=null;
            root.right=null;
            int temp=0;
            for(int i=0;i<in.length;i++){
                if(val==in[i]){
                    temp=i;
                    break;
                }
            }
           
            //左子树
            if(temp>0){
            	
                root.left=reConstructBinary(pre,Arrays.copyOfRange(in,0,temp));
            }
            
            //右子树
            if(temp<in.length-1){
            	
                root.right=reConstructBinary(pre,Arrays.copyOfRange(in,temp+1,in.length));
            }
            
            return root;
        }
    }

    2.输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果,假设输入的数组的任意两个数字都互不相同。找到根,在数组中找到第一个比根大的节点,这个节点后面的节点都要比根节点大(相当于右子树)。

    import java.util.*;
    public class Solution {
        public boolean VerifySquenceOfBST(int [] sequence) {
            
       	if(sequence==null||sequence.length==0)
                return false;
            int root=sequence[sequence.length-1];
            int i=0;
            for(;i<sequence.length-1;i++){
                if(sequence[i]>root){
                    break;
                }
            }
            int j=i;
            for(;j<sequence.length-1;j++){
                if(sequence[j]<root)
                    return false;
            }
            boolean left=true;
            boolean right=true;
            if(i>0){
    <span style="white-space:pre">	</span>//判断左子树
                left=VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
            }
            if(i<sequence.length-1){
    <span style="white-space:pre">	</span>//判断右子树
                right=VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length-1));
    <span style="white-space:pre">	</span>}
            return (left&&right);
        }
     
    }

    更多相关内容
  • 通过序列构建二叉树

    千次阅读 2018-01-11 15:38:34
    重构二叉树一、已知二叉树的先序序列和中序序列重建二叉树 示意图:根据示意图可以得到如下代码: node* create(int preL,int preR,int inL,int inR){ if(preL > preR){ return NULL;//先序序列的长度小于等于0时,...

    重构二叉树

    一、已知二叉树的先序序列和中序序列重建二叉树

    1. 示意图:

    1. 根据示意图可以得到如下代码:
    
        node* create(int preL,int preR,int inL,int inR){
            if(preL > preR){
                return NULL;//先序序列的长度小于等于0时,直接返回
            }
            node* root = new node;      //新建一个结点,用来存放当前二叉树的根节点
            root->data = preArr[preL];  //新结点的数据域为根结点的值
            int k;
            for(k = inL;k <= inR;k++){
                if(preArr[preL] == inArr[k]){    //在中序序列中找到inArr[k] == preArr[preL]的结点
                    break;
                }
            }
            int numLeft = k - inL;              //左子树的结点个数
    
            //左子树的先序区间为[preL+1,preL+numLeft],中序区间为[inL,k-1]
            //返回左子树的根结点地址,赋值给root的左指针
            root->lchild = create(preL+1,preL+numLeft,inL,k-1);
    
            //右子树的先序区间为[preL+numLeft+1,preR],中序区间为[k+1,inR]
            //返回右子树的根结点地址,赋值给root的右指针
            root->rchild = create(preL+numLeft+1,preR,k+1,inR);
    
            return root;        //返回根结点的地址
        }
    

    二、已知二叉树的后序序列和中序序列重建二叉树

    思想同上,只不过在后序序列中最后一个结点才是二叉树的根结点

    示例代码:

    
        node* create(int postL,int postR,int inL,int inR){
            if(postL > postR){
                return NULL;
            }
            node* root = new node;
            root->data = postArr[postR];
            int k;
            for(k = inL;k <= inR;k++){
                if(inArr[k] == postArr[postR])  break;
            }
            int numLeft = k - inL;
            root->lchild = create(postL,postL+numLeft-1,inL,k-1);
            root->rchild = create(postL+numLeft,postR-1,k+1,inR);
            return root;
        }
    

    三、总结

    要构建一个二叉树必须给出中序序列,中序序列可以与先序序列、后序序列、层次序列中任意一个来构建唯一的二叉树;但后三者两两搭配或是三个一起都无法构建唯一的二叉树。原因是先序、后序、层序均是提供根结点,作用是相同的都必须由中序序列来区分出左右子树。

    通过先序序列和中序序列构建二叉树的整个程序示例代码:

    
        #include <iostream>
        using namespace std;
        const int maxn = 1000 + 5;
        int preArr[maxn] = {1,2,4,5,3,6}; //先序序列
        int inArr[maxn] = {4,2,5,1,6,3};  //中序序列
        typedef struct node{
            int data;
            node* lchild;
            node* rchild;
        };
        node* create(int preL,int preR,int inL,int inR){
            if(preL > preR){
                return NULL;//先序序列的长度小于等于0时,直接返回
            }
            node* root = new node;      //新建一个结点,用来存放当前二叉树的根节点
            root->data = preArr[preL];  //新结点的数据域为根结点的值
            int k;
            for(k = inL;k <= inR;k++){
                if(preArr[preL] == inArr[k]){    //在中序序列中找到inArr[k] == preArr[preL]的结点
                    break;
                }
            }
            int numLeft = k - inL;              //左子树的结点个数
    
            //左子树的先序区间为[preL+1,preL+numLeft],中序区间为[inL,k-1]
            //返回左子树的根结点地址,赋值给root的左指针
            root->lchild = create(preL+1,preL+numLeft,inL,k-1);
    
            //右子树的先序区间为[preL+numLeft+1,preR],中序区间为[k+1,inR]
            //返回右子树的根结点地址,赋值给root的右指针
            root->rchild = create(preL+numLeft+1,preR,k+1,inR);
    
            return root;        //返回根结点的地址
        }
        void postOrder(node* root){         //后序遍历
            if(root){
                postOrder(root->lchild);
                postOrder(root->rchild);
                cout<<root->data<<" ";
            }
        }
    
        int main(void){
            node* root = create(0,5,0,5);
            cout<<"后序序列为:";
            postOrder(root);        //输出后序序列,观察二叉树构建是否正确
            cout<<endl;
            return 0;
        }
    
    
    

    画出此时的二叉树:

    后序序列:4 5 2 6 3 1

    程序结果:

    PAT上有一道类似的题:
    PAT1020

    展开全文
  • 二叉树构建及基础操作


    二叉树的存储结构主要有二叉链表和数组,根据不同的遍历结果可以构建二叉树(一定要有中序遍历结果)

    构建二叉树

    扩展先序序列构建二叉树

    ‘#’代表虚结点

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define  ElemType char
    
    typedef struct BiNode{
        ElemType data;
        struct BiNode *lchild, *rchild;
    }BiNode,*BiTree;
    
    void InitBiTree (BiTree *BT);
    void CreatBiTree (BiTree *BT);//二级指针
    void InOrderTraverse (BiTree BT);
    int main (void) {
        BiTree BT;
        InitBiTree (&BT);
        CreatBiTree (&BT);
        InOrderTraverse (BT);
        printf ("\n");
        return 0;
    }
    
    void InitBiTree (BiTree *BT) {
        (*BT) = NULL;
    }
    
    void CreatBiTree (BiTree *BT) {
        ElemType ch;
        ch = getchar();
        if (ch == '#') (*BT) = NULL;
        else {
            (*BT) = (BiTree)malloc(sizeof(BiNode));
            (*BT)->data = ch;
            CreatBiTree(&(*BT)->lchild);//依然要用二级指针
            CreatBiTree(&(*BT)->rchild);
            }
    }
    

    先序和中序遍历序列构建二叉树

    BiTree CreatBT (ElemType *pre, ElemType *in, int n) {
        BiTree s;
        ElemType *p;
        int k;
        if (n == 1) {
            s = (BiTree)malloc(sizeof(BiTNode));
            s->data = *pre;
            s->lchild = NULL;
            s->rchild = NULL;
    
            return s;
        }
    
        for (p = in; p < in + n; p++){
            if (*p == *pre) break;
        }
    
        k = p - in;
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = *pre;
        s->lchild = NULL;
        s->rchild = NULL;
        if (k) s->lchild = CreatBT (pre + 1, in, k);
        if (n - k -1) s->rchild = CreatBT (pre + k + 1, p + 1, n - k - 1);
        return s;
    }
    

    层次遍历及中序遍历构建二叉树

    参考这位的思路层次遍历和中序遍历构建二叉树。我个人因为先写的先序和中序序列构建二叉树,思维有些固化,而层次遍历和先序遍历在左右递归建立左右子树这个地方有蛮大的区别,需要多琢磨。

    BiTree CreatTree (ElemType *layer, ElemType *in, int lay1, int lay2, int in1, int in2) {
        if (in1 > in2) {
            return NULL;
        }
        BiTree T;
        T = (BiTree)malloc(sizeof(BiTNode));
        T->lchild = NULL;
        T->rchild = NULL;
    
        ElemType i, j;
        int flag = 0;
    
        for (i = lay1; i <= lay2; i++){
            for (j = in1; j <= in2; j++) {
                if (layer[i] == in[j]) {
                    flag = 1;
                    //printf ("%d %d %d\n",layer[i], in[j], i);
                    break;
                }
            }
            if (flag == 1) break;
        }
        T->data = layer[i];
        T->lchild = CreatTree (layer, in, lay1 + 1, lay2, in1, j - 1);
        T->rchild = CreatTree (layer, in, lay1 + 1, lay2, j + 1, in2);
        return T;
    }
    

    中序和后序遍历构建二叉树

    (肝完作业来补坑…)

    含虚结点的二叉树

    如abc@@de@#,#代表输入结束,@代表虚结点。
    (肝完作业来补坑…)

    二叉树的输出

    先判空再输出

    先序输出

    void PreOrderTraverse (BiTree T) {
        if (T) {
            printf ("%d ", T->data);
            PreOrderTraverse (T->lchild);
            PreOrderTraverse (T->rchild);
        }
    }
    

    中序输出

    void InOrderTraverse (BiTree BT) {
        if (BT) {
            InOrderTraverse (BT->lchild);
            printf ("%c ", BT->data);
            InOrderTraverse (BT->rchild);
        }
    }
    

    后序输出

    void PostOrderTraverse (BiTree T) {
        if (T) {
            PostOrderTraverse (T->lchild);
            PostOrderTraverse (T->rchild);
            printf ("%d ",T->data);
        }
    }
    

    叶子结点

    输出叶子结点

    void LeafNode (BiTree T) {
        if (T) {
            if (T->lchild == NULL && T->rchild == NULL) {
                printf ("%d ", T->data);
            }
            else {
                LeafNode (T->lchild);
                LeafNode (T->rchild);
            }
        }    
    }
    

    输出叶子结点个数

    判断条件同上,将输出改为计数。

    展开全文
  • 如何根据序列构建平衡二叉搜索树?什么是平衡二叉搜索树(AVL)?1、AVL树的定义2、AVL树的特点什么是右单旋转?什么是左单旋转?什么是双旋转?RR RL LR什么意思?实例题目过程 什么是平衡二叉搜索树(AVL)? 1、...

    什么是平衡二叉搜索树(AVL)?

    1、AVL树的定义

    AVL树又称平衡二叉搜索树,它能保证二叉树高度相对平衡,尽量降低二叉树的高度,提高搜索效率

    2、AVL树的特点

    (1)AVL的左右子树高度之差的绝对值不超过1
    (2)树中的每个左子树和右子树都是AVL树
    (3)每个节点都有一个平衡因子,任一节点的平衡因子只能是
    (-1、0、1)
    (每个节点的平衡因子等于右子树的高度减去左子 树的高度 )
    (4)平衡二叉树的高度和结点数量之间的关系也是O(logn)的
    在这里插入图片描述

    什么是右单旋转?

    在这里插入图片描述

    什么是左单旋转?

    在这里插入图片描述

    什么是双旋转?

    在这里插入图片描述

    RR RL LR什么意思?

    R:right缩写
    L:left缩写
    看自己旋转的情况判断
    不需要死记硬背
    只要能旋转满足平衡就行

    实例题目

    关键字序列(16,3,7,11,9,26,18,14,15)给出构造AVL树的构造过程

    过程

    第一步
    插入16,计算结点16的平衡因子
    平衡因子为0不需要调整、

    第二步
    插入3,3小于16插入右子树
    计算平衡因子为1
    不需要调整
    第三个结点7,比16小比3大
    插入3的右子树
    在这里插入图片描述

    失衡进行调整
    LR型调整。
    将7上升3作为7右子树16作为左子树
    在计算平衡因子
    都是0;

    第三步
    继续插入下一个结点
    插入11平衡
    继续
    在这里插入图片描述

    第四步
    插入9时失衡并且7失衡,16失衡
    找最小的失衡子树LL型
    将中间结点上升。
    在这里插入图片描述

    第五步
    插入26时
    计算平衡因子
    在这里插入图片描述
    RR型失衡
    在这里插入图片描述

    插入18RL型失衡
    在这里插入图片描述

    第六步
    平衡调整
    在这里插入图片描述

    第七步
    插入14平衡
    插入15
    在这里插入图片描述
    最后
    RL型调整
    在这里插入图片描述
    差最后一步自己变换一下
    我就不写了!加油

    展开全文
  • (2)在(1)的基础上,请编写一个函数(int LeafCount(Binary_tree BT)),求此二叉树的叶子结点个数。 有关的数据结构已描述如下:
  • 关键字序列1,2,3,4,5构造而得的二叉排序树 ASL=(1,2,3,4,5)/5=3 按关键字3,1,2,5,4构造而得的二叉排序树 ASL=(1+2+2+3+3)/5=2.2 很明显第二种序列的ASL要快。至于二叉排序树怎么构成的其实就是根据它的性质(若...
  • 对一个给定序列构建搜索二叉树

    千次阅读 2018-10-28 21:38:14
    对一个队列构建二叉搜索树,不要求平衡: 参考代码1:非递归 #include &lt;bits/stdc++.h&gt; using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x):...
  • 从前(或后)与中序序列构建二叉树 Leetcode 106. Construct Binary Tree from Inorder and Postorder Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal两道题是从前中后序列回复原二叉树...
  • 本篇文章以及代码参考其他博主的内容增加自己的注释完成,仅供学习交流 #include<cstdio> #include<iostream> #include<... //引入stl中的队列 ... //二叉树节点的数据域用字母表示 ...
  • 二叉排序树的定义、查找、插入、构建、删除、查找效率分析。
  • 二叉树构建

    千次阅读 2021-01-01 09:52:40
    文章目录什么是扩充二叉树扩充二叉树的前序遍历二叉树构建:前序 + 中序二叉树构建:后序 + 中序二叉树构建:层序 + 中序二叉树构建:扩充二叉树前序二叉树构建:扩充二叉树后序参考资料 先复习一下二叉树的遍历: ...
  • 由标明空子树的先序遍历序列创建二叉树 i=0 def createBiTree2(preOrder): # i为常数0 global i c = preOrder[i] # 取字符 if c != '#': root = BiTreeNode(c) i += 1 root.lchild = createBiTree2...
  • ![图片说明](https://img-ask.csdn.net/upload/201811/03/1541231260_380613.png)
  • 给定二叉树的后序和中序遍历序列,基于二叉树的基本操作,实现二叉树构建以及输出该二叉树的层次遍历序列。 【输入形式】 每个输入文件的第一行为一个正整数N(≤30),即二叉树中结点的总数。第二行给出了后续...
  • 文章目录二叉树1、什么是二叉树2、二叉树种类二叉查找树(binary search tree):斜树:满二叉树完全二叉树3、二叉树的一些性质4、二叉树的遍历先序遍历中序遍历后序遍历5、代码实现树的结构手动构建二叉树+遍历排序...
  • 一棵空树,或者是具有下列性质的二叉树: 若左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若右子树不空,则右子树上所有结点的值均大于它的根结点的值; 左、右子树也分别为二叉排序树; 没有键值...
  • day17 构造二叉树

    2020-06-18 00:11:54
    leetcode 105 从前序与中序遍历序列构造二叉树 这道题感觉好难,但是通过这道题也学到了好多东西 构成二叉树 中序序列和前、后,层次序列任一组合唯一确定一颗二叉树。前、后,层次序列都是提供根结点的信息,中序...
  • 以先序字符串方式建立二叉树

    千次阅读 2017-01-20 17:28:21
    输入一个二叉树的先序串,输出其后序遍历结果。如果结点的子树为空,先序串的对应位置为空格符。 输入 第1行:先序串(结点数≤26,以单个大写字母表示) 输出 第1行:后序序列 样例输入 AB C D 样例...
  • 使用递归(自顶向下,自底向上)的思路,解决 LeetCode《110. 平衡二叉树》问题
  • 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序() a.二叉排序树 b.哈夫曼树 c.avl树 d.堆 答案:d 解析: 首先a, 二叉排序树(B树即为二叉搜索树或称二叉排序...
  • (1)键盘输入二叉树结点前序序列,创建一棵二叉树; (2)实现SwapTree方法,以根结点为参数,交换每个结点的左子树和右子树(提示:前序递归); (3)实现Find方法,查找值为key的结点,并输出该结点的所有祖先...
  • 数据结构系列,二叉平衡树的构建

    千次阅读 2020-01-12 14:19:21
    平衡二叉树 平衡二叉树,首先要是一种二叉排序树, 然后,其中每一个结点的左子树,右子树的高度差(左子树的高度 – 右子树的高度)至多等于1,二叉树的高度就是这棵树有几层。 将二叉树上结点的左子树深度...
  • 数据结构与算法—复习:最优二叉树 哈夫曼算法 手画很简单,代码则需要多考虑 /** * 程序说明:复习 最优二叉树(哈夫曼树) 哈夫曼算法 */ #include <stdio.h> #include <malloc.h> /** * 定义一...
  • 一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序...
  • 平衡二叉树 平衡二叉树就是对二叉查找树的优化升级,它要求每个节点的左右子树的高度相差不大于1 1.平衡二叉树的查找 平衡二叉树和二叉排序树的查找是一摸一样的。 2.平衡二叉树的顺序输出 平衡二叉树的中序...
  • 堆排序

    2020-12-22 12:25:08
    将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区; 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]; 由于交换后...
  • 二叉树的建立及遍历

    2013-06-05 11:07:44
    如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
  • 8.6总结与提高

    2020-11-21 22:36:10
    第二类主要基于树形结构,包括二叉树和 m 叉树,主要采用基于比较的分支检索方法,即从树根开始,根据比较结果,沿着特定的分支进行检索,其检索的时间复杂度与树的深度同级别为对数函数。由于这一类查找表不仅用
  • 程序员技术交流①群:736386324 ,程序员技术交流②群:... Landis发明一种解决平衡二叉树的算法,所以很多资料称这样的平衡二叉树为AVL树 平衡因子:每个结点都有其各自的平衡因子,表示的就是其左子树深度同...
  • 二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像...对于排序二叉树,若按中序遍历就可以得到由小到大的有序序列。 我们先介绍一些关于二叉树的概念名词。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,400
精华内容 4,560
关键字:

关键字序列构建二叉树

友情链接: 开发板原理图V3.zip