二叉排序树的查找、插入、删除

目录

二叉排序树的定义

二叉排序树的查找

二叉排序树的插入

---

二叉排序树的定义

二叉排序树的定义
二叉排序树（Binary Sort Tree， BST），也称二叉查找树。
二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树：
1） 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字值；
2） 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字值；
3） 左、右子树本身也分别是一棵二叉排序树。

由定义可知，二叉排序树是一个递归的数据结构，可以方便的使用递归算法对二叉排序树进行各种运算。
根据二叉树的定义，可得左子树结点值 ＜ 根结点值 ＜ 右子树结点值。
所以，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。
二叉排序结点结构：

typedef struct BiTNode
{int data;struct BiTNode *left, *right;
}BiTNode,*Bitree;

二叉排序树的查找

二叉排序树的查找是从根结点开始的，沿某个分支逐层向下进行比较的过程。
 其查找过程描述如下：若二叉排序树非空，则将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找；否则在根结点的右子树中查找。

递归查找：

Bitree SearchBST(Bitree root, int key){if(root->data == key){return root;}else if(key< root->data){return SearchBST(root->left, key);}else{return SearchBST(root->right, key);}
}

非递归查找

//查找的非递归算法
Bitree SearchBST(Bitree root, int key){Bitree p = root;while(p!=NULL && p->data!=key){if(key< p->data)p = p->left;elsep = p->right;}return p;
}

二叉排序树的插入

//插入的递归算法
Bitree Insert(Bitree root, int x) {if (root == NULL) {root = (Bitree)malloc(sizeof(BiTNode));root->data;root->left = NULL;root->right = NULL;return root;}if (x < root->data) {root->left = Insert(root->left, x);}if (x > root->data) {root->right = Insert(root->right, x);}return root;
}
//插入的非递归算法
void Inser_Node(Bitree &T, int key)
{Bitree parent = NULL;Bitree p = T;Bitree s = (Bitree)malloc(sizeof(BiTNode));s->data = key;s->left = NULL;s->right = NULL;if (T== NULL){T = s;return;}while (p != NULL){parent = p;if (p->data > key)//在左孩子继续查找{p = p->left;}if (p->data < key){p = p->right;}}if (parent->data > key){parent->left = s;}else {parent->right = s;}}

根据书上代码，将查找和插入整合：

/****************书上代码***************************/
int SearchBST(Bitree T,int key, Bitree f, Bitree& p)
{if (!T){p = f;return 0;}else if(T->data==key){p = T;printf("有重复");return 1;}else if (T->data > key){return SearchBST(T->left, key, T, p);}else{return SearchBST(T->right, key, T, p);}
}
void InserBST(Bitree& T, int key)
{Bitree p;if (SearchBST(T, key, NULL, p)==0)//查找失败，进行插入{Bitree s =(Bitree) malloc(sizeof(BiTNode));s->data = key;s->left = NULL;s->right = NULL;if (!p){T = s;}else if (key < p->data){p->left = s;//被插入点作为*s左孩子}else {p->right = s;}}
}