概念
二叉搜索树(Binary Search Tree,简称BST),又称为二叉排序树或二叉查找树,是一种特殊的二叉树数据结构。它具有以下基本性质:
- 节点的值的有序性:对于BST中的任意一个节点,其左子树中所有节点的值都小于该节点的值,而其右子树中所有节点的值都大于该节点的值。
- 递归定义:BST可以为空树,或者是由一个根节点以及两个互不相交的子树(左子树和右子树)组成,其中左子树和右子树也分别是二叉搜索树。
- 搜索效率:由于其有序性,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;}