1.關於二叉搜索樹的定義,二叉搜索樹是具有以下特征的一棵二叉樹:
(1)若一個節點有左孩子,則此節點值大於它左孩子的節點值;
(2)若一個孩子有右孩子,則此節點值不小於它右孩子的節點值;
(3)對其左孩子和右孩子為根節點的子樹遞歸的具有此條性質。
在《COMPUTER ALGORITHMS Introduction to Design and Analysis》一書中對BST的定義如下:
A binary tree in which the nodes have keys keys from an ordered set has the binary search tree property if the key at each node is greater than all the keys in its left subtree and less than or equal to all keys in its right subtree.In this case the binary tree is called a binary search tree.
2.以下代碼分成三部分:
(1)BST的創建
(2)BST的查找
(3)BST的遍歷輸出
完整的代碼如下:
/* @class Node{} 在定義二叉樹之前先定義節點的類 */ class Node{ int value; //節點的值 Node l_child; //左孩子 Node r_child; //又孩子 Node(int value) //自定義的構造函數 { this.value=value; this.l_child=null; this.r_child=null; } } /*@ class BinaryTree 定義二叉樹*/ public class BinarySearchTree { private Node root; //根節點 BinarySearchTree(){ root=null; } //帶形參和不帶形參的構造函數 BinarySearchTree(int []arr){ for(int i:arr) insert(i); } private void insert(int value){ root=insert(root,value); ///這裡的root是根節點,每次從根節點開始遞歸查找待插入的節點 } private Node insert(Node node,int value) { if(node==null) node=new Node(value); else if(value<node.value) node.l_child=insert(node.l_child,value); //遞歸的找到待插入的位置 else node.r_child=insert(node.r_child,value); return node; //返回已插入值後的node,賦值給root } private void visit(Node node) { if(node==null) return; int value=node.value; System.out.println(value); } private void in_order_traves(Node node) { if(node==null) return; else { in_order_traves(node.l_child); //中序遍歷,左根右 visit(node); in_order_traves(node.r_child); } } private Node bstSearch(Node root,int key) { Node found; if(root==null) found=null; else if(root.value==key) found=root; else if(root.value>key) found=bstSearch(root.l_child,key); else found=bstSearch(root.r_child,key); return found; } public static void main(String[]args) { int arr[]={3,5,10,6,4,12,8,9,7,2}; BinarySearchTree bitree=new BinarySearchTree(arr); System.out.println(bitree.bstSearch(bitree.root, 5).value); bitree.in_order_traves(bitree.root); } }