二叉樹操作複習

2017-08-29 11:46:37

writer：pprp

已經寫了二叉樹好幾次了，但是還是有很多細節沒有考慮完全

還有好多東西都沒有考慮到，以後還是要寫這個代碼，把應該考慮的細節都考慮清楚

在寫有關樹的函數的時候都要小心地處理空樹的這種退化情況

代碼及講解如下：（都測試過了，應該沒問題，如果有問題請留言）

/*
@theme:樹的建立和周遊
@writer:pprp
@start:10:00
@end:11:47
@declare:我建立的這個樹好像跟教科書上的樹方向反了一下，
但是不影響了解，教科書上的是大的在右邊，小的在左邊，我的恰好反了過來
@date:2017/8/28
*/

#include <bits/stdc++.h>

using namespace std;

struct tree
{
    int val;
    tree * l;
    tree * r;
};

//function 1 insert
//插入操作，比根節點大的要在左子樹，比根節點小的要放在右子樹
//test:ok
tree * Insert(tree *root, int val)
{
    tree * parent;
    tree * current;

    tree * newVal = new tree();

    newVal->val = val;
    newVal->r = NULL;
    newVal->l = NULL;

    if(root == NULL)
    {
        root = newVal;
    }
    else
    {
        current = root;
        while(current != NULL)
        {
            parent = current;
            if(current->val < val)//這裡的符号要與下邊的符号一緻
            {
                current = current->l;
            }
            else
            {
                current = current->r;
            }
        }

        if(parent->val < val) //這裡的符号要跟上邊的符号一緻
        {
            parent->l = newVal;
        }
        else
        {
            parent->r = newVal;
        }
    }
    return root;
}

//function 2: MakeEmpty
//test: ok
tree* MakeEmpty(tree * root)
{
    if(root != NULL)
    {
        MakeEmpty(root->r);
        MakeEmpty(root->l);
        delete root;
        root = NULL;
    }
    return NULL;
}

//function 3: Find value
//test:ok
//@param:傳回一個指針，代表找到該節點的指針，否則傳回NULL
tree* FindValue(tree * root,int val)
{
    if(root == NULL)
        return NULL;
    if(val < root->val)
        return FindValue(root->r,val);
    else if(val > root->val)
        return FindValue(root->l,val);
    else
        return root;
}

//function 4:Find Min
//由于樹的構造是有大小之分的是以找小的直接向有子樹找就好
//test:ok
tree* FindMin(tree * root)
{
    if(root == NULL)
        return NULL;
    else if(root->r == NULL)
        return root;
    else
        return FindMin(root->r);
}

//function 5: Find Max
//直接向右子樹查找就好了
//test:ok
tree * FindMax(tree * root)
{
    if(root == NULL)
        return NULL;
    else if(root->l == NULL)
        return root;
    else
        return FindMax(root->l);
}

////function 6: delete
////test:error
////錯誤原因：思路不大對，如果隻有一個子節點的情況，還需要判斷這個本身是左邊子節點還是右邊子節點
//tree * Delete(tree * root, int val)
//{
//    tree * current = FindValue(root, val);
//    tree * tmp = NULL;
//    if(current->l == NULL && current->r == NULL)  //如果兩個孩子都沒有就可以直接删除掉
//    {
//        delete(current);
//    }
//    else if(current != NULL) //隻有左孩子,将左孩子中最小的值變成原先節點
//    {
//        tmp = FindMin(current);
//        current->val = tmp->val;
//        delete(tmp);
//        tmp = NULL;
//    }
//    else if(current->r != NULL) //隻有右孩子
//    {
//        tmp = FindMax(current);
//        current->val = tmp->val;
//        delete(tmp);
//        tmp = NULL;
//    }
//    else        //兩個孩子都有
//    {
//        tmp = FindMin(current);
//        current->val = tmp->val;
//        delete(tmp);
//        tmp = NULL;
//    }
//}

//function 6: delete
//test:ok
//要删除的節點值為val,最後傳回已經修改過的頭結點
tree * Delete(tree * root, int val)
{
    tree * par;
    tree * kid;
    //第一部分找到該節點并找到該節點的父親節點
    kid = root;
    while(kid != NULL)
    {

        if(kid->val > val)
        {
            par = kid;
            kid = kid->r;
        }
        else if(kid->val < val)
        {
            par = kid;
            kid = kid->l;
        }
        else if(kid->val == val)
        {
            break;  //這時候kid指向的是要找的節點 par記錄的是要找的節點的父親節點
        }
    }

    //沒有找到的情況
    if(kid == NULL)
    {
        cout << "not find! " << endl;
        return NULL;
    }
    //現在開始判斷是那種情況
    //1、如果是都是為空的情況
    if(kid->l == NULL && kid->r == NULL)
    {
        if(kid == root) //沒有想到，如果是根節點，那麼就直接指派根節點為空
            root = NULL;
        if(par->l == kid)
            par->l = NULL;
        if(par->r == kid)
            par->r = NULL;
        delete(kid);
    }//2、隻有一個節點的情況
    else if(kid->l == NULL || kid->r == NULL)
    {
        if(kid == root)
        {
            if(kid->r == NULL)
                root = kid->l;
            else
                root = kid->r;
            delete(root);
        }
        else  //分情況讨論 
        {
              if(par->r == kid && kid->l)
              {
                    par->r = kid->l;
              }
              else if(par->r == kid && kid->r)
              {
                    par->r =  kid->r;
              }
              else if(par->l == kid && kid->l)
              {
                     par->l = kid->l;
              }
              else if(par->l == kid && kid->r)
              {
                     par->l = kid->r;
              }
              delete(kid);
        }
    } //3、有兩個子節點的情況，這裡采用将左邊最小的替換找到節點的方案
    else
    {
           tree * tmp = FindMin(kid);
           kid->val = tmp->val;
           delete(tmp);
    }
    return root;
}

//前序周遊輸出 -- ok
void preOut(tree * root)
{
    if(root != NULL)
    {
        cout << root->val <<" ";
        preOut(root->l);
        preOut(root->r);
    }
}

//中序周遊輸出--ok
void midOut(tree * root)
{
    if(root != NULL)
    {
        midOut(root->l);
        cout << root->val << " ";
        midOut(root->r);
    }
}

//後序周遊輸出--ok
void backOut(tree * root)
{
    if(root != NULL)
    {
        backOut(root->l);
        backOut(root->r);
        cout << root->val << " ";
    }
}

int main()
{
    int n;
    cin >> n;
    int a[100];

    tree * root = NULL;

    for(int i = 0 ; i < n ; i++)
    {
        srand((int)time(NULL)+i);
        a[i] = rand()%100;
    }

    for(int i = 0 ; i < n ; i++)
        cout << a[i] <<" ";
    cout << endl;

    //create a tree
    for(int i = 0 ; i < n ; i++)
    {
        root = Insert(root, a[i]);
    }

    cout << "preOut:" << endl;
    preOut(root);
    cout << endl;

//    root = MakeEmpty(root);
//    cout << "preOut:" << endl;
//    backOut(root);
//    cout << endl;

//    int val;
//    cin >> val;
//    tree * tmp = FindValue(root,val);
//    if(tmp != NULL)
//      cout << tmp->val << endl;

    tree * tmp = FindMax(root);
    if(tmp != NULL)
        cout << tmp->val << endl;

    tmp = FindMin(root);
    if(tmp != NULL)
        cout << tmp->val << endl;

    cout << "-----" << endl;

    int val;
    cin >> val;
    root = Delete(root,val);

    cout << "preOut:" << endl;
    preOut(root);
    cout << endl;

    return 0;
}      

代碼改變世界