二叉排序树（BST）创建,删除,查找操作

binary search tree，中文翻译为二叉搜索树、二叉查找树或者二叉排序树。简称为BST一：二叉搜索树的定义他的定义与树的定义是类似的，也是一个递归的定义：1、要么是一棵空树2、如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值3、其左右子树也是二叉搜索树在算法导论中的定义：下图中是BST的两个例子：其中（b）图中的树是很不平衡的（所谓不平衡是值左右子树的高度差比较大）BST在数据结构中占有很重要的地位，一些高级树结构都是其的变种，例如AVL树、红黑树等，因此理解BST对于后续树结构的学习有很好的作用。同时利用BST可以进行排序，称为二叉排序，也是很重要的一种思想。相关代码如下:/** 二叉排序树（BST）创建,删除,查找操作 **/#include<stdio.h>#include<stdlib.h>#define LENGTH 15typedef int ElemType; //数据类型 typedef struct BiTNode{ElemTypedata;struct BiTNode *lchild;struct BiTNode *rchild;}BiTNode,*BiTree;/** * 向下遍历查找给定结点的相邻节点,以便插入指定节点 */void searchBiTreeNode（BiTree &root,BiTree &node）{if（root == NULL）{return;}if（root->data > node->data）{searchBiTreeNode（root->lchild,node）; //递归遍历搜索if（root->lchild == NULL）{ root->lchild = node;}}else if（root->data < node->data）{searchBiTreeNode（root->rchild,node）;if（root->rchild == NULL）{ root->rchild = node;}}}/** * 插入指定节点node */void insertNode（BiTree &biTree,BiTree &node）{if（biTree==NULL）{biTree = node;}else{searchBiTreeNode（biTree,node）;}}/** * 删除指定元素x */void deleteNode（BiTree &root,ElemType x）{if（root == NULL）{return;}if（root->data>x）{deleteNode（root->lchild,x）;}else if（root->data<x）{deleteNode（root->rchild,x）;}else{ //查找到了删除节点if（root->lchild == NULL）{ //左子树为空 BiTree tempNode = root; root = root->rchild; free（tempNode）;}else if（root->rchild == NULL）{ //右子树为空 BiTree tempNode = root; root = root->lchild; free（tempNode）;}else{//左右子树都不为空//一般的删除策略是左子树的最大数据或右子树的最小数据代替该节点（这里采用查找左子树最大数据来代替）BiTree tempNode = root->lchild;if（tempNode->rchild！=NULL）{tempNode = tempNode->rchild;}root->data = tempNode->data;deleteNode（root->lchild,tempNode->data）;}}}/** * 查找指定元素x所在的节点 */BiTree BST_Search（BiTree &root,ElemType x）{if（root == NULL）{return NULL;}else if（root->data>x）{return BST_Search（root->lchild,x）;}else if（root->data<x）{return BST_Search（root->rchild,x）;}else{return root;}}/** * 二叉排序树创建 */void createBiOrderTree（BiTree &biTree,ElemType arr[]）{for（int i=0;i<LENGTH;i++）{BiTree s = （BiTree）malloc（sizeof（BiTNode））;s->data = arr[i];s->lchild = NULL;s->rchild = NULL;insertNode（biTree,s）;}}/** * 中序打印二叉树 */ void midSearchBiTreePrint（BiTree &biTree）{if（biTree == NULL）{return;}midSearchBiTreePrint（biTree->lchild）;printf（"%d ",biTree->data）;midSearchBiTreePrint（biTree->rchild）;}/** * 测试程序入口 */int main（）{ElemType arr[LENGTH] = {62,88,58,47,35,73,51,99,37,93,23,27,45,21,12};BiTree biTree = NULL;/** 创建二叉排序树,并测试数据 **/createBiOrderTree（biTree,arr）;midSearchBiTreePrint（biTree）;printf（" "）;/** 从二叉排序树中删除指定元素,并测试数据 **/deleteNode（biTree,35）;midSearchBiTreePrint（biTree）;printf（" "）;/** 二叉排序树查找指定元素操作,并测试数据 **/BiTree searchNode = BST_Search（biTree,27）;if（searchNode == NULL）{fprintf（stdout,"没有查找到节点 "）;}else{if（searchNode->lchild==NULL && searchNode->rchild==NULL）{ //叶子节点printf（"所查找的节点x=%d是叶子节点 ",searchNode->data）;}else{ if（searchNode->lchild ！= NULL）{printf（"x=%d所在节点的左孩子: %d ",searchNode->data,searchNode->lchild->data）;}if（searchNode->rchild ！= NULL）{printf（"x=%d所在节点的右孩子: %d ",searchNode->data,searchNode->rchild->data）;}}}return 0;}运行结果截图:二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-04/130209.htm