完整详尽的二叉排序树性质及源码和注释 C语言 可直接运行/***二叉查找树的性质：* 1）若其左子树不空，左子树上所有节点的值均小于它的根节点的值* 2）若其右子树不空，右子树上所有节点的值均大于它的根节点的值* 3）它的左右子树也分别为二叉排序树 **/#include <stdio.h>#include <stdlib.h>#define OK true#define OVERFLOW false#define FALSE false#define ERROR false#define TRUE true#define EQ(x,y) (x==y)#define LT(x,y) (x<y)typedef bool Status;typedef int KeyType;typedef struct DataType{KeyType key;void * dt;}DataType; typedef struct BinarySearchTreeNode{DataType data;BinarySearchTreeNode * left, * right;}BinarySearchTreeNode,*BinarySearchTree;//返回的其实是指向结点的指针 BinarySearchTree SearchBST1(BinarySearchTree T, KeyType key) {if(!T||EQ(key,T->data.key))return T;else if(LT(key,T->data.key)) return (SearchBST1(T->left,key));elsereturn (SearchBST1(T->right,key));}/*** 1) 新插入的节点一定是一个新添加的叶子结点，* 2) 并且是查找不成功时查找路径上访问的最后一个节点的左孩子或者右孩子节点 **/ //结点f是通过参数传过来的，它是T的父结点，p是最终查找到的那个节点，或者没有查找到，但是最后指向的叶子结点 //递归的终止条件是什么一定要想清楚 Status SearchBST2(BinarySearchTree T, KeyType key, BinarySearchTree f, BinarySearchTree &p){if(!T){p = f; //如果树为空，则p和f均指向相同的，原来f=NULL return false;}else if EQ(key,T->data.key){p = T;return TRUE;}else if LT(key,T->data.key)return SearchBST2(T->left,key,T,p);elsereturn SearchBST2(T->right,key,T,p); } Status InsertBST(BinarySearchTree &T, DataType e){BinarySearchTreeNode *p = NULL;BinarySearchTreeNode *s = NULL;if(!SearchBST2(T,e.key,NULL,p)){s = (BinarySearchTree)malloc(sizeof(BinarySearchTreeNode));s->data = e;s->left = NULL;s->right = NULL;if(!p) T = s;else if LT(e.key,p->data.key)p->left = s;elsep->right = s;return TRUE;}elsereturn FALSE;} /*** 1）中序遍历二叉查找树 可得到一个关键字的有序序列* 2）构造树的过程即为对无序序列进行排序的过程，插入新的节点不必移动其他节点**///删除二叉排序树中的节点的方法有两种//一种是进行替代//另一种是先替代后删除 Status Delete(BinarySearchTree &p){BinarySearchTree q, s;if(!p->right) //只有左子树的情况 {q = p;p = p->left;free(q);}else if(!p->left) //只有右子树的情况 {q = p;p = p->right;free(q);}else //既有左子树又有右子树的情况 {q = p; //先将此节点保存起来 s = p->left; //找到此节点的左子树 while(s->right) //找到此节点左子树的最右节点，也即此节点的前驱 {q = s;s = s->right; //q为s的父亲节点 }p->data = s->data; //用s来替换将要被删除的节点p //下面几行的作用是删除掉s节点，重置s的父结点q的左右指针 if(q!=p)q->right = s->left; //重接q的右子树 else q->left = s->left; //重接q的左子树 delete s;}return TRUE;}Status DeleteBST(BinarySearchTree &T, KeyType key){if(!T)return FALSE;else{if(EQ(key,T->data.key)){return Delete(T);}else if(LT(key,T->data.key))return DeleteBST(T->left,key);elsereturn DeleteBST(T->right,key);}} int main(){int i=0;int key;BinarySearchTree T=NULL;printf("please input 10 nodes and construct the tree~~\n");while(i<10){scanf("%d",&key);DataType data = {key,NULL};InsertBST(T,data);i++;} KeyType querykey = 3; bool tag = SearchBST1(T,querykey);if(tag) printf("Find the exact data~~\n");elseprintf("Do not find the data~~\n");return 0; }
