二叉搜索树（1）

搜索树是一种支持多种动态收集操作的数据结构，包括构造，搜索，插入，删除，查找最小值和最大值等.

二进制搜索树是根据二进制树结构组织的，通常由链表表示.

1. 每个节点代表一个对象二叉排序树查找，该节点包括一个数据部分和一个指针（左，右指针）.

2. 如果某个节点的子节点不存在，则对应的子节点为空.

功能:

1. 根节点的左子树不为空，则左子树中所有节点的值小于根节点的值

2. 根节点的右子树不为空，则右子树中所有节点的值都大于根节点的值

3. 根节点的左右子树也是二叉搜索树

4. 中阶遍历二叉树搜索树，生成的中阶遍历序列是一个递增的有序序列

1. 搜索: 从根节点开始搜索

a. 搜索失败: 二叉树为空

b. 成功搜索:

1）如果搜索值是根节点值，则成功

2）如果搜索值小于根节点值，则在左侧子树中进行递归搜索

3）如果搜索值大于根节点值，则在右子树中递归搜索

2. 删除

a. 如果删除的节点没有子节点，则直接将其父节点对应位置的引用设置为空

b. 如果删除的节点只有一个子节点，只需替换要删除的该节点的子节点

c. 如果删除的节点有两个子节点二叉排序树查找，则用最接近删除的节点的中间顺序后继节点替换它.

3. 插入: 将要插入的节点与根节点进行比较

a. 要插入的节点小于根节点，然后递归到相应根节点的左子树，直到发现左子树为空

b. 要插入的节点大于根节点，然后递归到相应根节点的右子树，直到发现右子树为空

示例:

1. 节点类-节点

 1 /**
 2  * 节点类
 3  * @author Ivy
 4  */
 5 public class Node {
 6     // 节点值
 7     int data;
 8     // 左子树
 9     Node left;
10     // 右子树
11     Node right;
12 
13     public Node(int data, Node left, Node right) {
14         this.data = data;
15         this.left = left;
16         this.right = right;
17     }
18 
19 }

2. 插入算法-InsertBinaryTree

 1 /**
 2  * 节点类
 3  * @author Ivy
 4  */
 5 public class Node {
 6     // 节点值
 7     int data;
 8     // 左子树
 9     Node left;
10     // 右子树
11     Node right;
12 
13     public Node(int data, Node left, Node right) {
14         this.data = data;
15         this.left = left;
16         this.right = right;
17     }
18 
19 }

3. 查找算法-FindBinaryTree

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-241449-1.html