Monday, January 2, 2012

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; // 設置中斷點, 察看樹的形狀
}

No comments:

Post a Comment