• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

数据结构:二叉搜索树的增删查改

python BudingCode 2072次浏览 0个评论

二叉搜索树的增删查改

      • 二叉搜索树(Binary Search Tree)
      • 基本操作之查找(Update)
      • 基本操作之修改(Update)
      • 基本操作之增加(Create)
      • 基本操作之删除(Delete)

二叉搜索树(Binary Search Tree)

二叉搜索树可以是一棵空树或者是一棵满足下列条件的二叉树:

  • 如果它的左子树不空,则左子树上所有节点值均小于它的根节点值。
  • 如果它的右子树不空,则右子树上所有节点值均大于它的根节点值。
  • 它的左右子树均为二叉搜索树(BST)。
  • 严格定义下BST中是没有值相等的节点的(No duplicate nodes)。

根据上述特性,我们可以得到一个结论:BST中序遍历得到的序列是升序的。

Java版

class TreeNode{ 
	int val;
	TreeNode left;
	TreeNode right;
	pubic TreeNode(int val) { 
		this.val = val;
		this.left = this.right = null;
	}
}

Python版

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

基本操作之查找(Update)

思路:

查找值为val的节点,如果val小于根节点则在左子树中查找,反之在右子树中查找

Java版

public TreeNode searchBST(TreeNode root, int val) { 
	if (root == null) { 
		return null;
	}// 未找到值为val的节点
	if (val < root.val) { 
		return searchBST(root.left, val);//val小于根节点值,在左子树中查找
	} else if (val > root.val) { 
		return searchBST(root.right, val);//val大于根节点值,在右子树中查找
	} else { 
		return root;//找到了
	}
}

Python

def searchBST(root, val):
    if not root:
        return None # 未找到值为val的节点
    if val < root.val:
        return searchBST(root.left, val) # val小于根节点值,在左子树中查找哦
    elif val > root.val:
        return searchBST(root.right, val) # val大于根节点值,在右子树中查找
    else:
        return root

基本操作之修改(Update)

思路

查找值为val的节点,如果val小于根节点则在左子树中查找,反之在右子树中查找

Java版

public void updateBST(TreeNode root, int target, int val) { 
	if (root == null) { 
		return;
	}// 未找到target节点
	if (target < root.val) { 
		updateBST(root.left, target, val);//target小于根节点值,在左子树中查找
	} else if (target > root.val) { 
		updateBST(root.right, target, val);//target大于根节点值,在右子树中查找
	} else {  //找到了
		root.val = val;
	}
}

Python

def updateBSTBST(root, target, val):
    if not root:
        return  # 未找到target节点
    if target < root.val:
        updateBST(root.left, target, val) # target小于根节点值,在左子树中查找哦
    elif target > root.val:
        updateBST(root.right, target, val) # target大于根节点值,在右子树中查找
    else:  # 找到了
        root.val = val

基本操作之增加(Create)

思路

  • 根节点为空,则待添加的节点为根节点
  • 如果待添加的节点值小于根节点,则在左子树中添加
  • 如果待添加的节点值大于根节点,则在右子树中添加
  • 我们统一在树的叶子节点(Leaf Node)后添加

Java版

public TreeNode insertNode(TreeNode root, TreeNode node) { 
    if (root == null) { 
        return node;
    }
    if (root.val > node.val) { 
        root.left = insertNode(root.left, node);
    } else { 
        root.right = insertNode(root.right, node);
    }
    return root;
}

Python

def insertNode(root, node):
    if not root:
        return node
    if root.val > node.val:
        root.left = insertNode(root.left, node)
    else:
        root.right = insertNode(root.right, node)
    return root

基本操作之删除(Delete)

思路

  • 考虑待删除的节点为叶子节点,可以直接删除并修改父亲节点(Parent Node)的指针,需要区分待删节点是否为根节点
  • 考虑待删除的节点为单支节点(只有一棵子树——左子树 or 右子树),与删除链表节点操作类似,同样的需要区分待删节点是否为根节点
  • 考虑待删节点有两棵子树,可以将待删节点与左子树中的最大节点进行交换,由于左子树中的最大节点一定为叶子节点,所以这时再删除待删的节点可以参考第一条

Java版

public TreeNode removeNode(TreeNode root, int value) { 
    TreeNode dummy = new TreeNode(0);
    dummy.left = root;
    TreeNode parent = findNode(dummy, root, value);
    TreeNode node;
    if (parent.left != null && parent.left.val == value) { 
        node = parent.left;
    } else if (parent.right != null && parent.right.val == value) { 
        node = parent.right;
    } else { 
        return dummy.left;
    }
    deleteNode(parent, node);
    return dummy.left;
}

private TreeNode findNode(TreeNode parent, TreeNode node, int value) { 
    if (node == null) { 
        return parent;
    }
    if (node.val == value) { 
        return parent;
    }
    if (value < node.val) { 
        return findNode(node, node.left, value);
    } else { 
        return findNode(node, node.right, value);
    }
}

private void deleteNode(TreeNode parent, TreeNode node) { 
    if (node.right == null) { 
        if (parent.left == node) { 
            parent.left = node.left;
        } else { 
            parent.right = node.left;
        }
    } else { 
        TreeNode temp = node.right;
        TreeNode father = node;
        while (temp.left != null) { 
            father = temp;
            temp = temp.left;
        }
        if (father.left == temp) { 
            father.left = temp.right;
        } else { 
            father.right = temp.right;
        }
        if (parent.left == node) { 
            parent.left = temp;
        } else { 
            parent.right = temp;
        }
        temp.left = node.left;
        temp.right = node.right;
    }
}

Python

def removeNode(root, value):
    dummy = TreeNode(0)
    dummy.left = root
    parent = findNode(dummy, root, value)
    node = None
    if parent.left and parent.left.val == value:
        node = parent.left
    elif parent.right and parent.right.val == value:
        node = parent.right
    else:
        return dummy.left
    deleteNode(parent, node)
    return dummy.left

def findNode(parent, node, value):
    if not node:
        return parent
    if node.val == value:
        return parent
    if value < node.val:
        return findNode(node,node.left, value)
    else:
        return findNode(node, node.right, value)

def deleteNode(parent, node):
    if not node.right:
        if parent.left == node:
            parent.left = node.left
        else:
            parent.right = node.left
    else:
        temp = node.right
        father = node
        while temp.left:
            father = temp
            temp = temp.left
        if father.left == temp:
            father.left = temp.right
        else:
            father.right = temp.right
        if parent.left == node:
            parent.left = temp
        else:
            parent.right = temp
        temp.left = node.left
        temp.right = node.right


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明数据结构:二叉搜索树的增删查改
喜欢 (1)

您必须 登录 才能发表评论!

加载中……