精华内容
下载资源
问答
  • BST删除节点

    2018-07-17 18:50:00
    首先,BST节点删除分为几种情况: (a)当该节点为叶子节点,则让该节点的父节点指向其变为NULL,然后释放节点; (b)当该节点不是叶子节点,但左子树或者右子树为空,则: (1)若左子树为空,则让该节点...
    首先,BST节点的删除分为几种情况:
    (a)当该节点为叶子节点,则让该节点的父节点指向其变为NULL,然后释放节点;
    (b)当该节点不是叶子节点,但左子树或者右子树为空,则:
            (1)若左子树为空,则让该节点父节点指向其右节点;
            (2)若右子树为空,则让该节点父节点指向其左节点。
    (c)当该节点不是叶子节点,且左子树和右子树都不为空,则:
            (1)在该节点的左子树中找到最大节点Lmax(该节点必然是一个叶子节点),取出Lmax的值val,删除Lmax;
            (2)将 val 赋给该节点的值,即:root->val = val。
            (3)判断Lmax的父节点PreLmax的左节点是否等于Lmax,若是则:PreLmax->left = Lmax->left    否则:  PreLmax->right = Lmax->left。
    二叉搜索树的删除复杂度为O(h),h是二叉树的高度。代码如下:
    /*删除二叉搜索树中的指定值的节点*/
    node *deleteNode(node *root, int ele)
    {
        node *newroot = root;  //指向新的根节点 
        node *presite = root; //指向要删除节点的父节点 
        int pos = 0; //要删除节点在其父节点的位置: -1:在左侧    1:在右侧    0:就是根节点  
        /*找到要删除的元素在BST中的位置*/ 
        while(root != NULL)
        {
            if(root->val > ele)
            {
                presite = root;
                root = root->left;
                pos = -1;
            }
            else if(root->val < ele)
            {
                presite = root;
                root = root->right;
                pos = 1;
            }
            else
            {
                break;            
            }
        }
        if(root == NULL)
        {
            cerr<<"要删除的节点不存在于BST中\n";
        }
        else
        {
            //该节点有左子树和右子树 
            if(root->left!=NULL && root->right!=NULL)
            {
                cout<<"has left and right tree\n";
                node *Lmax = root->left;    //最大左子节点 
                node *PreLmax = root;       //最大左子节点的父节点 
                while(Lmax->right != NULL)
                {
                    PreLmax = Lmax;     
                    Lmax = Lmax->right;
                }
                root->val = Lmax->val;    //替换root的值为最大左子树节点值
                if(PreLmax->left == Lmax)  //root的左子树最大节点是root的左节点 
                    PreLmax->left = Lmax->left;
                else              //root的左子树最大节点不是root的左节点
                    PreLmax->right = Lmax->left;
                delete Lmax;
                Lmax = NULL;
            }
            //该节点的左子树为空 
            else if(root->left == NULL && root->right != NULL)      
            {
                cout<<"left tree is empty\n";
                if(0 == pos)        //在根节点 
                {
                    newroot = root->right;
                }
                else if(1 == pos)     //在右侧 
                {    
                    presite->right = root->right;
                }
                else                  //在左侧 
                {
                    presite->left = root->right;    
                }
                delete root;
                root = NULL;
            }
            //该节点的右子树为空 
            else if(root->right == NULL && root->left != NULL)     //site的右子树为空
            {
                cout<<"right tree is empty\n";
                if(0 == pos)      //在根节点 
                {
                    newroot = root->left;
                }
                else if(1 == pos) //在右侧 
                {
                    presite->right = root->left;
                }
                else                //在左侧 
                {
                    presite->left = root->left;    
                }
                delete root;
                root = NULL;
            }
            //该节点为叶子节点 
            else                    
            { 
                cout<<"leaf node\n";
                if(0 == pos)          //根节点 
                {
                    cerr<<"BST只有一个节点且被删除,该BST变为空树\n";
                    delete root;
                    root = NULL;
                }
                else if(1 == pos)      //在右侧 
                {
                    presite->right = NULL;
                    delete root;
                    root = NULL;
                }
                else                  //在左侧 
                {
                    presite->left = NULL;
                    delete root;
                    root = NULL;    
                }
            }    
        }
        return newroot;
    }

     

    转载于:https://www.cnblogs.com/ladawn/p/9325223.html

    展开全文
  • bst 删除节点Problem statement: 问题陈述: Given a BST and a value x, write a function to delete the nodes having values greater than or equal to x. The function will return the modified root. 给定...

    bst 删除节点

    Problem statement:

    问题陈述:

    Given a BST and a value x, write a function to delete the nodes having values greater than or equal to x. The function will return the modified root.

    给定一个BST和一个值x ,编写一个函数删除值大于或等于x的节点 。 该函数将返回修改后的根。

    Example:

    例:

    Input BST
          8
        /  \
       4    10
      / \   / \
     3   5  9  11
    
    Input X:  10
    
    After deletion:
    
    
         8
        /  \
       4    9
      / \   
     3   5  
    
    
    

    Solution:

    解:

    Basic properties of BST:

    BST的基本属性:

    1. All node values are distinct.

      所有节点值都是不同的。

    2. The left child node is always smaller than the root & right child node is always greater than the root.

      左子节点始终小于根节点,右子节点始终大于根节点。

    Thus it's clear whenever a root has a value greater than or equal to the input value X, the entire right subtree and root need to be deleted, but not the left one.

    因此,很明显,只要根的值大于或等于输入值X ,就需要删除整个右子树和根,而不必删除左子树和根。

    Algorithm:

    算法:

    FUNCTION buildTree (root,X)
        IF (root==NULL)
            Return NULL;
        END IF
        IF (root->data is equal to X)
            return root->left; //returning the left subtree basically
        ELSE IF(root->data>key)
            //recur for the left subtree since left subtree may also have nodes 
            //that need to be deleted due to greater or equal values
            return buildTree(root->left, X); 
        ELSE
            //root is not at all to be deleted, same for left subtree, 
            //recursively process right subtree
            root->right=buildTree(root->right, X);
            return root;
    END FUNCTION
    
    

    The above function actually builds the tree deleting the nodes having greater and equal value than X.

    上面的函数实际上是在构建树,删除值大于和等于X的节点。

    Example with Explanation:

    解释示例:

    Nodes are represented by respected values for better understanding
          8
        /  \
       4    10
      / \   / \
     3   5  9  11
    
    Input X:  10
    
    At main we callbuildTree (8, 10)
    ------------------------------------------------
    
    buildTree (8, 10)
    root not NULL
    8<10
    Thus root->left= 8->left
    root->right=buildTree (8->right, 10) //buildTree (10, 10)
    ------------------------------------------------
    
    buildTree (10, 10)
    root not NULL
    10==10
    Thus return root->left= 10->left=9
    ------------------------------------------------
    
    Hence At buildTree (8, 10)
    Thus root->left= 8->left
    root->right=9 (9 is the root to the remaining subtree which is NULL here luckily)
    
    So the tree actually becomes
         8
       / \
      4     9
     / \ 
    3   5 
    
    
    

    C++ Implementation:

    C ++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    class Node{
    	public:             
    	int data;           //value
    	Node *left;    //pointer to left child
    	Node *right;   //pointer to right child
    };
    
    // creating new node
    Node* newnode(int data)  
    { 
    	Node* node = (Node*)malloc(sizeof(Node)); 
    	node->data = data; 
    	node->left = NULL; 
    	node->right = NULL; 
    	return(node); 
    }
    
    Node* buildTree(Node* root,int key){
    	if(!root)
    		return NULL;
    	if(root->data==key){
    		return root->left; //only left subtree not deleted
    	}
    	else if(root->data>key)
    		return buildTree(root->left,key); //recur for left subtree
    	else{
    		//root not deleted
    		//left subtree not deleted
    		//buld right subtree
    		root->right=buildTree(root->right,key); 
    		return root;
    	}
    }
    
    Node* deleteNode(Node* root, int key)
    {
    	root=buildTree(root,key);
    	return root; 
    }
    
    void levelwisedisplay(Node *root)
    {
    	//to display the tree level wise
    	queue<Node*> q;
    
    	Node* temp;
    	int count=0;
    	q.push(root);
    	q.push(NULL);
    
    	while(!q.empty()){
    		temp=q.front();
    		q.pop();
    
    		if(temp==NULL){
    			if(!q.empty())
    				q.push(NULL);
    			cout<<"\nend of level "<<count++<<endl;
    		}
    		else{
    			cout<<temp->data<<" ";
    			if(temp->left)
    				q.push(temp->left);
    			if(temp->right)
    				q.push(temp->right);
    		}
    	}
    	return ;
    }
    
    int main(){
    	cout<<"tree is built as per example\n";
    
    	Node *root=newnode(8); 
    	root->left= newnode(4); 
    	root->right= newnode(10); 
    	root->right->right=newnode(11);
    	root->right->left=newnode(9);
    	root->left->left=newnode(3); 
    	root->left->right=newnode(5);
    
    	printf("Displaying level wise\n");
    	levelwisedisplay(root);
    
    	root=deleteNode(root,10);//as per example
    
    	printf("after deleting nodes greater or equal to 10\n");
    	levelwisedisplay(root);
    
    	return 0;
    }
    
    

    Output

    输出量

    tree is built as per example
    Displaying level wise
    8      
    end of level 0
    4 10   
    end of level 1
    3 5 9 11      
    end of level 2
    after deleting nodes greater or equal to 10
    8      
    end of level 0
    4 9    
    end of level 1
    3 5    
    end of level 2 
    
    
    

    翻译自: https://www.includehelp.com/icp/delete-nodes-greater-than-or-equal-to-k-in-a-bst.aspx

    bst 删除节点

    展开全文
  • bst 删除节点Problem statement: C++ program to find number of binary search trees with n nodes. 问题陈述: C ++程序查找具有n个节点的二进制搜索树的数量。 Input format: single integer n 输入格式:单...

    bst 删除节点

    Problem statement: C++ program to find number of binary search trees with n nodes.

    问题陈述: C ++程序查找具有n个节点的二进制搜索树的数量。

    Input format: single integer n

    输入格式:单整数n

    Constraints: 0=<n<=15

    约束: 0 = <n <= 15

    Sample input: 4

    样本输入: 4

    Sample output: 14 binary search tree/trees are there for 4 nodes

    输出示例: 14个二叉搜索树/四个树的树

    Problem explanation:

    问题说明:

    The number of BSTs with n vertices is given by Catalan numbers. For n=0,1,2,3,4... Catalan numbers are 1,1,2,5,14... and so on.

    具有n个顶点的BST数量由加泰罗尼亚语数字给出。 对于n = 0,1,2,3,4 ...加泰罗尼亚语数字是1,1,2,5,14 ...依此类推。

    Catalan numbers are given by Cn = (2n)!/(n+1)!*n! = count of BSTs with nodes n.

    加泰罗尼亚数字由Cn =(2n)!/(n + 1)!* n! =节点为n的BST的计数

    Catalan numbers are used here to find the count of BSTs because both satisfy same recurrence relation that is:

    由于两者都满足相同的递归关系,因此此处使用加泰罗尼亚语数字查找BST的计数:

    catalan-number

    For n=0 number of trees is 1 i.e. empty tree. For subsequent values:

    对于n = 0 ,树的数量为1,即空树。 对于后续值:

    catalan-number

    And, so on...

    等等...

    Solution:

    解:

    If we consider root as the ith node then:

    如果我们将root视为第i 节点,则:

    1. i-1 nodes are there in left subtree.

      i-1节点在左子树中。

    2. n-i nodes are there in right subtree.

      ni个节点在右子树中。

    Let’s denote count of BST by Bn for n elements

    我们用n表示Bn的BST计数

    The 2 subtrees here will be independent of each other. Therefore it will be ( B i-1 * B n-i ) for Bi . For n nodes (as i has n choices) it will be :

    这里的2个子树将彼此独立。 因此,Bi将为(B i-1 * B ni)。 对于n个节点(因为我有n个选择),它将为:

    catalan-number

    Since the recurrence relation is same as of catalan numbers , so count of BST is given by Cn.

    由于递归关系与加泰罗尼亚数相同,因此BST的计数由Cn给出。

    Recurrence relation:

    递归关系:

    catalan-number

    This gives complexity O(4^n). Complexity can be reduced to O(n^2) by using DP.

    这给出了复杂度O(4 ^ n)。 使用DP可以将复杂度降低到O(n ^ 2)。

    C++ implementation:

    C ++实现:

    #include <iostream>
    using namespace std;
    
    int CN(int n){
    	int Cn =0;
    	// base case
    	if(n==0) // empty tree
    	{
    		return 1;
    	}
    	for(int i=1;i<n+1;i++)
    	{
    		Cn+= CN(i-1)*CN(n-i);
    	}
    	return Cn;
    }
    
    int main(){
    	int n;
    	cout<<"Enter number of nodes: ";
    	cin>>n;
    	cout<<n<<endl;
    	int trees=CN(n);
    	cout<<trees<<" binary search trees are there for "<<n<<" nodes"<<endl;
    	return 0; 
    }
    
    

    Output

    输出量

    Enter number of nodes: 4
    14 binary search trees are there for 4 nodes
    
    
    

    翻译自: https://www.includehelp.com/cpp-programs/find-number-of-bsts-with-n-nodes-catalan-numbers.aspx

    bst 删除节点

    展开全文
  • Leetcode 702 BST删除节点

    2020-03-20 19:26:50
    前驱结点: 先取当前节点的左节点,取该节点的最右节点 后继结点: 先取当前节点的右... root.val,说明要删除节点在右子树,root.right = deleteNode(root.right, key)。 如果 key < root.val,说明要删除的...
            前驱结点: 先取当前节点的左节点,取该节点的最右节点
            后继结点: 先取当前节点的右节点,取该节点的最左节点 
    
        算法:
    
            如果 key > root.val,说明要删除的节点在右子树,root.right = deleteNode(root.right, key)。
            如果 key < root.val,说明要删除的节点在左子树,root.left = deleteNode(root.left, key)。
            如果 key == root.val,则该节点就是我们要删除的节点,则:
            ①:如果该节点是叶子节点,则直接删除它:root = null。
            ②:如果该节点不是叶子节点且有右节点,则用它的后继节点的值替代 root.val = successor.val,然后删除后继节点。
            ③:如果该节点不是叶子节点且只有左节点,则用它的前驱节点的值替代 root.val = predecessor.val,然后删除前驱节点。
            ④:返回 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 {
    public:
        TreeNode*  deletenode(TreeNode* root, int val) {
            if(root==NULL){
                return NULL;
            }
            if(root->val>val){
                deletenode(root->left,val);
            }
            if(root->val<val){
                deletenode(root->right,val);
            }
            else{
                if(root->left==NULL&&root->right==NULL){
                    root=NULL;
                }
                //左右子树都存在,返回后继节点(右子树最左叶子)作为新的根
                //有右结点,则赋值后继结点的值给待删节点,再删除后继结点
                if(root->right!=NULL){
                    root->val=getlaternode(root);
                    root->right=deletenode(root->right,root->val);
                }
                if(root->left!=NULL){
                    root->val=getprenode(root);
                    root->left=deletenode(root->left,root->val);
                }//现在已经把前驱节点的值赋给了root,即现在root和pre的值均为pre->val,所以现在应该删除pre节点,即左子树中数值为root->val(pre->val)的节点
            }
            return root;
        }
    private:
        TreeNode*getlaternode(TreeNode*root){
            root=root->right;
            while(root->left!=NULL){
                root=root->left;
            }
            return root->val;
        }
        TreeNode*getprenode(TreeNode*root){
            root=root->left;
            while(root->right!=NULL){
                root=root->right;
            }
            return root->val;
        }
    };
    
    展开全文
  • BST删除节点

    千次阅读 2018-03-26 22:50:49
    给定一棵BST和一个key,要求找到并删除值为key的节点删除后的二叉树还是BST。 方法一:找到该节点,并把该节点的右节点替代该节点,并把该节点的左子树链接到其右节点的最左下节点的left。 public TreeNode ...
  • 1 BST删除节点 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int...
  • 实现了BST节点的插入,删除和查找,其中删除只实现了一种,即用前驱替换,另外一种用后继替换没有实现。
  • 我正在尝试删除BST . 我使用的算法是:如果搜索与一个节点匹配1.1 . 如果有左子节点,则交换该节点及其左子节点的值 . 并再次调用左节点的功能 .1.2 . 否则,如果没有左节点但是有正确的节点,则交换节点和右节点的...
  • 1 解题思想现在有一个二叉搜索树,现在要让你删除一个节点,并且保证整个BST的性质不变。要保证整个性质,我们必须在删除的位置上,找一个合适的值来进行替换,使得BST上的每个节点都满足 当前节点的值大于左节点...
  • 前言:在学习BST时,发现查找插入等操作都很好理解和实现,而删除节点的操作情况比较复杂,故通过自己的理解整理如下,本文适合初学者理解并自己动手实现BST删除操作。 在很多文章中提到,删除节点可以考虑以下三种...
  • Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided int
  • public TreeNode deleteNode(TreeNode root, int key) { if(root==null) return root; //key找到 if (root.val == key) { //无左孩子也无右孩子 if (root.left == null &amp;&a...
  •  先找到节点,然后再对要删除节点进行处理  找到节点好说,用BST的性质找就好了  主要在于如何处理  这里的方法比较笨也比较麻烦,  1. 先确定当前root是prev的左孩子还是右孩子,后面重构prev要用  .....
  • 我正在尝试遵循“Data Structures and Algorithms” by Granville Barnett中的BST算法,但是我不理解其在下面描述的节点删除算法.第3.3节(第22页)Removing a node from a BST is fairly straightforward, with four ...
  • (02) 没有父节点节点称为根节点; (03) 每一个非根节点有且只有一个父节点; (04) 除了根节点外,每个子节点可以分为多个不相交的子树。 树的基本术语 若一个结点有子树,那么该结点称为子树根的"双亲",子树的根...
  • Delete Node in a BST 删除二叉搜索树中的节点【Medium】【Python】【二叉树】ProblemGiven a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node ...
  • 3、求BST树高度,求BST节点个数 4、返回中序遍历第k个节点的值 5、判断一个二叉树是否是BST树,判断一个BST树是否是AVl树 6、BST树的镜像 7、把BST树满足[begin,end]区间的值放在集合中、打印出来 8、判断...
  • Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divi...
  • 思路:这题的求解依然可以使用到递归的思想,给出一个根节点和key值,删除key值对应的节点,如果当前给出的根节点的val大于key值,那么就可以从把当前根节点的左子节点作为新的根节点,递归调用这个方法;如果根节点...
  • * BST删除一个节点,并返回新的BST * @author zhaizhg * */ public class DeleteNumInBST { public static void main(String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(2);...
  • 题干中给定一个二叉搜索树(BST)的根节点以及一个给定的值,要求我们删除BST中与该值相等的节点,并且删除节点后,该树仍旧满足二叉搜索树的性质。下面举出一个例子 root = [5,3,6,2,4,null,7] key = 3 5 / \...
  • 给定一棵 Binary Search Tree(BST)和一个范围 [min, max],请把 BST 上所有在 [min, max] 范围之外的节点都删除掉,且保持删除节点后的新树仍是 BST。如下是一棵 BST,给定范围为 [-10, 13] 在删除掉所有在 ...
  • 给定一个二叉搜索树的根...一般来说,删除节点可分为两个步骤:首先找到需要删除的节点;如果找到了,删除它。说明: 要求算法时间复杂度为 O(h),h 为树的高度。示例:root = [5,3,6,2,4,null,7] key = 3 5 /...
  • 关于BST的知识点,小编不在这里细讲了,不懂的大家自行百度吧或者查找有关资料。但是,小编还是会告诉你BST的全名是啥,不然你们查资料太费事了。BST的全名是binary search tree。大概中文名就叫做二叉搜索树。下面...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 668
精华内容 267
关键字:

bst删除节点