定义:
它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值查找操作
查找最大结点的位置
1 | node* findmax(node* root) |
查找最小结点的位置
1 | node* findmin(node* root) |
插入操作
1 | void create(node*& root, int x) |
删除操作
我们把比要删除结点的权值小的最大值叫做 前驱(pre) 比结点权值大的最小值叫做 后继(next) 要删除一个结点,我们可以用这个结点的前驱来覆盖他,因为这个结点比要删除的结点的左子树的任意一个结点权值都要大,同理后继比要删除结点的右子树的所有权值都要小。思路如下
1.如果说当前结点为空,说明不存在权值为给定权值为x的结点(二叉查找树由于他的左右根结点的大小关系,使得我们可以直接找到一条路,逐步通往要删除的值,不用遍历所有的路,所以,只要为空,就说明我们没有找到这个点) 2.如果找到了一个结点等于权值,那么就进入删除操作 2.1如果当前结点不存在左右孩子,那么说明这个结点是叶子,可以直接删除 2.2如果当前结点存在左孩子,就在左子树中找前驱元素,并用前驱元素替换他,随后删除前驱元素原来的位置 2.2如果不存在左孩子,有右孩子,就找后驱元素........ 3.如果当前结点的权值大于给定的权值,那么就在左子树中去寻找 4.如果当前结点的权值小于给定的权值,那么就在右子树中去寻找1 | void deletenode(node* &root,int x)//注意这个& |
本文作者: jiangyuhao
本文链接: http://example.com/2022/06/09/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!