資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式中二叉樹的刪除操作
在本教程中，我們將學習如何在二叉樹中刪除節點。
二叉樹中的節點不像二叉搜尋樹那樣遵循任何順序。那麼，如何在刪除二叉樹中的節點後重新排列節點呢？
我們將用樹中最深的節點替換要刪除的節點。然後我們將從節點中刪除最深的節點。
讓我們看看解決問題的步驟。
用二叉節點結構初始化樹。
編寫一個函式（前序、中序和後序）來列印樹的節點。
編寫一個函式來刪除節點。
初始化一個佇列來遍歷樹。
迭代直到佇列為空。
找到具有給定鍵的節點並將其儲存在一個變數中。
佇列中的最後一個節點是最深的節點。
使用另一個函式刪除最深的節點。
使用佇列遍歷樹。
當我們找到要刪除的節點時，刪除它並返回它。
列印樹以檢視節點是否已刪除。
示例
讓我們看看程式碼。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* node) {
if (node == NULL) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp == deleting_node) {
temp = NULL;
delete (deleting_node);
return;
}
if (temp->right) {
if (temp->right == deleting_node) {
temp->right = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->right);
}
}
if (temp->left) {
if (temp->left == deleting_node) {
temp->left = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->left);
}
}
}
}
Node* deleteNode(struct Node* root, int key) {
if (root == NULL){
return NULL;
}
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
return NULL;
}
else {
return root;
}
}
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
struct Node* key_node = NULL;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp->data == key) {
key_node = temp;
}
if (temp->left) {
nodes.push(temp->left);
}
if (temp->right) {
nodes.push(temp->right);
}
}
if (key_node != NULL) {
int deepest_node_data = temp->data;
deleteDeepestNode(root, temp);
key_node->data = deepest_node_data;
}
return root;
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << "Tree before deleting key: ";
inorder(root);
int key = 5;
root = deleteNode(root, key);
cout << "\nTree after deleting key: ";
inorder(root);
cout << endl;
return 0;
}輸出
如果您執行上面的程式碼，您將得到以下結果。
Tree before deleting key: 3 2 4 1 8 6 9 5 7 Tree after deleting key: 3 2 4 1 8 6 9 7
結論
如果您在本教程中有任何疑問，請在評論區提出。
更新於：2021年1月27日
5000+ 次瀏覽
廣告