二叉排序树(Binary Sort Tree)&＃xff0c;又称为二叉查找树(Binary Search Tree) &＃xff0c;即BSTree。
构造一棵二叉排序树的目的&＃xff0c;其实并不是为了排序&＃xff0c;而是为了提高查找和插入删除的效率。
什么是二叉排序树呢&＃xff1f;二叉排序树具有以下几个特点。
&＃xff08;1&＃xff09;若根节点有左子树&＃xff0c;则左子树的所有节点都比根节点小。
&＃xff08;2&＃xff09;若根节点有右子树&＃xff0c;则右子树的所有节点都比根节点大。
&＃xff08;3&＃xff09;根节点的左&＃xff0c;右子树也分别是二叉排序树。
1、二叉排序树的图示
下面是二叉排序树的图示&＃xff0c;通过它可以加深对二叉排序树的理解。
2、二叉排序树常见的操作及思路
下面是二叉排序树常见的操作及思路。
2-1、插入节点
思路&＃xff1a;比如我们要插入数字20到这棵二叉排序树中。那么步骤如下&＃xff1a;
&＃xff08;1&＃xff09;首先将20与根节点进行比较&＃xff0c;发现比根节点小&＃xff0c;所以继续与根节点的左子树30比较。
&＃xff08;2&＃xff09;发现20比30也要小&＃xff0c;所以继续与30的左子树10进行比较。
&＃xff08;3&＃xff09;发现20比10要大&＃xff0c;所以就将20插入到10的右子树中。
此时的二叉排序树如下图&＃xff1a;
2-2、查找节点
比如我们要查找节点10&＃xff0c;那么思路如下&＃xff1a;
&＃xff08;1&＃xff09;还是一样&＃xff0c;首先将10与根节点50进行比较&＃xff0c;发现比根节点要小&＃xff0c;所以继续与根节点的左子树30进行比较。
&＃xff08;2&＃xff09;发现10比左子树30要小&＃xff0c;所以继续与30的左子树10进行比较。
&＃xff08;3&＃xff09;发现两值相等&＃xff0c;即查找成功&＃xff0c;返回10的位置。
2-3、删除节点
删除节点的情况相对复杂&＃xff0c;主要分为以下三种情形&＃xff1a;
&＃xff08;1&＃xff09;删除的是叶节点(即没有孩子节点的)。比如20&＃xff0c;删除它不会破坏原来树的结构&＃xff0c;最简单。如图所示。
&＃xff08;2&＃xff09;删除的是单孩子节点。比如90&＃xff0c;删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。
&＃xff08;3&＃xff09;删除的是有左右孩子的节点。比如根节点50
这里有一个问题就是删除它后&＃xff0c;谁将作为根节点&＃xff1f;利用二叉树的中序遍历&＃xff0c;就是右节点的左子树的最左孩子。
3、代码
有了思路之后&＃xff0c;下面就开始写代码来实现这些功能。
BSTreeNode.java
public class BSTreeNode {public int data; public BSTreeNode left; public BSTreeNode right; public BSTreeNode(int data) { this.data &＃61; data; } }
BSTreeOperate.java
/*** 二叉排序树的常见操作*/
public class BSTreeOperate { // 树的根节点 public BSTreeNode root; // 记录树的节点个数 public int size; /** * 创建二叉排序树 * * &＃64;param list * &＃64;return */ public BSTreeNode create(int[] list) { for (int i &＃61; 0; i
BSTreeOperateTest.java
public class BSTreeOperateTest {public static void main(String[] args) { BSTreeOperate bsTreeOperate &＃61; new BSTreeOperate(); int[] list &＃61; new int[]{50, 30, 70, 10, 40, 90, 80}; System.out.println("*********创建二叉排序树*********"); BSTreeNode bsTreeNode &＃61; bsTreeOperate.create(list); System.out.println("中序遍历原始的数据&＃xff1a;"); bsTreeOperate.LDR(bsTreeNode); System.out.println(""); System.out.println(""); System.out.println("********查找节点*******"); System.out.println("元素20是否在树中&＃xff1a;" &＃43; bsTreeOperate.search(bsTreeNode, 20)); System.out.println(""); System.out.println("********插入节点*******"); System.out.println("将元素20插入到树中"); bsTreeOperate.insert(20); System.out.println("中序遍历&＃xff1a;"); bsTreeOperate.LDR(bsTreeNode); System.out.println(""); System.out.println(""); System.out.println("********查找节点*******"); System.out.println("元素20是否在树中&＃xff1a;" &＃43; bsTreeOperate.search(bsTreeNode, 20)); System.out.println(""); } }
运行结果&＃xff1a;
欢迎转载&＃xff0c;但请保留文章原始出处
本文地址&＃xff1a;http://www.cnblogs.com/nnngu/p/8294714.html
京公网安备 11010802041100号