paixushu.txt

二叉排序树,实现二叉树的排序。可删除结点。

#include<stdafx.h> 


#include <malloc.h> 
#include <stdio.h> 

typedef struct node 
{ 
int data; 
struct node *left, 
*right; 
}NODE; 

void Insert(NODE **root, NODE *node) 
{ 
NODE *tmp = *root; 
if ( *root == NULL) 
*root = node; 
else if ( node->data > (*root)->data ) 
Insert(&(*root)->right, node); 
else if (node->data < (*root)->data) 
Insert(&(*root)->left, node); 
else 
printf("  *** Repeated values, just drop it!***\n"); 
return; 
}//尾递归 

void CreateTree(NODE **root) 
{ 
int value; 
NODE *tmp = NULL; 
printf("\tNow let's begin to create a binary searching tree.\n" 
   "\tValue 0 means your input is over.\n\n"); 
do 
{ 
printf("  Please input the value for tree node: "); 
scanf("%d", &value); 
if (value == 0) 
break; 
tmp       = (NODE *)malloc(sizeof(NODE)); 
tmp->data = value; 
tmp->left = tmp->right=NULL; 
Insert(root, tmp); 
}while(value != 0); 
} 

void InOrderTree(NODE * root) 
{ 
if (root != NULL) 
{ 
InOrderTree(root->left); 
printf(" %3d", root->data); 
InOrderTree(root->right); 
} 
} 

NODE * DeleteNode(NODE *root, int value) 
{ 
NODE *tmp = root; 
NODE *par = tmp; 
NODE *sub = NULL; 
while ( tmp!=NULL && tmp->data!=value ) 
{ 
par = tmp; 
if ( tmp->data > value ) 
tmp = tmp->left; 
else 
tmp = tmp->right; 
} 

if ( NULL == tmp )//the value does not exist. 
{ 
printf("\n  Can't find the node. Delete failure!\n"); 
return root; 
} 

if ( NULL == tmp->left)//left child is null. 
{ 
if ( par == tmp )//删除没有left孩子的根节点 
{ 
root = root->right; 
return root; 
} 
if ( par->left == tmp) 
par->left  = tmp->right; 
else 
par->right = tmp->right; 
free(tmp); 
return root; 
} 
else //it has left child 
{//并不真正的删除节点，而是把要删除的节点的value覆盖掉 
par = tmp; 
sub = tmp->left; 
while (sub->right) 
{ 
par   = sub; 
sub = sub->right; 
} 
tmp->data = sub->data; 
if (par != tmp) 
par->right = sub->left; 
else 
par->left  = sub->left; 
return root; 
} 
} 

int main() 
{ 
NODE *root = NULL; 
CreateTree(&root); 
printf("\n  The orginal tree is :\n"); 
InOrderTree(root); 
root = DeleteNode(root,6);     //假设删除节点值为6的节点 
printf("\n\n  After delete node, now the tree is :\n"); 
InOrderTree(root); 
printf("\n\n"); 
return 0; 
}