二叉搜索树最大特征是：左边子结点的值<当前结点的值，右边子结点的值＞当前结点的值。
依照这个特征，可以使用递归和非递归两种方式建立一颗二叉搜索树。
下面是我的代码，分明列举了递归和非递归的建立方式。最初写的代码与正确版本大致相同，但程序总是运行不通过，debug后发现问题在于指针操作错误。自以为对c语言非常熟稔了，但还是犯下如此幼稚的错误，所以贴出这个错误，作为一个警示。
2014/5/24 ps:原来二叉搜索树最难的地方在于删除操作，所以补充一个删除操作。此外，还明白了书本介绍二叉搜索树的原因，因为很多更复杂的树结构，是以此为基础的，如b树，b+树，avl树等等。
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef struct NODE { NODE * pleft; NODE * pright; int ivalue; } node; /* 错误示例，实际上这个函数并没有连接起新建的结点 void insert_bitree(node *pt, int value) { if(pt == NULL) { pt = (node *) malloc ( sizeof(node) ); pt->ivalue = value; pt->pleft = NULL; pt->pright = NULL; return ; } else if( value < pt->ivalue) { insert_bitree(pt->pleft, value); } else { insert_bitree(pt->pright, value); } } */ void insert_bitree(node **ppt, int value) //递归方式1 { if(*ppt == NULL) { *ppt = (node *) malloc ( sizeof(node) ); (*ppt)->ivalue = value; (*ppt)->pleft = NULL; (*ppt)->pright = NULL; return ; } else if( value < (*ppt)->ivalue) { insert_bitree(&((*ppt)->pleft), value); //将指向指针的指针重定位到当前结点的pleft } else { insert_bitree(&((*ppt)->pright), value); //将指向指针的指针重定位到当前结点的pright } } node* create_searchtree(node *t, int temp) //递归方式2 { if (t == NULL) { // 若当前树为空 t = (node *)malloc(sizeof(node) * 1); if (t == NULL) { printf("内存分配失败! "); exit(EXIT_FAILURE); } t->ivalue = temp; t->pleft = NULL; t->pright = NULL; }else if (t->ivalue > temp) { // 如果比当前结点小，则插入左子树 t->pleft = create_searchtree(t->pleft, temp); }else if (t->ivalue < temp){ // 如果比当前结点大，则插入右子树 t->pright = create_searchtree(t->pright, temp); } return t; } node * creat_bitree(int value[], int len) //非递归方式 { int i, flag; node *before; node *tmp; node *pt = (node *)malloc( sizeof(node) ); pt->ivalue = value[0]; pt->pleft = pt->pright = NULL; flag = 0; for(i = 1; i < len; i++) { tmp = pt; while(tmp != NULL) { if ( value[i] < (tmp)->ivalue) { before = tmp; // 存储当前结点的位置 flag = -1; //标志位，表明向左子树探索 tmp = (tmp)->pleft; } else { before = tmp; flag = 1; tmp = tmp->pright; } } if(flag == -1) //将输入值插入当前结点的左子树 { before->pleft = (node *) malloc (sizeof(node) ); before->pleft->ivalue = value[i]; before->pleft->pleft = before->pleft->pright = NULL; } else if( flag == 1) { before->pright = (node *) malloc (sizeof(node) ); before->pright->ivalue = value[i]; before->pright->pleft = before->pright->pright = NULL; } } return pt; } void preorder(node *pt) //先序访问二叉树 { if(pt != NULL) { printf("%d ", pt->ivalue); preorder(pt->pleft); preorder(pt->pright); } } void postorder(node *pt) { if(pt != NULL) { postorder(pt->pleft); postorder(pt->pright); printf("%d ", pt->ivalue); } } int main() { int a[8] = {1, 2, 7, 4, 5, 19, 9, 3}; int len = sizeof(a) / sizeof(int); #if 1 int i; node *pt = (node *)malloc(sizeof(node)); assert(pt != NULL); pt->ivalue = a[0]; pt->pleft = pt->pright = NULL; for(i = 1; i < 8; i++) { //pt = create_searchtree(pt, a[i]); insert_bitree(&pt, a[i]); } #else node *pt = creat_bitree(a, len); #endif preorder(pt); return 0; }
node * find_elem(int x, node * t) { if( t == NULL) return NULL; if( x < t->ivalue) return find_elem(x, t->pleft); else if ( x > t->ivalue) return find_elem(x, t->pright); else return t; } node * find_min(node *t) { if( t == NULL) return NULL; else if( t->pleft == NULL) return t; else return find_min(t->pleft); } node * delete_elem(int x, node *t) { node * tmp; if( t == NULL) // 已到树底，并且树中不存在该元素 { printf("element: %d doesn't exist ", x); exit(-1); } else if( x < t->ivalue ) // 进入左子树 t->pleft = delete_elem(x, t->pleft ); else if( x > t->ivalue ) t->pright = delete_elem(x, t->pright); else if( t->pleft && t->pright) // 找到该元素，但该元素还有两个子节点，从最右端节点找到最小点，进行替换该元素所在节点，替换后该树仍为二叉搜索树 { tmp = find_min(t->pright); t->ivalue = tmp->ivalue; t->pright = delete_elem(t->ivalue, t->pright); } else // 找到该元素，但该元素仅有一个子节点 { tmp = t; if( t->pleft == NULL) t = t->pright; else if( t->pright == NULL) t = t->pleft; free(tmp); } return t; }