07_二叉搜索树
二叉搜索树又叫二叉排序树，二叉查找树。
7.1 定义
在二叉树的基础上，增加了几个规则约束（左小右大）：
- 如果它的左子树不空，则左子树上所有的值均小于它的根节点的值
- 若它的右子树不空，则右子树上所有的值均大于它的根节点的值
- 它的左、右树又分为二叉排序树
7.2 申明
c 实现：
typedefintElement_t;//定义节点结构typedefstructtreenode{Element_t data;structtreenode*left;structtreenode*right;}TreeNode_t;//定义二叉搜索树结构typedefstruct{intcount;TreeNode_t*root;}BinarySearchTree_t;Java 实现：
Element:
packagecom.Sonnet.Element;publicclassElement{privateintdata;publicElement(){}publicElement(intdata){this.data=data;}@OverridepublicStringtoString(){returnString.valueOf(this.data);}@OverridepublicinthashCode(){returnInteger.hashCode(this.data);}@Overridepublicbooleanequals(Objectobj){if(this==obj)returntrue;if(this.getClass()!=obj.getClass())returnfalse;Elementother=(Element)obj;returnthis.data==((Element)obj).data;}publicintgetData(){returndata;}}TreeNode:
packagecom.Sonnet.BinarySearchTree;importcom.Sonnet.Element.Element;publicclassTreeNode{privateElementdata;privateTreeNodeleft;privateTreeNoderight;publicTreeNode(){};publicTreeNode(Elementdata){this.data=data;this.left=null;this.right=null;}}BinarySearchTree:
packagecom.Sonnet.BinarySearchTree;publicclassBinarySearchTree{privateTreeNoderoot;privateintcount;}7.3 创建
c 实现：
/*创建树*/BinarySearchTree_t*createBinarySearchTree(){BinarySearchTree_t*tree=malloc(sizeof(BinarySearchTree_t));if(tree==NULL){printf("malloc failed\n");returnNULL;}//初始化tree->count=0;tree->root=NULL;returntree;}Java 实现：
publicBinarySearchTree(){this.root=null;this.count=0;}7.4 插入
7.4.1 递归
c 实现：
/*创建节点*/staticTreeNode_t*createTreeNode(Element_t data){TreeNode_t*node=malloc(sizeof(TreeNode_t));if(node==NULL){printf("malloc failed\n");returnNULL;}//初始化node->data=data;node->left=NULL;node->right=NULL;returnnode;}/*插入节点*/staticTreeNode_t*insertNode(BinarySearchTree_t*tree,TreeNode_t*node,Element_t data){if(node==NULL){tree->count++;returncreateTreeNode(data);}if(data<node->data){node->left=insertNode(tree,node->left,data);}elseif(data>node->data){node->right=insertNode(tree,node->right,data);}returnnode;}/*递归插入*/voidinsertTreeNodeRecur(BinarySearchTree_t*tree,Element_t data){if(tree==NULL)return;tree->root=insertNode(tree,tree->root,data);}Java 实现：
/*插入节点*/privateTreeNodeinsertNode(TreeNodenode,Elementdata){if(node==null){this.count++;returnnewTreeNode(data);}if(data.getData()<node.getData().getData()){node.setLeft(insertNode(node.getLeft(),data));}elseif(data.getData()>node.getData().getData()){node.setRight(insertNode(node.getRight(),data));}returnnode;}/* 功能： 递归插入 参数： 节点数据 返回值： 无 */publicvoidinsertTreeNodeRecur(Elementdata){this.root=insertNode(this.root,data);}7.4.2 非递归
c 实现：
/*插入节点非递归*/voidinsertTreeNodeNoRecur(BinarySearchTree_t*tree,Element_t data){if(tree==NULL)return;//辅助指针TreeNode_t*pre=NULL;TreeNode_t*cur=tree->root;while(cur){pre=cur;if(data<cur->data){cur=cur->left;}elseif(data>cur->data){cur=cur->right;}//如果相等就直接返回else{return;}}//创建节点TreeNode_t*node=createTreeNode(data);if(pre){if(data<pre->data){pre->left=node;}else{pre->right=node;}}//当根节点不存在时，pre和cur都为空else{tree->root=node;}tree->count++;}Java 实现：
/* 功能：非递归插入节点 参数：节点数据 返回值：无 */publicvoidinsertTreeNodeNoRecur(Elementdata){//辅助指针TreeNodepre=null;TreeNodecur=this.root;while(cur!=null){pre=cur;if(data.getData()<cur.getData().getData()){cur=cur.getLeft();}elseif(data.getData()>cur.getData().getData()){cur=cur.getRight();//相等直接返回}else{return;}}//创建节点TreeNodenode=newTreeNode(data);if(pre!=null){if(data.getData()<pre.getData().getData()){pre.setLeft(node);}else{pre.setRight(node);}//当根节点为空时，pre和cur都为空}else{this.root=node;}this.count++;}7.5 访问节点数据
c 实现：
/*访问节点数据*/voidvisitTreeNode(TreeNode_t*node){if(node){printf("%d\t",node->data);}}Java 实现：
publicvoidvisitTreeNode(TreeNodenode){if(node==null)return;System.out.print(node.getData()+"\t");}7.6 释放
c 实现：
/*释放节点*/staticvoidreleaseTreeNode(BinarySearchTree_t*tree,TreeNode_t*node){if(node==NULL)return;releaseTreeNode(tree,node->left);releaseTreeNode(tree,node->right);free(node);tree->count--;}/*释放*/voidreleaseBinarySearchTree(BinarySearchTree_t*tree){releaseTreeNode(tree,tree->root);printf("tree have %d node\n",tree->count);free(tree);}Java 实现：
/*释放节点*/privatevoidreleaseTreeNode(TreeNodenode){if(node==null){return;}releaseTreeNode(node.getLeft());releaseTreeNode(node.getRight());node.setLeft(null);node.setRight(null);this.count--;}/* 功能： 释放二叉搜索树 参数： 无 返回值： 无 */publicvoidreleaseBinarySearchTree(){releaseTreeNode(this.root);this.root=null;System.out.println("this tree have "+this.count+" node");}7.7 中序遍历
c 实现：
/*中序遍历节点*/staticvoidinOrderTreeNode(TreeNode_t*node){if(node==NULL)return;inOrderTreeNode(node->left);visitTreeNode(node);inOrderTreeNode(node->right);}/*中序遍历*/voidinOrderBinarySearchTree(BinarySearchTree_t*tree){inOrderTreeNode(tree->root);printf("\n");}Java 实现：
/*中序遍历节点*/privatevoidinOrderTreeNode(TreeNodenode){if(node==null)return;this.inOrderTreeNode(node.getLeft());this.visitTreeNode(node);this.inOrderTreeNode(node.getRight());}/* 功能： 中序遍历 参数： 无 返回值: 无 */publicvoidinOrderBinarySearchTree(){inOrderTreeNode(this.root);System.out.println();}7.8 获取高度
c 实现：
/*高度*/intheightBinarySearchTree(TreeNode_t*node){if(node==NULL)return0;intrightHeight=heightBinarySearchTree(node->right);intleftHeight=heightBinarySearchTree(node->left);if(leftHeight>rightHeight){return++leftHeight;}else{return++rightHeight;}}Java 实现：
/* 功能： 获取二叉搜索树高度 参数： 根节点 返回值： 高度 */publicintheightBinarySearchTree(TreeNoderoot){if(root==null)return0;intleftHeight=this.heightBinarySearchTree(root.getLeft());intrightHeight=this.heightBinarySearchTree(root.getRight());if(leftHeight>rightHeight){return++leftHeight;}else{return++rightHeight;}}7.9 搜索
c 实现：
/*搜索*/TreeNode_t*searchTreeNode(BinarySearchTree_t*tree,Element_t data){TreeNode_t*node=tree->root;while(node){if(data<node->data){node=node->left;}elseif(data>node->data){node=node->right;}elsereturnnode;}returnNULL;}Java 实现：
/* 功能： 搜索节点 参数： 数据 返回值： 节点 */publicTreeNodesearchTreeNode(Elementdata){TreeNodenode=this.root;while(node!=null){if(data.getData()<node.getData().getData()){node=node.getLeft();}elseif(data.getData()>node.getData().getData()){node=node.getRight();}else{returnnode;}}returnnull;}e"> Java 实现：
/* 功能： 搜索节点 参数： 数据 返回值： 节点 */publicTreeNodesearchTreeNode(Elementdata){TreeNodenode=this.root;while(node!=null){if(data.getData()<node.getData().getData()){node=node.getLeft();}elseif(data.getData()>node.getData().getData()){node=node.getRight();}else{returnnode;}}returnnull;}
