精华内容
下载资源
问答
  • 目录由遍历序列构造二叉树or二叉搜索树由先序与中序遍历序列构造二叉树递归算法:非递归算法:由中序与后序序列构造二叉树由前序与后序序列构造二叉树由前序序列构建二叉搜索树 由遍历序列构造二叉树或二叉搜索树...

    由遍历序列构造二叉树or二叉搜索树+由连续数构造二叉搜索树


    由遍历序列构造二叉树或二叉搜索树可用递归方式求解,也可用非递归方式
    递归方式的关键是定位根的左子树遍历序列与右子树遍历序列

    由先序与中序遍历序列构造二叉树

    问题
    在这里插入图片描述

    递归算法:

    递归函数的作用是根据先序与中序遍历序列创建二叉树,问题的关键在于定位根的左子树序列与右子树序列,分别对其调用递归函数,得到根的左子树与右子树

    递归函数除需要两个遍历序列外,还需4个参数,分别为两个遍历序列的左右边界,前序序列的左边界即对应根,需建立哈希表,在中序序列中定位该根的位置,在中序序列中,根的左侧部分即为左子树序列,由此得到左子树序列的长度

    前序序列中左子树序列的左界即为根的右边一个位置,右界可由之前计算的左子树序列长度得到,右子树序列左界即为左子树右界+1,右子树序列右界为前序序列右界。

    中序序列中左子树左界为中序序列左界,左子树右界为根的位置-1,右子树左界为根的位置+1,右界为中序序列右界

    当出现左界大于右界时,递归函数返回
    或者说因为当递归函数中序列的长度为1,即只有一个节点时,其计算得到的前序序列中的左子树序列长度为0,计算得到的左子树序列左界将大于右界,计算得到的右子树序列左界也将大于右界,其调用递归函数得到左右子树时,递归函数应返回NULL,因此递归函数结束的条件为左子树序列左界大于右界

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        unordered_map<int,int> table;
    public:
        TreeNode* create( vector<int>& preorder,vector<int>& inorder,int pre_left,int pre_right,int in_left,int in_right )
        {
            if( pre_left>pre_right )
                return NULL;
            TreeNode* root=new TreeNode( preorder[pre_left] );
            int pre_root=pre_left;
            int in_root=table[ preorder[pre_left] ];
            int size= in_root-in_left;
            root->left=create( preorder,inorder,pre_root+1,pre_root+size,in_left,in_root-1 );
            root->right=create( preorder,inorder,pre_root+1+size,pre_right,in_root+1,in_right );
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int i;
            for( i=0;i<inorder.size();i++ )
            {
                table[ inorder[i] ]=i;
            }
            return create( preorder,inorder,0,preorder.size()-1,0,inorder.size()-1 );
        }
    };
    

    非递归算法:

    对于前序遍历序列中的两个连续节点u,v
    只可能有两种情况,一是v是u的左孩子,这是由根左右的遍历顺序确定的,若u有左孩子,则v一定是u的左孩子;二是v是u的某祖先(或u)的右孩子,因为若u无左孩子,则下一个遍历的是u的右孩子,若u也没有右孩子,则回溯至第一个有右儿子(且 u 不在它的右儿子的子树中)的节点ua,v即为ua的右孩子

    用一个栈保存当前节点的所有没有考虑过右孩子的祖先节点,用指针point指向当前节点不断往左走达到的最终节点,初始值指向中序遍历的第一个元素

    首先将根节点入栈,遍历前序序列,若栈顶元素不等于point指向的元素,证明当前元素是栈顶元素的左孩子(若等于,则表明栈顶元素无左孩子),将当前元素连接为栈顶元素的左孩子并入栈;

    若相等,则证明栈顶元素没有左孩子,当前元素是其祖先(或自己)的右孩子,为找到它是谁的右孩子,需比较栈中元素与中序序列。

    若中序序列中没有混入某节点的右孩子,则其节点顺序与退栈顺序是一致的,当出现中序序列某节点与栈顶节点不一致时,说明刚刚退栈的节点在中序序列中引入了它的右孩子

    若栈顶元素等于point指向的元素,将其退栈并暂存,point指向下一个元素,不断进行该操作直至栈顶元素与point指向的元素不等或栈为空,刚刚退栈的节点的右孩子即为现在在前序序列中遍历到的节点,将当前遍历到的节点连接并入栈

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if( preorder.size()==0 )
                return NULL;
            stack<TreeNode*> s;
            TreeNode* root=new TreeNode( preorder[0] );
            s.push( root );
            TreeNode* p;
            int point=0;
            int i;
            for( i=1;i<preorder.size();i++ )
            {
                if( s.top()->val!=inorder[point] )
                {
                    TreeNode* newnode=new TreeNode( preorder[i] );
                    s.top()->left=newnode;
                    s.push( newnode );
                }
                else
                {
                    while( !s.empty() && s.top()->val==inorder[point] )
                    {
                        p=s.top();
                        s.pop();
                        point++;
                    }
                    TreeNode* newnode=new TreeNode( preorder[i] );
                    p->right=newnode;
                    s.push( newnode );
                }
            }
            return root;
        }
    };
    

    由中序与后序序列构造二叉树

    在这里插入图片描述

    递归算法与由前、中序构建相似,只是边界的计算稍有不同

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        unordered_map<int,int> table;
    public:
        TreeNode* create( vector<int>& inorder,vector<int>& postorder,int in_left,int in_right,int post_left,int post_right )   
        {
            if( post_left>post_right )
                return NULL;
            int post_root=post_right;
            int in_root=table[ postorder[ post_right ] ];
            int size=in_root-in_left;
            TreeNode* root=new TreeNode( postorder[ post_right ] );
            root->left=create( inorder,postorder,in_left,in_root-1,post_left,post_left+size-1 );
            root->right=create( inorder,postorder,in_root+1,in_right,post_left+size,post_root-1 );
            return root;
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int i;
            for( i=0;i<inorder.size();i++ )
                table[ inorder[i] ]=i;
            return create( inorder,postorder,0,inorder.size()-1,0,postorder.size()-1 );
        }
    };
    

    由前序与后序序列构造二叉树

    在这里插入图片描述

    由前序与后序序列无法唯一确定一颗二叉树,但是能确定的是根的位置为前序序列的左界以及后序序列的右界,根的左子树的根为前序序列左界+1,需在后序序列中找到它的位置,因为其在后序序列中的位置为左子树后序序列的右界,因此可以计算得到左子树序列的长度

    需要注意的是,当前序序列中只有一个元素时,用哈希表查找其左子树根是不能进行的,因此除左界大于右界外,需加上一个递归函数返回条件为左界等于右界,在此种情况下直接构建根节点并返回

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        unordered_map<int,int> table;
    public:
        TreeNode* create( vector<int>& pre,vector<int>& post,int pre_left,int pre_right,int post_left,int post_right )
        {
            if( pre_left>pre_right  )
                return NULL;
            if( pre_left==pre_right )
            {
                TreeNode* root=new TreeNode( pre[ pre_left ] );
                return root;
            }
            int pre_root=pre_left;
            int post_root=post_right;
            int pre_ll=pre_root+1;
            int post_lr=table[ pre[ pre_ll ] ];
            int size=post_lr-post_left+1;  
            TreeNode* root=new TreeNode( pre[ pre_left ] );
            root->left=create( pre,post,pre_root+1,pre_root+size,post_left,post_left+size-1 );
            root->right=create( pre,post,pre_root+size+1,pre_right,post_left+size,post_root-1 );
            return root;
        }
        TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
            int i;
            for( i=0;i<post.size();i++ )
            {
                table[ post[i] ]=i;
            }
            return create( pre,post,0,pre.size()-1,0,post.size()-1 );
        }
    };
    

    由前序序列构建二叉搜索树

    在这里插入图片描述
    上下界的计算方式发生改变,右子树先序序列左界位置为第一个大于根节点的元素

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* create( vector<int>& preorder,int left,int right )
        {
            if( left>right )
                return NULL;
            int pre_root=left;
            TreeNode* root=new TreeNode( preorder[left] );
            int i=pre_root+1;
            int size;
            while( i<=right && preorder[i]<preorder[left] )
            {
                i++;
            }
            size=i-1-left;
            root->left=create( preorder,pre_root+1,pre_root+size );
            root->right=create( preorder,pre_root+size+1,right );
            return root;   
        }
        TreeNode* bstFromPreorder(vector<int>& preorder) {
            return create( preorder,0,preorder.size()-1 );
        }
    };
    

    由连续数构造二叉搜索树

    在这里插入图片描述
    左子树序列右界即为根位置-1,右子树序列左界即为根位置+1
    在连续数数组中,每个元素都可为根,因此递归函数中包含对数组元素的遍历,所得到的是二叉搜索树的集合

    对左子树序列以及右子树序列调用递归函数得到的也是左右子树集合,因此需分别从两个集合中取一个,与根节点组成完整的二叉搜索树,并保存

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        vector<TreeNode*> create( int left,int right )
        {
            if( left>right )
                return {NULL};
            int i;
            vector<TreeNode*> allcombine;
            for( i=left;i<=right;i++ )
            {
                vector<TreeNode*> leftall=create( left,i-1 );
                vector<TreeNode*> rightall=create( i+1,right );
                for( auto x:leftall )
                    for( auto y:rightall )
                    {
                        TreeNode* newnode=new TreeNode( i );
                        newnode->left=x;
                        newnode->right=y;
                        allcombine.push_back( newnode );
                    }
            }
            return allcombine;
        }
        vector<TreeNode*> generateTrees(int n) {
            if( n<1 )
                return {};
            return create( 1,n );
        }
    };
    
    展开全文
  • 构造二叉搜索树 定义 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都...

    构造二叉搜索树

    定义

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

    • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

    • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

    • 它的左右子树也分别为二叉搜索树

    在这里插入图片描述

    特性

    • 二叉搜索树中最左侧的节点是树中最小的节点,最右侧节点一定是树中最大的节点
    • 采用中序遍历遍历二叉搜索树,可以得到一个有序的序列

    代码实现

    public class BSTree {
    
        //定义Node类
        public  static  class Node{
            int val;
            Node left;
            Node right;
    
            Node(int val){
                this.val = val;
                this.left = null;
                this.right = null;
            }
        }
    
        //定义根节点
        private Node root = null;
    
        //查找
        public Node find (int val){
            if (root == null){
                return  null;
            }
    
            Node cur = root;
            while (cur !=null){
                if (cur.val == val){
                    return  cur;
                }else if (cur.val > val){
                    cur = cur.left;
                }else{
                    cur = cur.right;
                }
            }
    
            return  null;
        }
    
        // 插入
        // 新的节点都是插入在叶子节点或者不完全的子树上
        public boolean insert(int val){
            if (root == null){
                root = new Node(val);
                return  true;
            }
    
            Node cur = root;
            Node parent = null;
    
            //搜索要插入的位置
            while (cur != null){
                parent = cur;
                if (cur.val == val){
                    //保证插入的节点不重复
                    return  false;
                }else if (cur.val > val){
                    cur = cur.left;
                }else{
                    cur = cur.right;
                }
            }
    
            // 找到了合适的位置,根据与父节点的大小关系建立连接
            Node node = new Node(val);
            if (val > parent.val){
                parent.right = node;
            }else{
                parent.left = node;
            }
    
            return  true;
        }
    
        //删除
        public boolean remove(int val){
            if (root == null){
                return  false;
            }
    
            Node cur = root;
            Node parent = null;
    
            // 搜索要删除的节点
            while (cur != null){
                if (cur.val == val ){
                    break;
                }else if (cur.val > val){
                    parent = cur;
                    cur = cur.left;
                }else {
                    parent = cur;
                    cur = cur.right;
                }
            }
    
            if (cur == null){
                return  false;
            }else{
                remove(parent,cur);
                return  true;
            }
        }
    
        public void remove(Node parent, Node cur){
            if (cur.left == null){
                if (cur != root){
                    if (parent.left == cur){
                        parent.left = cur.right;
                    }else{
                        parent.right = cur.right;
                    }
                }else{
                    root = cur.right;
                }
            }else if (cur.right == null){
                if (cur != root){
                    if (parent.left == cur){
                        parent.left = cur.left;
                    }else{
                        parent.right = cur.left;
                    }
                }else{
                    root = cur.left;
                }
            }else{
                // 左右都不为空选取一个新的节点作为子树的根
                // 1.左子树的最右节点 ---> 大于左子树中的所有节点,小于右子树中的所有节点
                // 2.右子树的最左节点 ---> 小于右子树中的所有节点,大于左子树中的所有节点
                // 以下为选取左子树的最右节点
                parent = cur;
                Node next = cur.left;
    
                while (next.right != null){
                    parent = next;
                    next = next.right;
                }
    
                cur.val = next.val;
                if (parent.left == next){
                    parent.left = next.left;
                }else{
                    parent.right = next.left;
                }
            }
    
        }
    
        public  void inOrder(){
            inOrderInternal(root);
            System.out.println();
        }
    
        private void inOrderInternal(Node root) {
            if (root != null){
                inOrderInternal(root.left);
                System.out.print(root.val + " " );
                inOrderInternal(root.right);
            }
        }
    
    
        public static void main(String[] args) {
            BSTree bs = new BSTree();
            bs.insert(10);
            bs.insert(5);
            bs.insert(6);
            bs.insert(8);
            bs.insert(3);
            bs.insert(7);
            bs.insert(2);
            bs.insert(6);
            bs.insert(11);
            bs.insert(14);
            bs.insert(12);
            bs.insert(13);
            bs.inOrder();
    
            bs.remove(3);
            bs.inOrder();
    
            bs.remove(14);
            bs.inOrder();
    
            bs.remove(2);
            bs.inOrder();
    
            bs.remove(10);
            bs.inOrder();
        }
    }
    
    

    性能分析

    插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
    对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
    但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

    在这里插入图片描述

    最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:log2 N
    最差情况下,二叉搜索树退化为单支树,其平均比较次数为:N

    展开全文
  • 前序遍历构造二叉搜索树 * @author wsq * @date 2021/3/24 * 返回与给定前序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。 * (回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下...
    /**
     * 1008. 前序遍历构造二叉搜索树
     * @author wsq
     * @date 2021/3/24
     * 返回与给定前序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。
     * (回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left 的任何后代,值总 < node.val,而 node.right 的任何后代,值总 > node.val。此外,前序遍历首先显示节点 node 的值,然后遍历 node.left,接着遍历 node.right。)
     * 题目保证,对于给定的测试用例,总能找到满足要求的二叉搜索树。
     *
     * 示例:
     * 输入:[8,5,1,7,10,12]
     * 输出:[8,5,10,1,7,null,12]
     *
     * 链接:https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
     */
    public class BstFromPreorder {
        /**
         * 根据前序序列构建二叉搜索树
         * @param preorder
         * @return
         */
        public TreeNode bstFromPreorder(int[] preorder) {
            int n = preorder.length;
            if(n == 0){
                return null;
            }
            int start = 0;
            int end = n - 1;
            TreeNode root = dfs(preorder, start, end);
            return root;
        }
    
        private TreeNode dfs(int[] preorder, int start, int end){
            if(start > end){
                return null;
            }
            // 如果直接有个节点,直接构建一个节点,并返回
            if(start == end){
                return new TreeNode(preorder[start]);
            }
            // 创建当前的根节点
            TreeNode root = new TreeNode(preorder[start]);
            // 根据二叉搜索树左子树都比根节点值小的特点,寻找左子树在列表中终止的位置
            int mid = -1;
            for(int i = start + 1; i <= end; i++){
                if(preorder[i] > preorder[start]){
                    mid = i;
                    break;
                }
            }
            // 如果mid为-1,证明后续值都比root的值要小,证明root只有左子树没有右子树
            if(mid == -1){
                mid = end + 1;
            }
            // 如果根据mid值,去构建当前root节点的左右子树
            root.left = dfs(preorder, start + 1, mid - 1);
            root.right = dfs(preorder, mid, end);
            return root;
        }
    }
    
    
    展开全文
  • 1008. 前序遍历构造二叉搜索树 题目描述 题目解析 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int ...

    题目来源

    1008. 前序遍历构造二叉搜索树

    题目描述

    在这里插入图片描述

    题目解析

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
            TreeNode root = null;
            for (int i = 0; i < preorder.length; i++){
                root = helper(root, preorder[i]);
            }
            return root;
        }
        
        private TreeNode helper(TreeNode root, int val){
            if (root == null){
                return new TreeNode(val);
            }
            
            if (root.val > val){
                root.left = helper(root.left, val);
            }else{
                root.right = helper(root.right, val);
            }
            
            return root;
        }
    }
    

    在这里插入图片描述

    展开全文
  • 构造二叉搜索树,一不小心就平衡了
  • Construct Binary Search Tree from Preorder Traversal(C++前序遍历构造二叉搜索树
  • 给定一个排好序的数组,去构造二叉排序 array = [10,-3,0,5,9] 思路 找到数组的中点,然后递归构造左右。 代码 def array_build_tree(array): if len(array) == 0: return None mid = len(array)//2 root =...
  • 构造二叉搜索树C++

    2015-04-08 20:31:49
    构造一颗二叉搜索树,树的结构如图(a),下面上代码(最后输出是中序遍历输出的) #include using namespace std; typedef struct BSTree { char node_value; struct BSTree *left; struct BSTree *right; } ...
  • Python 构造二叉搜索树

    2017-09-09 10:51:38
    本文采用Python语言编写数据结构之二叉搜索树,主要实现二叉树的构造,插入数据,删除数据,以及二叉树的中序遍历,先序遍历,和后序遍历。
  • 给你 n 个数,按照输入顺序构造二叉搜索树,然后输出每个数的父亲。 Step2 Ideas: 二叉搜索树:将要插入的数 num, 树上比 num 大的数 Max, 比 num 小的树 Min. 那么 Max 或者 Min 一定是 num 的父亲。 所以...
  • #include &lt;cstdio&gt; #include &lt;vector&gt; using namespace std; bool isMirror; vector&lt;int&gt; pre; vector&lt;int&gt; post; void getpost(int root, int tail)... ...
  • 108. 将有序数组转换为二叉搜索树 难度简单621 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 ...
  • 分析 简单递归遍历 代码 class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { TreeNode* root = nullptr;... int size = preorder.size();... root = insert(root, preorde.
  • 标签:树、二叉树、二叉搜索树 解法 时间复杂度 空间复杂度 执行用时 Ans 1 (Python) O(N)O(N)O(N) O(N)O(N)O(N) 52ms (52.88%) Ans 2 (Python) Ans 3 (Python) 解法一: class Solution: def ...
  • 是否完全二叉搜索树  将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。 输入格式: 输入第...
  • 第一行是搜索树的后面输入值的个数 第二行是依次插入节点的key(节点的key是整数) 输入的key值可能重复,如果已经形成的搜索树中存在该key,则不再插入
  • Task The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer,, pointing to the root of a binary search tree....
  • 原题题目 闲谈 最近发现其实用很多解法解出来还是挺简单的 但是真的需要用 时间空间复杂度相对简单的方法做出来确实 另一种世界了 所以最近可能做题会做的比较少 但是每道题都希望能够用最好的方法 时空复杂度...
  • 题目描述 原题 大概意思就是给你一个...方法2:利用二叉搜索树的性质:递增排序后的结点顺序就是中序遍历序列,而知道中序和前序就能创建一棵树 AC代码(方法2) #include<bits/stdc++.h> using namespace st

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,226
精华内容 490
关键字:

构造二叉搜索树