网站排名 算法,seo网络优化推广,杭州商城网站建设,煎蛋无聊图 wordpress二叉排序树就是节点经过排序构建起的二叉树#xff0c;其有以下性质#xff1a;
1. 若它的左子树不为空#xff0c;则左子树上所有节点的值均小于它的根节点的值。
2. 若它的右子树不为空#xff0c;则右子树上所有节点的值均大于它的根节点的值。
3. 它的左、右子树也分…二叉排序树就是节点经过排序构建起的二叉树其有以下性质
1. 若它的左子树不为空则左子树上所有节点的值均小于它的根节点的值。
2. 若它的右子树不为空则右子树上所有节点的值均大于它的根节点的值。
3. 它的左、右子树也分别为二叉排序树。
画个图方便理解 第一张图是一个简单的排序二叉树51015所以顺序应该是 10 作为根节点小于10的在左子树大于10的在右子树。 如果现在又要加入一个节点呢比如说6它应该放在哪里因为 6 比 10 小所以 6 应该放在 10 的左子树又因为 6 比 5 大所以放在 5 的右子树。如图 那么如果是 16 呢16 先和 10 进行比较1610 进入10的右子树16 再和 15 比较1615进入 15 的右子树。如图 现在如果给一个数组int array[6] { 6,3,12,5,20,1 }如何构建一个二叉排序树呢
我们可以回想我们在构建树的时候代码思路
void CreatTree(TreeNode** T, int data) {if (data #) {孩子置空停止递归*TNULL;}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。
这就是文章的全部内容了希望对你有所帮助如有错误欢迎评论。
