二进制排序树的删除节点

全部展开

删除二进制排序树中的一个节点，并在三种情况下进行讨论: 如果* p节点是叶节点，则PL（左子树）和PR（右子树）都是空树. 由于删除叶节点不会破坏整个树的结构，因此可以直接删除此子节点. 如果* p节点仅具有左子树PL或右子树PR二叉排序树的删除，则只需使PL或PR直接成为其父节点* f（当* p是左子树时）或右子树（当*时）的左子树即可. p是正确的子树），此修改不会破坏二进制排序树的特征. * p节点的左右子树不为空. 删除* p后，为了保持其他元素之间的相对位置不变，可以根据中间顺序遍历进行调整以保持顺序，有两种方法:

一种方法是使* p的左子树成为* f的左/右（取决于* p是* f的左子树还是右子树），而* s是左子树* p的右下子节点，以及* p的右e5a48de588b6e799bee5baa6e997aee7ad9431333361303030子树是* s的右子树；

第二种方法是使* p的直接前任（或直接后继）替换* p，然后从二进制排序树中删除其直接前任（或直接后继）二叉排序树的删除，即让* f的左子树（如果有的话）成为* p左子树（如果有）的最左侧最低节点，那么让* f成为* p左节点和右节点的父节点.

删除二进制排序树上的节点的算法如下: C代码#defineStatusboolStatusDelete（BiTree *）; // //必须首先声明StatusDeleteBST（BiTree＆T，KeyTypekey）{//如果二进制排序树T中有关键字，则当数据元素等于key时，删除数据元素并返回// TRUE;否则返回FALSEif（！T）返回false; //没有键等于键else的数据元素{if（键== T-> data .key）{//找到键等于键returnDelete（T）的数据元素；} elseif（键 data.key）returnDeleteBST（T-> lchild，key）; elsereturnDeleteBST（T-> rchild，key）;} returntrue;} StatusDelete（BiTree＆p）{//如果（！p-> rchild）{//，则从二进制排序树中删除节点p并重新连接其左或右子树. 仅右子树为空重新连接其左子树q = p; p = p-> lchild; deleteq;} elseif（！P-> lchild）{//左子树为空，只需重新连接其右子树q = p; p = p-> rchild;删除（q）;}否则{//左右子树都不为空q = p; s = p-> lchild;而（s-> rchild）{q = s; s = s-> rchild;} //向左转，然后向右转到末尾p-> data = s-> data; // s指向已删除节点的“前任”，如果（q！= p）// //上述循环至少执行一次q-> rchild = s-> lchild; elseq-> lchild = s-> lchild; //重新连接* q的左子树delete（s）;} returntrue;} Java代码/ ***方法名称: delete（）*方法描述: 删除节点* @ param递归删除它* @ returnString * @ Exception * / privatevoiddeleteNode （BinarySortTreep）{// TODOAuto-generatedmethodstubif（p！= null）{//如果节点具有左子树/ * 1.

如果p具有左子树，请找到其左子树的最右叶节点r，使用该叶节点r替换p，然后将r的左子节点用作r的父节点的右子节点. 2.如果p没有左子树，则将其直接替换为p的右子树. * / if（p.lChild！= null）{BinarySortTreer = p.lChild; BinarySortTreeprev = p.lChild; while（r.rChild！= null）{上一页= r; r = r.rChild;} p.data = r .data; //如果r不是p的左子树，则p的左子树保持不变，并且r的左子树充当r的父节点的右子节点if（prev！= r）{prev.rChild =河lChild;}否则{//如果r是p的左子树，则p的左子树指向r的左子树. p.lChild = r.lChild;}}其他{p = p.rChild;}}} <

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-184777-1.html