二叉查找树（一）

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

二叉查找树按照二叉树结构组织，通常采用链表表示。
   1.每一个节点表示一个对象，节点包括data数据部分，指针（left，right指针）。
   2.若某节点的儿子节点不存在，则相应的儿子结点为空。

特点：
   1.根节点的左子树不为空，则左子树所有节点的值均小于根节点的值
   2.根节点的右子树不为空，则右子树所有节点的值均大于根节点的值
   3.根节点的左右子树本身也是二叉查找树
   4.中序遍历二叉查找树，所得到的中序遍历序列是一个递增、有序的序列

1.查找：从根节点开始查找
   a.查找失败：二叉树为空
   b.查找成功：
       1)若，查找值就是根节点值，那么成功
       2)若，查找值小于根节点值，在左子树递归查找
       3)若，查找值大于根节点值，在右子树递归查找
2.删除
   a.若，删除的节点没有子节点，直接将其父节点的相应位置的引用设置为空
   b.若，删除的节点只有一个子节点，只要将这个要删除的节点的子节点代替它的位置即可
   c.若，删除的节点有两个子子节点，用最接近于删除节点的中序后继节点来替代它。
3.插入：将待插入的节点与根节点比较
   a.待插入的节点小于根节点，，递归到相应根节点的左子树，直到找到左子树为空的位置
   b.待插入的节点大于根节点，，递归到相应根节点的右子树，直到找到右子树为空的位置
范例：
1.节点类-Node

 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

  1 /**
  2  * @Description: 二叉查找树查找算法
  3  * @author Ivy
  4  */
  5 public class FindBinaryTree {
  6 //    根节点
  7     private Node root;
  8 //    插入节点
  9     public void add(int data) {
 10         System.out.println("插入节点：" + data);
 11         if (null == root) {
 12             root = new Node(data, null, null);
 13         } else {
 14             addTree(root,data);
 15         }
 16     }
 17 
 18     private void addTree(Node root, int data) {
 19         if (root.data > data) {
 20 //            进入左子树
 21             if (null == root.left) {
 22                 root.left = new Node(data, null, null);
 23             } else {
 24                 addTree(root.left, data);//吊本身的方法，实现递归进入左子树
 25             }
 26         } else {
 27 //            进入右子树
 28             if (null == root.right) {
 29                 root.right = new Node(data, null, null);
 30             } else {
 31                 addTree(root.right, data);//吊本身的方法，实现递归进入右子树
 32             }
 33         }
 34         
 35     }
 36     
 37 //    中序遍历二叉查找树
 38     public void show() {
 39         showTree(root);
 40     }
 41 
 42     private void showTree(Node root) {
 43         if (null != root.left) {
 44             showTree(root.left);
 45         }
 46         System.out.println(root.data + " ");
 47         if (null != root.right) {
 48             showTree(root.right);
 49         }
 50         
 51     }
 52 //    查找算法
 53     public Node searchNode(int findData) {
 54         Node node = null;
 55         Node rootNode = root;
 56         while (true) {
 57             if (null == rootNode) {
 58                 break;
 59             }
 60             if (rootNode.data == findData) {
 61                 node = rootNode;
 62                 break;
 63             }
 64             if (rootNode.data > findData) {
 65                 rootNode = rootNode.left;
 66             } else {
 67                 rootNode = rootNode.right;
 68             }
 69             
 70         }
 71         return node;
 72     }
 73     
 74 //    测试
 75     public static void main(String[] args) {
 76         FindBinaryTree tree = new FindBinaryTree();
 77         tree.add(9);
 78         tree.add(13);
 79         tree.add(45);
 80         tree.add(2);
 81         tree.add(34);
 82         tree.add(45);
 83         tree.add(5);
 84         tree.add(3);
 85         tree.add(78);
 86         tree.add(56);
 87         tree.show();
 88         
 89         int findData = 0;
 90         Scanner input = new Scanner(System.in);
 91         System.out.println("请输入要查找的节点值：");
 92         findData = input.nextInt();
 93         Node node = tree.searchNode(findData);
 94         if (null == node) {
 95             System.out.println("查找失败！");
 96         } else {
 97             System.out.println("查找成功，查找的节点值为：" + node.data);
 98         }
 99     }
100     
101 }