/******************************** 运行环境:http://www.anycodes.cn/zh/ 原文:http://blog.csdn.net/u014488381/article/details/41719765/ 二叉排序树的查找算法的C代码实现 修改以直接测试 待C++类封装版本 *********************************/ #include#include typedef int Elemtype; typedef struct BiTNode{ Elemtype data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; /*/在给定的BST中插入结点,其数据域(数值)为element/*/ void BSTInsert( BiTree *t, Elemtype element ) {/*/每次插入 开辟空间/*/ if( NULL == *t ) { (*t) = (BiTree)malloc(sizeof(BiTNode)); (*t)->data = element; (*t)->lchild = (*t)->rchild = NULL; } /*/依据二叉搜索树性质/*/ if( element == (*t)->data ) return ; /*/不允许有重复的数据,若遇到直接不处理/*/ else if( element < (*t)->data ) BSTInsert( &(*t)->lchild, element ); else BSTInsert( &(*t)->rchild, element ); } /*/创建BST/*/ void CreateBST( BiTree *t, Elemtype *a, int n ) { (*t) = NULL; for( int i=0; i data ) printf("查找成功!\n"); else if( (key < p->data) && (NULL != p->lchild) ) SearchBST( p->lchild , key ); else if( (key > p->data) && (NULL != p->rchild) ) SearchBST( p->rchild , key ); else printf("无此元素!\n"); } } /*/BST的迭代查找/*/ void _SearchBST( BiTree t, Elemtype key ) { BiTree p; p = t; while( NULL != p && key != p->data ) /*/结点存在而数值不等时/*/ { if( key < p->data ) p = p->lchild ; else p = p->rchild ; }/*/ 走出循环后 p指针总是指向找到的元素 或者 叶子结点下的空结点/*/ if( NULL != p ) printf("查找成功!\n"); else printf("无此元素!\n"); } /*/BST结点的删除 本二叉树内容重点/*/ void DelBSTNode( BiTree t, Elemtype key ) { BiTree p, q; p = t; Elemtype temp; /*/ 先遍历找这元素/*/ while( NULL != p && key != p->data ) { q = p; /*/ q总是在结点p的上方(当p不是根结点时q总是父亲) p就是我们要删的元素 /*/ if( key < p->data ) p = p->lchild ; else p = p->rchild ; } if( NULL == p ) printf("无此元素!\n"); /*/找到元素 会有如下几个情况 1. 2. 3. q q q /\ / \ / \ p p p p p p / \ / \ / \ x x x x x x /*/ else { /*/情况1:结点p的双亲结点为q,且p为叶子结点,则直接将其删除。/*/ if( NULL == p->lchild && NULL == p->rchild ) { if( p == q->lchild ) q->lchild = NULL; if( p == q->rchild ) q->rchild = NULL; free(p); p = NULL; } /*/情况2:结点p的双亲结点为q,且p只有左子树或只有右子树, 则可将p的左子树或右子树直接改为其双亲结点q的左子树或右子树。/*/ else if( (NULL == p->rchild && NULL != p->lchild) ) { /*/p只有左子树/*/ if( p == q->lchild ) q->lchild = p->lchild ; else if( p == q->rchild ) q->rchild = p->lchild ; free(p); p = NULL; } else if( NULL == p->lchild && NULL != p->rchild ) { /*/p只有右子树/*/ if( p == q->lchild ) q->lchild = p->rchild ; if( p == q->rchild ) q->rchild = p->rchild ; free(p); p = NULL; } /*/情况3:结点p的双亲结点为q,且p既有左子树又有右子树。 本代码使用直接前驱(也可以直接后继)这里找的是左子树中最大的元素/*/ else if( NULL != p->lchild && NULL != p->rchild ) { BiTree s, sParent; sParent = p; s = sParent->lchild ; while( NULL != s->rchild ) {/*/找到p的直接前驱/*/ sParent = s; s = s->rchild ; /*/左子树最大的总是在左子树中最右下角/*/ } temp = s->data ; /*/此时 s指向的是最大的右下叶子结点 为一般情况1 直接删除/*/ DelBSTNode( t, temp ); p->data = temp; /*/最后将原来要删除的p的数据改为temp/*/ } } } /*/ 待递归版本的删除 传引用的妙处 中序遍历打印BST/*/ void PrintBST( BiTree t ) { if( t ) { PrintBST( t->lchild ); printf("%d ", t->data); PrintBST( t->rchild ); } } void use() { int n; int *a; Elemtype key; BiTree t; printf("请输入二叉查找树的结点数:\n"); scanf("%d", &n); a = (int *)malloc(sizeof(int)*n); printf("请输入二叉找树的结点数据:\n"); for( int i=0; i
分享文章:小代码向原文学习BST简单的C语言版本
网页路径:http://cdkjz.cn/article/pjsooe.html