主要内容 #
- 二叉排序树
- 二叉排序树的查找
- 二叉排序树的删除
1. 二叉排序树 #
二叉排序树,又称二叉查找树(BST,Binary Search Tree),如图1所示。一棵二叉树或者空二叉树,或者是具有如下性质的二叉树:
- 左子树上所有结点的关键字均小于根结点的关键字。
- 右子树上所有结点的关键字均大于根结点的关键字。
- 左子树和右子树又各是一棵二叉排序树。
对二叉排序树进行中序遍历,可以得到一个递增的有序序列。二叉排序树可用于元素的有序组织、搜索。
2. 二叉排序树的查找 #
左子树结点值 < 根节点值 < 右子树根节点值若树非空,目标值与根结点的值比较:
- 若相等,则查找成功;
- 若小于根结点,则在左子树上查找,否则在右子树上查找。
- 查找成功,返回结点指针;查找失败,返回NULL。
在上节课的基础上,采用递归的方式对二叉树进行查找:
tree findn(tree bt, int n){ if(bt){ //如果节点不为空 if(n < bt->data) findn(bt->lchild, n); //查找左子树 else if(n < bt->data) findn(bt->rchild, n);//查找右子树 else return bt; }else return NULL; }
3. 二叉排序树的插入 #
若原有二叉排序树为空,则直接插入结点;否则,若关键字n小于根结点的值,则插入左子树,若关键字n大于根结点值,则插入右子树。
说明:新插入的结点一定是叶子结点。
void insert(tree &bt, int n){ //插入一个节点到排序二叉树中 if(bt){ if(n < bt -> data) insert(bt->lchild, n); else if(n > bt -> data) insert(bt->rchild, n); }else{ bt = new node; //开一个新空间 bt -> data = n; bt -> lchild = NULL; bt -> rchild = NULL; } }