BST二叉搜索树

本文主要是介绍BST二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概念

二叉搜索树（Binary Search Tree，简称BST），又称为二叉排序树或二叉查找树，是一种特殊的二叉树数据结构。它具有以下基本性质：

1. 节点的值的有序性：对于BST中的任意一个节点，其左子树中所有节点的值都小于该节点的值，而其右子树中所有节点的值都大于该节点的值。
2. 递归定义：BST可以为空树，或者是由一个根节点以及两个互不相交的子树（左子树和右子树）组成，其中左子树和右子树也分别是二叉搜索树。
3. 搜索效率：由于其有序性，BST支持高效的查找、插入和删除操作。在平均和最好情况下，这些操作的时间复杂度为O(log n)，其中n是树中节点的数量。但在最坏情况下，如果树变得不平衡（例如，每个节点都只有左子树或只有右子树，形成一个链状结构），这些操作的时间复杂度会退化到O(n)。
   

示例

首先创建了一个表示二叉树节点的TreeNode类，它包含一个整数值、一个左子节点和一个右子节点。然后我们创建了一个BinaryTree类，它包含一个根节点。insert方法用于向二叉树中插入一个新的值，它调用了一个私有的递归方法insertRecursively来实现插入操作。在insertRecursively方法中，我们首先检查当前节点是否为空，如果为空，则创建一个新的节点并返回。然后我们比较要插入的值和当前节点的值，如果要插入的值小于当前节点的值，则将其插入到左子树中；否则将其插入到右子树中。最后返回当前节点。

public class TreeNode {//整数值Integer val;//左孩子TreeNode left;// 右孩子TreeNode right;TreeNode(int x) {val = x;}}

二叉树的添加

public class BinaryTree {TreeNode root;//添加方法public void insert(int value) {root = insertRecursively(root, value);}//添加的实现（递归）private TreeNode insertRecursively(TreeNode node, int value) {if (node == null) {return new TreeNode(value);}if (value < node.val) {node.left = insertRecursively(node.left, value);} else if (value > node.val) {node.right = insertRecursively(node.right, value);}return node;}}

使用：

public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(3);tree.insert(2);tree.insert(4);tree.insert(5);System.out.println(tree);}

遍历

先序遍历（Pre-order Traversal）

遍历顺序为“根-左-右”。首先访问根节点，然后递归地遍历左子树，最后遍历右子树。先序遍历的递归算法通常用于复制一棵树或计算树的前缀表达式。

public static void preOrder(TreeNode tree) {if (tree != null) {System.out.println(tree.val);preOrder(tree.left);preOrder(tree.right);}}

中序遍历（In-order Traversal）

遍历顺序为“左-根-右”。先递归遍历左子树，然后访问根节点，最后递归遍历右子树。对于二叉搜索树来说，中序遍历会得到一个按节点值升序排列的序列，这是BST特有的性质，常用于BST的排序输出或验证BST的性质。

public static void inOrder(TreeNode tree) {if(tree != null) {inOrder(tree.left);System.out.println(tree.val);inOrder(tree.right);}}

后序遍历（Post-order Traversal）

遍历顺序为“左-右-根”。先递归遍历左子树，然后递归遍历右子树，最后访问根节点。后序遍历常用于计算表达式的后缀表示或树的释放操作。

 public static void afterOrder(TreeNode tree) {if (tree != null) {preOrder(tree.left);preOrder(tree.right);System.out.println(tree.val);}}

查找

递归版本的代码：

    private TreeNode search(TreeNode x, Integer val) {if (x == null) {return null;}int cmp = val.compareTo(x.val);if (cmp < 0) {return search(x.left, val);} else if (cmp > 0) {return search(x.right, val);} else {return x;}}

非递归，用while循环：

private TreeNode iterativeSearch(TreeNode x, Integer key) {while (x!=null) {int cmp = key.compareTo(x.val);if (cmp < 0) {x = x.left;} else if (cmp > 0) {x = x.right;} else {return x;}}return x;}public TreeNode search(Integer key) {return iterativeSearch(node, key);}public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(1);tree.insert(5);tree.insert(2);tree.insert(3);TreeNode search = tree.search(3);System.out.println(search);}

最大最小值

在二叉树中寻找最大值和最小值的效率通常非常高，特别是对于二叉搜索树（BST）。这是因为BST的性质保证了左子树的所有节点值小于根节点值，而右子树的所有节点值大于根节点值。

• 最小值：在BST中，最小值总是位于树的最左侧，即沿着左子节点一直向下走，直到没有左子节点为止的节点，就是最小值。
• 最大值：相应地，最大值总是位于树的最右侧，即沿着右子节点一直向下走，直到没有右子节点为止的节点，就是最大值。

private TreeNode maximum(TreeNode tree) {if (tree == null) {return null;}while(tree.right != null) {tree = tree.right;}return tree;}
private TreeNode minimum(TreeNode tree) {if (tree == null) {return null;}while(tree.left != null) {tree = tree.left;}return tree;}

删除

在二叉树中删除一个节点是一个相对复杂的过程，尤其是当涉及到二叉搜索树（BST）时，因为删除操作需要维护树的性质。删除节点的几种情况：

• 叶子节点（没有子节点）：直接从父节点移除对该节点的引用即可。
• 只有一个子节点：如果待删除节点只有左子节点，将父节点对当前节点的引用改为指向当前节点的左子节点。如果只有右子节点，类似地，将父节点对当前节点的引用改为指向当前节点的右子节点。
• 有两个子节点：这是最复杂的情况。一种常见的做法是找到右子树中的最小节点（或左子树中的最大节点），用这个节点的值替换待删除节点的值，然后删除那个最小（或最大）节点。因为最小节点在右子树中肯定没有左子节点，所以它要么是叶子节点，要么只有一个右子节点，这两种情况都可以简化为前面讨论的简单情况。

// 删除节点的方法public void deleteNode(int key) {node = deleteRec(node, key);}private TreeNode deleteRec(TreeNode root, int key) {if (root == null) {return root;}// 如果键值小于根节点的值，则只可能在左子树中if (key < root.val) {root.left = deleteRec(root.left, key);}// 如果键值大于根节点的值，则只可能在右子树中else if (key > root.val) {root.right = deleteRec(root.right, key);}// 如果键值等于根节点的值，那么这就是我们要删除的节点else {// 节点没有子节点，即为叶子节点if (root.left == null && root.right == null) {root = null;}// 节点只有一个子节点else if (root.left == null) {TreeNode temp = root;root = root.right;temp = null; // 帮助垃圾回收} else if (root.right == null) {TreeNode temp = root;root = root.left;temp = null; // 帮助垃圾回收}// 节点有两个子节点else {// 找到右子树的最小节点TreeNode minNodeForRight = minValueNode(root.right);// 复制最小节点的值到当前节点root.val = minNodeForRight.val;// 删除右子树中最小的节点root.right = deleteRec(root.right, minNodeForRight.val);}}return root;}

这篇关于BST二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---