二叉查找树（一）

　　一个二叉查找树是按照二叉树的结构来组织的，不熟悉二叉树的童鞋请查下资料，这里不多讲了。先来讲一下二叉查找树的性质吧。

二叉查找树的性质

　　用比较通俗易懂的语言来描述一下就是，二叉查找树的左子树上的结点不比父结点大，右子树上的结点不比父结点小，即，设x为二叉查找树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树中的一个结点，则key[x]<=key[y]。此处的key[x]，key[y]表示的是x结点和y结点的关键字。

　　知道了二叉查找树的性质，我们就可以来编程了，但是在这之前我们需要先将二叉树在计算机里表示出来，因此要讲一下二叉树的存储结构。

二叉树的存储结构

　　二叉树的存储结构分为两种：顺序存储和链式存储。

　　顺序存储结构就是用数组来存储二叉树，具体做法为将一棵二叉树从上往下，从左到右顺序进行编号，依次存放到数组中，如果不是满二叉树，则要在数组中将空结点的位置空出来。

　　链式存储就是用链表的形式将二叉树存储起来，每个结点有左孩子，右孩子，数据以及父结点等几个域。关于存储结构可以参考：

　　http://www.cnblogs.com/abatei/archive/2008/05/23/1205707.html。

二叉树的结点定义

　　在这里，我选用链式的存储结构，并将二叉查找树的结点定义为：

TreeNode.java

 1 package com.alfred.bstree;
 2 
 3 /**
 4  * 二叉查找树结点
 5  * @author Alfred
 6  */
 7 public class TreeNode {
 8     //key值
 9     private int key;
10     //记录相同的key值的结点个数
11     private int dataNum;
12     //下面三个大家都懂得！
13     private TreeNode parent;
14     private TreeNode left;
15     private TreeNode right;
16     public TreeNode(int key){
17         this.key = key;
18         this.dataNum = 1;
19     }
20     public String toString(){
21         return ""+key+"*"+dataNum+"  ";
22     }
23     /**
24      * 偷个懒...自加方法
25      * @author Alfred
26      */
27     public void incNumByOne(){
28         this.dataNum++;
29     }
30     
31     /**
32      * @return the key
33      */
34     public int getKey() {
35         return key;
36     }
37     /**
38      * @param key the key to set
39      */
40     public void setKey(int key) {
41         this.key = key;
42     }
43     /**
44      * @return the dataNum
45      */
46     public int getDataNum() {
47         return dataNum;
48     }
49     /**
50      * @param dataNum the dataNum to set
51      */
52     public void setDataNum(int dataNum) {
53         this.dataNum = dataNum;
54     }
55     /**
56      * @return the parent
57      */
58     public TreeNode getParent() {
59         return parent;
60     }
61     /**
62      * @param parent the parent to set
63      */
64     public void setParent(TreeNode parent) {
65         this.parent = parent;
66     }
67     /**
68      * @return the left
69      */
70     public TreeNode getLeft() {
71         return left;
72     }
73     /**
74      * @param left the left to set
75      */
76     public void setLeft(TreeNode left) {
77         this.left = left;
78     }
79     /**
80      * @return the right
81      */
82     public TreeNode getRight() {
83         return right;
84     }
85     /**
86      * @param right the right to set
87      */
88     public void setRight(TreeNode right) {
89         this.right = right;
90     }    
91 }

　　好了有了二叉树结点的定义，我们就可以来构造我们的二叉查找树了。