数据结构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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

如果需要返回整个节点,则写法稍微复杂一点,这里以前序遍历为例

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果最终没有找到则返回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);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果传入的是一个空树,可以在树中对root节点进行判断,如果为空直接返回即可