【数据结构】树与二叉树（十七）：二叉树的基础操作：删除指定结点及其左右子树（算法DST）_删除相关子树算法

5.2.1 二叉树

  二叉树是一种常见的树状数据结构，它由结点的有限集合组成。一个二叉树要么是空集，被称为空二叉树，要么由一个根结点和两棵不相交的子树组成，分别称为左子树和右子树。每个结点最多有两个子结点，分别称为左子结点和右子结点。

二叉树性质

引理5.1：二叉树中层数为i的结点至多有$2^i$个，其中$i\ge 0$。

引理5.2：高度为k的二叉树中至多有$2^{k+1}-1$个结点，其中$k\ge 0$。

引理5.3：设T是由n个结点构成的二叉树，其中叶结点个数为$n_0$，度数为2的结点个数为$n_2$，则有$n_0=n_2+1$。

• 详细证明过程见前文：【数据结构】树与二叉树（三）：二叉树的定义、特点、性质及相关证明

满二叉树、完全二叉树定义、特点及相关证明

• 详细证明过程见前文：【数据结构】树与二叉树（四）：满二叉树、完全二叉树及其性质

5.2.2 二叉树顺序存储

  二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，详见：
【数据结构】树与二叉树（五）：二叉树的顺序存储（初始化，插入结点，获取父节点、左右子节点等）

5.2.3 二叉树链接存储

  二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。在链式存储中，每个二叉树结点都包含三个域：数据域（Data）、左指针域（Left）和右指针域（Right），用于存储结点的信息和指向子结点的指针，详见：
【数据结构】树与二叉树（六）：二叉树的链式存储

5.2.4 二叉树的遍历

• 遍历（Traversal）是对二叉树中所有节点按照一定顺序进行访问的过程。
• 通过遍历，可以访问树中的每个节点，并按照特定的顺序对它们进行处理。
• 对二叉树的一次完整遍历，可给出树中结点的一种线性排序。
  • 在二叉树中，常用的遍历方式有三种：先序遍历、中序遍历和后序遍历。
  • 这三种遍历方式都可以递归地进行，它们的区别在于节点的访问顺序。
    • 在实现遍历算法时，需要考虑递归终止条件和递归调用的顺序。
  • 还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。
• 遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。
  

1-3 先序、中序、后序遍历递归实现及相关练习

【数据结构】树与二叉树（七）：二叉树的遍历（先序、中序、后序及其C语言实现）

4. 中序遍历非递归

【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO）

5. 后序遍历非递归

【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO）

6. 先序遍历非递归

【数据结构】树与二叉树（十）：二叉树的先序遍历（非递归算法NPO）

7. 层次遍历

【数据结构】树与二叉树（十一）：二叉树的层次遍历（算法LevelOrder）

5.2.5 二叉树的创建

1. 先序创建

  由二叉树的遍历，很容易想到用遍历方法去创建二叉树，我们考虑从先根遍历思想出发来构造二叉树：

【数据结构】树与二叉树（十二）：二叉树的递归创建（算法CBT）

2. 复制二叉树

  考虑用后根遍历思想递归复制二叉树的算法CopyTree：

【数据结构】树与二叉树（十三）：递归复制二叉树（算法CopyTree）

5.2.6 二叉树的基础操作

1. 查找给定结点的父亲

• 递归思想
  • 给定结点是指给定的是一个指向某个结点的指针(比如p)。
  • 返回值也应该是指针，指向结点p之父亲的指针（找不到时为空）。

【数据结构】树与二叉树（十四）：二叉树的基础操作：查找给定结点的父亲（算法Father ）

2. 查找结点

  考虑利用先根遍历在二叉树中搜索符合数据条件(item)的结点p，即满足data§=item的结点。

3. 插入结点

4. 删除结点及其左右子树

a. 逻辑删除与物理删除

逻辑删除（Logical Deletion）

  逻辑删除通常是指在数据结构中标记某个节点为被删除的状态，而不是真正地从内存中删除它。在二叉树中，逻辑删除可以通过断开节点与其父节点之间的连接来实现。以下是逻辑删除的算法：

// 逻辑删除结点p及其左右子树
void logicalDelete(struct Node* parent, struct Node* p) {
    if (parent == NULL || p == NULL) {
        return;
    }

    if (parent->left == p) {
        // 如果p是父节点的左子节点，将左子节点指针设为NULL
        parent->left = NULL;
    } else if (parent->right == p) {
        // 如果p是父节点的右子节点，将右子节点指针设为NULL
        parent->right = NULL;
    }
    // 注意：这里没有释放p的内存，只是断开了连接，实现了逻辑删除。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

物理删除（Physical Deletion）

  物理删除是指真正地从内存中释放某个节点及其子树的内存。在这种情况下，通常会使用递归来遍历整个子树并释放每个节点。以下是物理删除的算法：

// 物理删除结点p及其左右子树
void physicalDelete(struct Node* p) {
    if (p == NULL) {
        return;
    }

    // 递归删除左子树
    physicalDelete(p->left);

    // 递归删除右子树
    physicalDelete(p->right);

    // 释放当前节点的内存
    free(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

c. 算法DST

d. 代码实现

释放二叉树

void releaseTree(struct Node* p) {
    // 如果p为空，则返回
    if (p == NULL) {
        return;
    }

    // 递归释放左子树
    releaseTree(p->left);

    // 递归释放右子树
    releaseTree(p->right);

    // 释放当前节点
    free(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法DST

void DST(struct Node* root, struct Node* t) {
    if (t == NULL) {
        return;
    }
    
    if (t == root) {
        // 调用releaseTree(p)删除t，将root置为NULL，然后返回
        releaseTree(t);
        root = NULL;
        return;
    }
    
    struct Node* p = t;
    struct Node* q = findFather(root, p);

    if (q->left == p) {
        q->left = NULL;
    }

   
    if (q->right == p) {
        q->right = NULL;
    }

    releaseTree(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• （特殊情况）如果t为空，则返回
• （特殊情况）如果t是树的根节点，调用releaseTree(p)删除t，将root置为NULL，然后返回
• （一般情况）复制p = t，找到t的父节点q
  • 如果p是q的左子节点，将q的左子节点p(t)置为NULL
  • 如果p是q的右子节点，将q的右子节点p(t)置为NULL
  • 调用releaseTree(p)删除t及其子树

e. 算法测试

int main() {
    // 创建一棵二叉树
    char tostop = '#';
    char input_data[] = {'a', 'b', 'd', '#', '#', 'e', 'f', '#', '#', 'g', '#', '#', 'c', '#', '#'};
    int index = 0;

    struct Node* root = CBT(input_data, &index, tostop);
    printf("Inorder Traversal before Deletion: ");
    inorderTraversal(root);
    printf("\n");

    // struct Node* targetNode = root->left->right;
    struct Node* targetNode = root->left;
    // struct Node* targetNode = root;

    DST(root,targetNode);
    printf("Inorder Traversal after Deletion: ");
    inorderTraversal(root);
    printf("\n");

    // 释放整棵树
    releaseTree(root);
    root = NULL;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 采用前文算法CBT，先序递归创建一棵二叉树
• 删除指定结点targetNode
• 对比删除前后的结果
• 释放整棵树
  • 注意，需要将释放的指针置为 NULL，以防止悬空指针

5. 代码整合

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点的定义
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 创建新结点
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* CBT(char data[], int* index, char tostop) {
    char ch = data[(*index)++];
    if (ch == tostop) {
        return NULL;
    } else {
        struct Node* t = createNode(ch);
        t->left = CBT(data, index, tostop);
        t->right = CBT(data, index, tostop);
        return t;
    }
}

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%c ", root->data);
        inorderTraversal(root->right);
    }
}

// 查找给定结点的父亲节点（递归实现）
struct Node* findFather(struct Node* root, struct Node* p) {
    // 如果树为空或者给定结点为空，则返回NULL
    if (root == NULL || p == NULL) {
        return NULL;
    }

    // 如果给定结点是根节点，则根据定义返回NULL
    if (root == p) {
        return NULL;
    }

    // 如果给定结点是根节点的左孩子或右孩子，则根节点就是其父亲
    if (root->left == p || root->right == p) {
        return root;
    }

    // 在左子树中递归查找
    struct Node* leftResult = findFather(root->left, p);
    if (leftResult != NULL) {
        return leftResult;
    }

    // 在右子树中递归查找
    return findFather(root->right, p);
}


// 释放以p指向结点为根的树
void releaseTree(struct Node* p) {
    // 如果p为空，则返回
    if (p == NULL) {
        return;
    }

    // 递归释放左子树
    releaseTree(p->left);

    // 递归释放右子树
    releaseTree(p->right);

    // 释放当前节点
    free(p);
}

// root指向一棵二叉树T之根，从T中删除给定结点t及其左右子树
void DST(struct Node* root, struct Node* t) {
    // 如果t为空，则返回
    if (t == NULL) {
        return;
    }

    // 如果t是树的根节点
    if (t == root) {
        // 调用releaseTree(p)删除t，将root置为NULL，然后返回
        releaseTree(t);
        root = NULL;
        return;
    }

    struct Node* p = t;
    struct Node* q = findFather(root, p);

    // 如果p是q的左子节点，将q的左子节点p(t)置为NULL
    if (q->left == p) {
        q->left = NULL;
    }

    // 如果p是q的右子节点，将q的右子节点p(t)置为NULL
    if (q->right == p) {
        q->right = NULL;
    }

    // 调用releaseTree(p)删除t及其子树
    releaseTree(p);
}

int main() {
    // 创建一棵二叉树
    char tostop = '#';
    char input_data[] = {'a', 'b', 'd', '#', '#', 'e', 'f', '#', '#', 'g', '#', '#', 'c', '#', '#'};
    int index = 0;

    struct Node* root = CBT(input_data, &index, tostop);
    printf("Inorder Traversal before Deletion: ");
    inorderTraversal(root);
    printf("\n");

    // 需要找到父亲的结点，比如 'e'
    // struct Node* targetNode = root->left->right;
    struct Node* targetNode = root->left;
    // struct Node* targetNode = root;

    DST(root,targetNode);
    printf("Inorder Traversal after Deletion: ");
    inorderTraversal(root);
    printf("\n");

    // 释放整棵树
    releaseTree(root);
    root = NULL;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147