Binary Search Tree IN C

<!-- lang: cpp -->
#include "stdafx.h"
#include <iostream>
#include <malloc.h>

typedef struct Node{
    Node* parent;
    Node* left;
    Node* right;
    int key;
}node;

node* NodeInit(int data){
    node* n=(node*)malloc(sizeof(node*));
    n->parent = (node*)malloc(sizeof(node*));
    n->left = (node*)malloc(sizeof(node*));
    n->right = (node*)malloc(sizeof(node*));
    n->key = (int)malloc(sizeof(int));

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;
    n->key = data;

    return n;
}    

void InsertNode(node* root, int data){
    if(data < root->key){
        if(root->left){
            InsertNode(root->left,data);
        }else{
            root->left = NodeInit(data);
            root->left->parent = root;
        }
    }else{
        if(root->right){
            InsertNode(root->right,data);
        }else{
            root->right = NodeInit(data);
            root->right->parent = root;
        }
    }
}

void inorderTraversal(node* root){
    if(root->left)
        inorderTraversal(root->left);
    printf(" %d ",root->key);
    if(root->right)
        inorderTraversal(root->right);
}    

node* MaxNode(node* root){
    if(root->right)
        return MaxNode(root->right);
    else
        return root;
}

node* MinNode(node* root){
    if(root->left)
        return MinNode(root->left);
    else
        return root;
}    

node* Search(node* root, int data){
    if(data == root->key){
        return root;
    }else if(data < root->key){
        if(root->left)
            return Search(root->left,data);
        else
            return NULL;
    }else if(data > root->key){
        if(root->right)
            return Search(root->right,data);
        else
            return NULL;
    }
}    

node* Sucessor(node* n){
    node *p;
    if(n->right){
        return MinNode(n->right);
    }else{
        p = n->parent;
        while(p && p->right == n){
            n=p;
            p=p->parent;
        }
        return p;
    }
}

void DelNode(node* root,node* n){
    node* temp;
    if(root == n){
        temp = Sucessor(n);
        if(temp == n)   printf("No node left in this tree!\n");
        DelNode(root,temp);
        root->key = temp->key;

        return;
    }

    if(n->left==NULL && n->right==NULL){
        if(n->parent->left == n)
            n->parent->left = NULL;
        else
            n->parent->right = NULL;
    }else if(n->left && n->right==NULL){
        if(n->parent->left == n){
            n->parent->left = n->left;
            n->left->parent = n->parent;
        }else{
            n->parent->right = n->left;
            n->left->parent = n->parent;
        }
    }else if(n->right && n->left ==NULL){
        if(n->parent->left == n){
            n->parent->left = n->right;
            n->right->parent = n->parent;
        }else{
            n->parent->right = n->right;
            n->right->parent = n->parent;
        }       
    }else{
        temp = Sucessor(n);
        n->key = temp->key;
        DelNode(root,temp);
    }
}    

int main(){
    node* root = NodeInit(10);
    int i,j;
    for(i=1;i<20;i=i+2){
        InsertNode(root,i);
        inorderTraversal(root);
        printf("\n");
    }
    DelNode(root,Search(root,10));
    inorderTraversal(root);

    getchar();
    return 0;
}    

你可能感兴趣的