allbetgaming开户:二叉搜索树

admin/2020-07-14/ 分类:科技/阅读:

二叉搜索树

注重:本文的算法和代码思绪大部分来自《算法导论》

什么是二叉搜索树

二叉搜索树首先是一棵二叉树,此外,它还能用来搜索。由于它知足这样的性子:每个结点的左子树的结点值都比自身小,而它的右子树的结点值都比自身大。

它长得像下面这样:(依据建立时结点插入顺序差别,可能是满二叉,也可能不是)

二叉搜索树可以异常利便的用来举行查找指定元素,查找最大值和最小值等。

界说数据结构

我们可以用链表或者数组的方式来实现一棵树。这里我们接纳链表的方式。

首先界说节点结构,可以看到,每个结点有一个值,而且有两个孩子,而且有一个父亲。

此外,我们还要分外界说一棵树的结构,它很简朴,只有一个指向树根的指针。

//树结点结构 struct Node { int key; Node* left; Node* right; Node* parent; }; //树 struct Tree { Node* root; }; 

二叉树的遍历

由于二叉搜索树的特殊性子,我们对其举行中序遍历就可以获得所有元素的一个有序序列。

遍历既可以用递归也可以用迭代的方式去实现,这里给出递归的版本:

//中序遍历 void inorder_tree_walk(Node* x) { if (x != NULL) { inorder_tree_walk(x->left); cout << x->key << " "; inorder_tree_walk(x->right); } } //前序遍历 void preorder_tree_walk(Node* x) { if (x != NULL) { cout << x->key << " "; preorder_tree_walk(x->left); preorder_tree_walk(x->right); } } //后续遍历 void postorder_tree_walk(Node* x) { if (x != NULL) { postorder_tree_walk(x->left); postorder_tree_walk(x->right); cout << x->key << " "; } } 

遍历二叉树的时间复杂度是:O(n)。

如对上图左边的那棵树举行中序遍历的话,获得的序列就是:2 3 4 5 7 9

查询指定结点值

若是给出一个关键字,想要查询其是否存在与二叉树中,若是存在则返回指向它的结点的指针。这个历程可以形貌如下:首先把关键字和根结点的值做对照,若是相等则返回;否则,若是比根节点值小,那就递归的在左子树中查找,否则就在右子树中查找。

这个历程既可以用递回去实现,也可以用迭代去实现,这里给出两个版本:

//递归版 Node* tree_search(Node* x, int k) { //找到或者为空 if (x == NULL || k == x->key) { return x; } if (k < x->key) { return tree_search(x->left, k); } else { return tree_search(x->right, k); } } //迭代版 Node* iterative_tree_search(Node* x, int k) { while (x != NULL && k != x->key) { if (k < x->key) { x = x->left; } else { x = x->right; } } return x; } 

最大元素和最小元素

凭据二叉搜索树的性子,左子树的结点值都比其父节点的小,而右子树的相反。以是,只要从树根最先,沿着左孩子举行查找,直到最后一个左孩子,那它一定就是最小值。最大值也是类似。

像这里:

这里给出迭代方式的实现:

//找最小结点 Node* tree_minimum(Node* x) { while (x->left != NULL) { x = x->left; } return x; } //找最大结点 Node* tree_maximum(Node* x) { while (x->right != NULL) { x = x->right; } return x; } 

前驱和后继

一个结点的前驱和后继是什么呢?它是根据中序遍历时,排在该结点前和后的第一个结点。

如:上图的中序遍历是:2 3 4 5 7 9 , 那5的前驱就是4,而其后继就是7。

也就是,前驱是恰好比它小(或者即是)的元素,后继是恰好比它大(或者即是)的元素。

那要怎么找呢?

首先看这幅图:

我们先讨论,有左子树的结点的前驱,和有右子树的结点的后继。

首先,有左子树的结点的前驱。我们知道,一个节点的左子树的值都比他自身小,以是它的前驱一定是在左子树中,而且是左子树中最大的那一个。比如说,结点6,它的前驱就是左子树中最大的谁人,也就是4。

然后,是有右子树的结点的后继。很显然,它应该是它的右子树中最小的那。比如说,结点

6,它的后继就是右子树中最小的谁人,也就是7。

那么,为什么有左子树的前驱一定在左子树中,而不能能在它的父系结点或其他地方呢?

我们可以这样思量,看到结点13,它有一个左子树,左子树的结点值都比它小。它有一个父亲7,且它是它父亲的右孩子,以是父亲也比它小。那有没有可能,父亲的某一个取值会使得它是13的前驱呢?谜底是不能能的。由于前驱是比它小之中的最大的谁人,而若是它有左子树,那左子树中的元素由于在它13的父亲结点的右子树中,以是一定比父亲结点7要大,然则却比13小。

接下来是,没有左子树的结点的前驱,和没有右子树的结点的后继。

显然,没有左子树的结点的前驱不能能在左子树里找,只能在其他地方找。注重到,前驱和后继其实是对称的关系,若是b的前驱是a,那么a的后继一定就是b。以是我们要找到a的后继,相当于要找到b的前驱。比如说我们要找到结点7的前驱,那若是能找到某个结点,它的后继是7,那就完事了。由于7没有左子树,以是7的前驱一定在父亲结点上面。而由于6的后继就是7,以是6就是7的前驱(可以这样验证,由于6有右子树,且7是右子树中最小的谁人,以是7是6的后继)。以是这个前驱节点a知足这样一个性子:它一定在结点b的父系结点上,而且,它是第一个使得b在它的右子树中的结点。

响应的,没有右子树的结点的后继也是类似求法。

这里给出实现方式:

//前驱 Node* tree_predecessor(Node* x) { //若是左子树非空,则前驱是左子树中最大的结点 if (x->left != NULL) { return tree_maximum(x->left); } //否则,找到父系结点中第一个使得它是其右子孙的结点 Node* y = x->parent; while (y != NULL && y->left == x) { x = y; y = x->parent; } return y; } //后继 Node* tree_successor(Node* x) { //若是右子树非空,则后继是右子树中的最左结点 if (x->right != NULL) { return tree_minimum(x->right); } //否则,找到父系结点中第一个使得它是其左子孙的结点 Node* y = x->parent; while (y != NULL && y->right == x) { x = y; y = x->parent; } return y; } 

插入

首先,要明确一点,新结点一定是以叶节点的形式插入的。而我们要找的就是谁人能收养它的父结点。

比如说,我们要在这棵树里插入结点8:

首先,8和5对照,比5大,在右子树中查找。然后和9对照,比9小;最后和7对照,比7大,但由于7已经没有右子树了,以是就把8挂在7的右子树上。

实现如下:

void tree_insert(Tree* T, Node* z) { Node* y = NULL; //用来记着父节点 Node* x = T->root; //从根最先查找 while (x != NULL) { y = x; //记着要挂留的父节点 if (z->key < x->key) { //在左子树中找 x = x->left; } else { x = x->right; //在右子树中找 } } z->parent = y; //挂上去 if (y == NULL) { //若是树是空的 T->root = z; } //父亲收养它 else if (z->key < y->key) { y->left = z; } else { y->right = z; } } 

删除

删除是一件对照贫苦的事。我们分3种大的情形来讨论。

  • 若是z没有孩子结点,那么只是简朴的把它删除掉,而且修改它的父节点指向空。

  • 若是z只有一个孩子,那么将这个孩子提升到树中z的位置上,并修改z的父节点的孩子指针。

  • 若是z有两个孩子,那么找到z的后继y(在右子树中),并让y占有z的位置。

    这里有细分为两种情形:

    • 若是y是z的右孩子,则直接把以y为根的子树放到z上,在让z的左子树成为y的左子树。

    • 若是y不是z的右孩子,则先用y的右孩子来替换y,在用y替换z。

    为了完成以上事情,分外界说一个函数transplant,它专门用来移植结点。它用一棵以v为根的子树来替换一棵以u为根的子树,结点u的双亲变为结点v的双亲,而且最后v成为u的双亲的响应孩子。

    代码如下:

    void transplant(Tree* T, Node* u, Node* v) { if (u->parent == NULL) { //若是被替换的是树根,则要让其成为树根 T->root = v; } else if (u == u->parent->left) { //若是被替换的谁人结点是其父节点的左孩子 u->parent->left = v; } else { //否则是右孩子 u->parent->right = v; } if (v != NULL) { //指向父节点 v->parent = u->parent; } } void tree_delete(Tree* T, Node* z) { //对应第一种和第二种情形 if (z->left == NULL) { transplant(T, z, z->right); } else if (z->right == NULL) { transplant(T, z, z->left); } //对应第三种情形 else { Node* y = tree_minimum(z->right); if (y->parent != z) { //若是y不是z的直接右孩子 transplant(T, y, y->right); y->right = z->right; y->right->parent = y; } transplant(T, z, y); y->left = z->left; y->left->parent = y; } } 

参考资料: 《算法导论》Thomas H. Cormen Charles E.Leiserson && Ronald L.Rivest Clifford Stein 著

,

Allbet开户

欢迎进入Allbet开户(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

TAG:
阅读:
广告 330*360
广告 330*360
Sunbet_进入申博sunbet官网
微信二维码扫一扫
关注微信公众号
新闻自媒体 Copyright © 2002-2019 Sunbet 版权所有
二维码
意见反馈 二维码