두 갈래 정렬 트 리 의 결점 삭제

13323 단어 데이터 구조
      8
    3    9   
  2   6    10
1    4  7 
      5

위 에는 1 부터 10 까지 의 이 진 트 리 가 있다.어떻게 이 진 트 리 의 노드 삭 제 를 실현 합 니까?만약 에 우리 가 결점 6 을 삭제 하면 먼저 전구 결점 이나 후계 노드 를 찾 습 니 다. 6 의 전구 결점 은 5 이 고 후계 가 7 입 니 다. 결점 6 을 삭제 한 후에 나 무 는 어떻게 변화 해 야 하 는 지 상상 해 보 세 요.사실 6 을 5 로 바 꾸 고 5 의 노드 를 삭제 하면 된다.
전구 나 후계 의 도 는 1 또는 0 이 므 로 주의 하 세 요.
(PS: 이 건 마늘 손님 에 게 서 배 운 것 이지 광 고 를 하 는 것 이 아니 라 권리 침해 하면 삭제 합 니 다)
#include <iostream>
#include <cstdlib>

using namespace std;

class Node
{
public:
    int data;
    Node *lchild, *rchild, *father;
    Node(int _data, Node*_father=NULL){
        data = _data;
        lchild = NULL;
        rchild = NULL;
        father = _father;
    }
    ~Node(){
        if(lchild != NULL)
            delete lchild;
        if(rchild != NULL)
            delete rchild;
    }
    void myInsert(int value){
        if(data == value)
            return;
        else if(value < data){
            if(lchild == NULL)
                lchild = new Node(value, this);
            else
                lchild->myInsert(value);
        }
        else{
            if(rchild == NULL)
                rchild = new Node(value, this);
            else
                rchild->myInsert(value);
        }
    }

    Node *mySearch(int value){
        if(data == value)
            return this;
        else if(value < data){
            if(lchild == NULL)
                return NULL;
            else
                lchild->mySearch(value);
        }
        else{
            if(rchild == NULL)
                return NULL;
            else
                rchild->mySearch(value);
        }
    }
    /*    */
    Node *predecessor(){
        Node *temp = lchild;
        while(temp!=NULL && temp->rchild!=NULL){
            temp = temp->rchild;
        }
        return temp;
    }
    /*    */
    Node *successor(){
        Node *temp = rchild;
        while(temp!=NULL && temp->lchild!=NULL){
            temp = temp->lchild;
        }
        return temp;
    }

    /*    1 0   */
    void removeNode(Node *nodeOfdelete){
        /*      temp    NULL*/
        Node *temp = NULL;
        if(nodeOfdelete->lchild != NULL){
            temp = nodeOfdelete->lchild;
            /*              */
            temp->father = nodeOfdelete->father;
            /*            lchild rchild  NULL,  Node      */
            nodeOfdelete->lchild = NULL;
        }
        if(nodeOfdelete->rchild != NULL){
            temp = nodeOfdelete->rchild;
            temp->father = nodeOfdelete->father;
            nodeOfdelete->rchild = NULL;
        }
        /*    if      ,  if          */
        if(nodeOfdelete->father->lchild == nodeOfdelete)
            nodeOfdelete->father->lchild = temp;
        if(nodeOfdelete->father->rchild == nodeOfdelete)
            nodeOfdelete->father->rchild = temp;
        delete nodeOfdelete;
    }

    bool deleteNode(int value){
        Node *currentNode, *nodeOfdelete;
        currentNode = mySearch(value);
        if(currentNode == NULL)
            return false;
        /*    */
        if(currentNode->lchild != NULL)
            nodeOfdelete = currentNode->predecessor();
        /*     */
        else if(currentNode->rchild != NULL)
            nodeOfdelete = currentNode->successor();
        /*           */
        else
            nodeOfdelete = currentNode;
        /*     data */
        currentNode->data = nodeOfdelete->data;
        /*           1   ,                  ,     remove      */
        removeNode(nodeOfdelete);
        return true;
    }

    void inOrder(){
        if(lchild != NULL)
            lchild->inOrder();
        cout<<data<<" ";
        if(rchild != NULL)
            rchild->inOrder();
    }

};

class BinaryTree
{
private:
    Node *root;
public:
    BinaryTree(){
        root = NULL;
    }
    ~BinaryTree(){
        if(root != NULL)
            delete root;
    }
    void myInsert(int value){
        if(root == NULL)
            root = new Node(value);
        else
            root->myInsert(value);
    }
    void mySearch(int value){
        if(root->mySearch(value) != NULL)
            cout << "  " <<endl;
        else
            cout << "   " << endl;
    }
    void deleteNode(int value){
        if(root->deleteNode(value))
            cout << "    " <<endl;
        else
            cout << "    " <<endl;
    }
    void inOrder(){
        if(root != NULL)
            root->inOrder();
    }
};

int main(){
    BinaryTree binarytree;
    int arr[] = {-111, 0, 22, 4, 3, 8, -2, -11, 123, 2333, 44, 9, 100};

    for(int i=0; i<13; i++)
        binarytree.myInsert(arr[i]);
    binarytree.inOrder();
    cout<

질문 이나 오류 가 있 으 시 면 환영 합 니 다. 감사합니다.

좋은 웹페이지 즐겨찾기