Binary Search Tree(BST)二叉搜索树的实现-Java语言

Binary Search Tree(BST)二叉搜索树的实现-Java语言

1.关于二叉搜索树的定义，二叉搜索树是具有以下特征的一棵二叉树：

（1）若一个节点有左孩子，则此节点值大于它左孩子的节点值；

（2）若一个孩子有右孩子，则此节点值不小于它右孩子的节点值；

（3）对其左孩子和右孩子为根节点的子树递归的具有此条性质。

在《COMPUTER ALGORITHMS　Introduction to Design and Analysis》一书中对ＢＳＴ的定义如下：

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); }       }