二叉排序树就是节点经过排序构建起的二叉树,其有以下性质:
1. 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。
2. 若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。
3. 它的左、右子树也分别为二叉排序树。
画个图方便理解:
第一张图是一个简单的排序二叉树,5<10<15,所以顺序应该是 10 作为根节点,小于10的在左子树,大于10的在右子树。
如果现在又要加入一个节点呢?比如说:6,它应该放在哪里?因为 6 比 10 小,所以 6 应该放在 10 的左子树,又因为 6 比 5 大所以放在 5 的右子树。如图:
那么如果是 16 呢?16 先和 10 进行比较,16>10 进入10的右子树,16 再和 15 比较,16>15,进入 15 的右子树。如图:
现在如果给一个数组:int array[6] = { 6,3,12,5,20,1 },如何构建一个二叉排序树呢?
我们可以回想我们在构建树的时候代码思路:
void CreatTree(TreeNode** T, int data) {if (data == "#") {孩子置空停止递归*T=NULL;}else {*T = (TreeNode*)malloc(sizeof(TreeNode));(*T)->val = data;(*T)->lchild = NULL;(*T)->rchild = NULL;递归左子树,递归右子树Creat_BST(&((*T)->rchild), data);Creat_BST(&((*T)->lchild), data);}}
}
我这里写的不完整,主要看 else部分,创建节点,然后递归创建左右孩子节点,那么二叉排序树的特殊条件就是小的放在左孩子,大的放在右孩子,只不过加了个判断条件,而不是左右孩子都创建。
所以我们可以这样创建排序二叉树:
void Creat_BST(TreeNode** T, int data) {if (*T == NULL) {*T = (TreeNode*)malloc(sizeof(TreeNode));(*T)->val = data;(*T)->lchild = NULL;(*T)->rchild = NULL;}else {if (data> (*T)->val){Creat_BST(&((*T)->rchild), data);}else {Creat_BST(&((*T)->lchild), data);}}
}
我的函数是只创建一个二叉排序树的节点,首先传进的 *T 是空,说明树为空,所以创建节点。第二个数据进入时,因为根不为空进入 else,如果小于根节点数据,则进入左孩子遍历(因为左孩子在在创建根节点时置空,所以这时就会创建左孩子存放第二个数据。),如果大于根节点数据,则进入右孩子遍历。
下面是用循环创建二叉排序树的主函数代码:
int main() {TreeNode* T = NULL;int array[6] = { 6,3,12,5,20,1 };for (int i = 0; i < 6; i++) {Creat_BST(&T, array[i]);}return 0;
}
最后写一个寻找树中是否有目标值的函数,逻辑很相似:
TreeNode* BST_search(TreeNode* T, int val) {if (T) {if (T->val == val) {return T;}else{if (val < T->val) {return BST_search(T->lchild, val);}if (val > T->val) {return BST_search(T->rchild, val);}}}else {return NULL;}
}
如果相等就返回地址,如果小于树节点的值,利用二叉排序树的性质,就一定在左子树,继而进入左子树递归,如果大于树节点的值,就一定在右子树,进入右子树进行递归。如果都没有,最后一定会找到末端节点的左右孩子,末端节点的左右孩子是空,所以进入最后一个 else 返回NULL。
这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎评论。