首页 > 代码库 > 二叉搜索树的建立
二叉搜索树的建立
二叉搜索树最大特征是：左边子结点的值<当前结点的值，右边子结点的值＞当前结点的值。
依照这个特征，可以使用递归和非递归两种方式建立一颗二叉搜索树。
下面是我的代码，分明列举了递归和非递归的建立方式。最初写的代码与正确版本大致相同，但程序总是运行不通过，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 = http://www.mamicode.com/value;>*/void insert_bitree(node **ppt, int value) //递归方式1{ if(*ppt == NULL) { *ppt = (node *) malloc ( sizeof(node) ); (*ppt)->ivalue =http://www.mamicode.com/ 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("内存分配失败!\n"); exit(EXIT_FAILURE); } t->ivalue =http://www.mamicode.com/ 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 = http://www.mamicode.com/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 =http://www.mamicode.com/ value[i]; before->pleft->pleft = before->pleft->pright = NULL; } else if( flag == 1) { before->pright = (node *) malloc (sizeof(node) ); before->pright->ivalue =http://www.mamicode.com/ value[i]; before->pright->pleft = before->pright->pright = NULL; } } return pt;}void preorder(node *pt) //先序访问二叉树{ if(pt != NULL) { printf("%d\n", pt->ivalue); preorder(pt->pleft); preorder(pt->pright); }}void postorder(node *pt){ if(pt != NULL) { postorder(pt->pleft); postorder(pt->pright); printf("%d\n", 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 = http://www.mamicode.com/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\n", 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 = http://www.mamicode.com/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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。