C++ 二元樹的刪除節點

#include "stdafx.h"

#include <iostream>

#include <stdlib.h>

using namespace std;

struct node

{

    int data;

    struct node *left;    // self-reference linker

    struct node *right;    // self-reference linker

} *root, *tree, *t;

struct node *GetSmallest(struct node *ptr)

{

     while (ptr->left != NULL)

           ptr=ptr->left;

     return ptr;

}

struct node *Delete(struct node *ptr, int value)

{

     //從維基百科知，There are three possible cases to consider:

     //   1. Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

     //   2. Deleting a node with one child: Remove the node and replace it with its child.

     //   3. Deleting a node with two children: Call the node to be deleted N. Do not delete N.

     //  Instead, choose either its in-order successor node or its in-order predecessor node, R.

     //         Replace the value of N with the value of R, then delete R.

     //第一和和第二種情形的刪除很容易，第種情形時的刪除，我是用「中序立即後繼節點(inorder immediate successor)」法，

     //就是將欲刪除節點的右子樹最小者向上提。詳細可參閱網路上搜尋的介紹

    

    

     struct node *temp;

     if (ptr!= NULL)

     {

           ////第一種情形

           if (ptr->right == NULL && ptr->left == NULL)

                ptr= NULL;

           ///////////

           //第二種情形

           else if (ptr->left == NULL)

                ptr = ptr->right;

           else if (ptr->right == NULL)

                ptr = ptr->left;

           //////////

           else if (value > ptr->data)

                ptr->right = Delete(ptr->right, value);

           else if (value < ptr->data)

                ptr->left = Delete(ptr->left, value);

           ////////

           //第三種情形

           else

           {

                temp = GetSmallest(ptr->right);

                temp->left = ptr->left;

                ptr = ptr->right;

           }

           /////////

     }

     else

           cout << "Sorry, the input does not match any node's value in the tree.\n";

     return ptr;

}

int main(int argc, char* argv[])

{

    int i, key;

    root = NULL;

    for (i = 0; i < 6; i++)

    {

           cout << "Enter number " << i+1 << " > " ;

           cin >> key;

           if (root == NULL)   // 插入第一個數字

           {

                root = new struct node;

                root->data = key;

                root->left = root->right = NULL;

           }

           else  // 插入第二個以後的數字

           {

                tree = root;

                while (tree != NULL)

                {

                     if (key == tree->data)  // 要插入的數字已經存在於樹中

                     {

                           cout << "duplicate node!";

                           break;

                     }

                     else if (key < tree->data)   // 要插入的數字< 節點數字, 向左子樹移動

                     {

                           if (tree->left != NULL)

                                tree = tree->left; // 向左子樹移動

                           else // 沒有左子樹時, 則新增節點, 放置要插入的數字

                           {

                                t = new struct node;

                                t->data = key;

                                t->left = t->right = NULL;

                                tree->left = t;

                                break;

                           }

                     }

                     else // 要插入的數字> 節點數字, 向右子樹移動

                     {

                           if (tree->right != NULL)

                                tree = tree->right; // 向右子樹移動

                           else // 沒有右子樹時, 則新增節點, 放置要插入的數字

                           {

                                t = new struct node;

                                t->data = key;

                                t->left = t->right = NULL;

                                tree->right = t;

                                break;

                           }

                     }

                }

           }

     }

     cout << "root->left->left->data = " << root->left->left->data << endl;

     Delete(root, 0);

     cout << "root->left->data = " << root->left->data << endl;

     if (root->left->left == NULL)

           cout << "root->left->left == NULL";

     //例如插入3 1 4 0 2 5 ，經Delete(root, 0)後，就會發現被刪掉了

     system("pause");

    return 0; // 設置中斷點, 察看樹的形狀

}