期末复习(用c++实现二叉树的简单操作)

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184

//
// Created by 13265 on 2023/5/25.
//

#include <queue>
# include "iostream"
# include "vector"
using namespace std;
//todo 完成数据结构中的二叉树章节的相关练习


struct Node{
    int val;
    Node *left, *right;
    Node(int x) : val(x) ,left(nullptr), right(nullptr){};
    Node(){};
};

/**
 * 创建二叉树的节点
 * @param root 根节点
 * @return 返回创建的节点
 */
Node* createNode(Node* root, int data) {
    if (root == nullptr) {
        return new Node(data);
    } else if (data <= root->val) {
        root->left = createNode(root->left, data);
    } else {
        root->right = createNode(root->right, data);
    }
    return root;
}


/**
 * 注意：  必须有序的二叉树
 * 删除某个二叉树的节点
 *  分为三种情况，删除的节点为叶子节点，有一个节点的节点 ，有一个子树的节点
 *
 *
 * @param root 树的根节点
 * @param index 要删除的节点val
 */
Node* deleteNode(Node *& root,int index){
    if(root == nullptr){
        return root;
    }
    //todo 先遍历找到要删除的节点
    else if(root->val > index){
        root->left = deleteNode(root->left, index);
    }else if (root->val < index){
        root->right = deleteNode(root->right, index);
    }
    //todo 找到了， 开始分情况删除
    else{
        //case1 : 要删除的节点是叶子节点
        if (root->left == nullptr && root->right == nullptr){
            delete root;
            root = nullptr;
        }
        //case2 : 要删除的节点上有一个子节点
        else if (root->left == nullptr || root->right == nullptr){
            Node* temp = root;
            //左子节点不为空
            if(root->left != nullptr){
                root = root->left;
            }
            //右子节点不为空
            else{
                root = root->right;
            }
            delete temp;
        }
        //case3 : 要删除的节点上有两个子节点
        else{/** 为了保持二叉搜索树的性质，我们选择该结点的右子树中的最小值结点来作为替代结点（也可以选择左子树中的最大值结点）。*/
            Node* temp = root->right;
            /*从该结点的右子树开始，找到右子树中的最小值结点。在这个过程中，我们不断遍历右子树的左子结点，直到找到没有左子结点的结点，即为右子树中的最小值结点。*/
            while(temp->left != nullptr){
                temp = temp->left;
            }
            /*然后，我们将该最小值赋值给待删除的结点，并递归地删除该最小值结点（因为该最小值结点已经成为了待删除结点的替代结点，所以要将其从右子树中删除）。*/
            root->val = temp->val;
            root->right = deleteNode(root->right , temp->val);
        }
    }
    return root;
}
/**
 * 更新节点
 * @param root 树的根节点
 * @param oldVal 原来的节点val
 * @param newVal  新的节点val
 */
void updateNode(Node *& root, int oldVal , int newVal){
    if (root == nullptr){
        return;
    }
    Node* temp = root;
    //因为是有序二叉树，所以需要先删除， 然后在进行插入
    deleteNode(root,oldVal);
    createNode(root,newVal);

}

/**
 * 二叉树的层序遍历
 * @param root 二叉树根节点的指针
 */
void listNode(Node *root){
    //可以有三种遍历方式

    queue<Node*> que ;
    que.push(root);
    while (!que.empty()){
        //先出队列， 然后将值输出 ，然后将该节点的子节点全部入队列
        Node * temp = que.front();
        que.pop();
        cout<<temp->val<<" ";
        if (temp->left != nullptr){
            que.push(temp->left);
        }
        if (temp->right != nullptr){
            que.push(temp->right);
        }
    }
}
void preOrder(Node* root){
    if (root== nullptr){
        return;
    }
    cout<<root->val<<" -> ";
    if (root->left != nullptr){
        preOrder(root->left);
    }
    if(root->right != nullptr){
        preOrder(root->right);
    }
}
void midOrder(Node* root){
    if (root== nullptr){
        return;
    }
    midOrder(root->left);
    cout<<root->val<<" -> ";
    midOrder(root->right);

}
void postOrder(Node* root){
    if (root== nullptr){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" -> ";
}



int main(){
    cout<<"test"<<endl;
    //添加节点
    Node* root = nullptr;
    root = createNode(root, 5);
    root = createNode(root, 3);
    root = createNode(root, 7);
    root = createNode(root, 1);
    root = createNode(root, 4);
    root = createNode(root, 6);
    root = createNode(root, 8);
    deleteNode(root,4);
    cout<<"\n前序遍历: "<<endl;
    preOrder(root);
    cout<<"\n中序遍历: "<<endl;
    midOrder(root);
    updateNode(root,3,10);
    cout<<"\n后序遍历: "<<endl;
    postOrder(root);
    cout<<endl;
    cout<<"层序遍历 "<<endl;
    listNode(root);
    return 0;
}