数据结构6.3:二叉树的查找和删除
二叉树的查找
前中后序查找
1,前序查找思路
先判断当前节点的数据是否为自己需要查找的
如果相等返回当前节点
如果不等,先判断左子节点是否为空,不为空就对左子节点递归前序查找
再判断右子节点是否为空,对右子节点递归前序查找
public void presearch(int num) {
if (this.num == num) {
System.out.println("找到了" + this.name);
}else{
System.out.println("没找到" + this.name);
}
if (this.left != null) {
this.left.presearch(num);
}
if (this.right != null) {
this.right.presearch(num);
}
}
2,中序查找思路
先判断左子节点是否为空,不为空就对左子节点递归中序查找
如果返回空
再判断当前节点的数据是否为自己需要查找的
如果相等返回当前节点
再判断右子节点是否为空,对右子节点递归中序查找
public void midsearch(int num) {
if (this.left != null) {
this.left.presearch(num);
}
if (this.num == num) {
System.out.println("找到了" + this.name);
}else{
System.out.println("没找到" + this.name);
}
if (this.right != null) {
this.right.presearch(num);
}
}
3,后序查找思路
判断当前节点的左子节点是否为空,不为空就对左子节点递归后序查找
再判断右子节点是否为空,对右子节点递归后序查找
如果都返回空
对当前节点数据进行判断
public void backsearch(int num) {
if (this.left != null) {
this.left.presearch(num);
}
if (this.right != null) {
this.right.presearch(num);
}
if (this.num == num) {
System.out.println("找到了" + this.name);
}else{
System.out.println("没找到" + this.name);
}
}
如果需要返回整个节点,则写法稍微复杂一点,这里以前序遍历为例
public BinaryTreeNode presearch_node(int num){
BinaryTreeNode node = null;
if(this.num == num){
return this;//找到就将节点向上传递
}
if(this.left != null){
node = left.presearch_node(num);
}
if(node != null){//找到结果
return node;
}
if(this.right != null){
node = right.presearch_node(num);
}
if(node != null){
return node;
}
return null;
}
如果最终没有找到则返回null
二叉树的删除
如果删除的是叶子节点,就直接删除节点
如果删除的是非叶子节点,就删除子树
思路分析
因为二叉树的单向特性,所以应该对父节点判断其子节点是否需要删除,而非判断本身是否需要被删除.
如果当前节点的左子树不为空且左子结点需要被删除
直接将指向左子结点的指针置空即可
并且退出递归
如果没有删除,
向左子树递归删除,
右子节点同理,将指向右子节点指针置空并返回即可
如果没有删除,
向右子树递归删除
代码实现
public void deleteNode(int num) {
if (this.left == null && this.right == null) {
return;
}
if (this.left != null) {
if (this.left.getNum() == num) {
System.out.printf("删除了%s的左子节点\n", this.getName());
this.left = null;
return;
} else {
this.left.deleteNode(num);
}
}
if (this.right != null) {
if (this.right.getNum() == num) {
System.out.printf("删除了%s的右子节点\n", this.getName());
this.right = null;
return;
} else {
this.right.deleteNode(num);
}
}
}
如果传入的是一个空树,可以在树中对root节点进行判断,如果为空直接返回即可
原文地址:https://blog.csdn.net/qq_55630615/article/details/137717752
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!