資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中二叉樹的刪除操作？
刪除操作是透過用最底部最右邊的節點替換要刪除的節點來執行的。
首先，讓我們定義一個結構體來表示樹節點，其中包含資料及其左右子節點。如果這是第一個建立的節點，則它是根節點，否則是子節點。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下來，我們建立 `newNode(int data)` 函式，該函式接收一個整數值並將其賦值給節點的 data 成員。該函式返回指向已建立的 `struct Node` 的指標。此外，新建立節點的左右子節點都設定為 null。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}`deletion(struct Node* root, int data)` 函式用於刪除具有給定 data 值的節點。它接收根節點和要搜尋和刪除的 data 值。如果沒有子節點並且 data 值等於根節點的 data 值，則返回 null，否則返回根節點。
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
}現在，我們建立一個型別為 `struct Node*` 的佇列，並將其命名為 `q`，並將根節點推入 `q`。我們還宣告 `temp` 和 `data_node`，它們是指向 `Node` 的指標，並將 `data_node` 設定為 NULL。
struct Node* temp; struct Node* data_node = NULL;
接下來，我們執行層序遍歷以查詢最深的節點。當佇列 `q` 不為空時，執行 while 迴圈。佇列是一種先進先出 (FIFO) 資料結構，因此，由於我們正在進行層序遍歷，佇列中的最後一個元素將是最右邊的最深節點。`temp` 始終指向佇列的前面，並且隨著我們的進行，元素會從前面彈出。
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
}接下來，如果 `data_node` 不為 NULL，則我們將要刪除的節點資料儲存在 `x` 中，並刪除 `temp`（即最深的節點）。然後，`data_node` 的值被替換為最深節點的值，最深節點被刪除。刪除和替換後，新節點將從函式返回。
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root, temp);
data_node->data = x;
}`deleteDeepest(struct Node* root, struct Node* deepestNode)` 函式檢查傳遞的節點是否確實是深度節點，或者其右子節點或左子節點是否是深度節點，在這種情況下，它會在刪除父節點（即 `deepestNode`）之前將其子節點值設定為 null。
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
}示例
讓我們看看下面的實現，以瞭解二叉樹中的刪除操作：
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
struct Node* temp = new Node;
temp->data = data;
temp->leftChild = temp->rightChild = NULL;
return temp;
};
void inorder(struct Node* temp){
if (!temp)
return;
inorder(temp->leftChild);
cout << temp->data << " ";
inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
}
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* data_node = NULL;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
}
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root,temp);
data_node->data = x;
}
return root;
}
// Driver code
int main(){
struct Node* root = NewNode(12);
root->leftChild = NewNode(13);
root->leftChild->leftChild = NewNode(9);
root->leftChild->rightChild = NewNode(14);
root->rightChild = NewNode(11);
root->rightChild->leftChild = NewNode(17);
root->rightChild->rightChild = NewNode(10);
cout << "Inorder traversal before deletion : ";
inorder(root);
int data = 13;
root = deletion(root, data);
cout <<endl<< "Inorder traversal after deletion : ";
inorder(root);
return 0;
}輸出
以上程式碼將產生以下輸出：
Inorder traversal before deletion : 9 13 14 12 17 11 10 Inorder traversal after deletion : 9 10 14 12 17 11
226 次瀏覽
