Binary Search Tree IN C-白红宇

Binary Search Tree IN C

阅读量：5894 次

发布时间：2019-06-19

本文共 2601 字，大约阅读时间需要 8 分钟。


    #include "stdafx.h"#include 
    
     #include 
     
      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;}