我这有个二叉树生成和删除节点的程序！不过是拿c写的，楼主可以看看
#include <stdlib.h>
#include <stdio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;
b_tree InsertChild(b_tree root,int node)
{
b_tree newnode; /*Òª¼ÓÈëµÄ½Úµã*/
b_tree parentnode; /*¸¸½Úµã*/
b_tree currentnode; /*µ±Ç°½Úµã*/
newnode=(b_tree)malloc(sizeof(treenode));
newnode->data=node;
newnode->left=NULL;
newnode->right=NULL;
/*Ê÷¿Õʱ£¬Ëù¼ÓÈë½ÚµãΪ¸ù½Úµã*/
if(root==NULL)
return newnode;
/*Ê÷²»¿Õʱ£¬Ñ°ÕÒÕýȷλÖüÓÈë½Úµã*/
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->data > node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->data > node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return root;
}
/*´ÓÊý×éÖÐÒÀ´Î¶ÁÈëÊý¾Ý£¬Éú³É¶þ²æÊ÷*/
b_tree CreateBiTree(int *data,int len)
{
b_tree root=NULL;
int i;
for (i=0;i<len;i++)
root=InsertChild(root,data[i]);
return root;
}
void PreOrder(b_tree pointer)
{
if(pointer!=NULL)
{
printf("%d ",pointer->data);
PreOrder(pointer->left);
PreOrder(pointer->right);
}
}
void InOrder(b_tree pointer)
{
if(pointer!=NULL)
{
InOrder(pointer->left);
printf("%d ",pointer->data);
InOrder(pointer->right);
}
}
void PostOrder(b_tree pointer)
{
if(pointer!=NULL)
{
PostOrder(pointer->right);
printf("%d ",pointer->data);
PostOrder(pointer->left);
}
}
/*¶¨Ò常½ÚµãλÖÃ*/
b_tree SearchBiTree(b_tree pointer,int node,int *position)
{
b_tree parent;
parent=pointer;
*position=0;
while(pointer!=NULL)
{
if(pointer->data==node)
return parent; /*positionΪ0ʱ£¬½ÚµãÎÞ¸¸½Úµã*/
else
{
parent=pointer;
if(pointer->data > node)
{
pointer=pointer->left;
*position=-1; /*positionΪ-1ʱ£¬½ÚµãΪ¸¸½ÚµãµÄ×ó×Ó½Úµã*/
}
else
{
pointer=pointer->right;
*position=1; /*positionΪ1ʱ£¬½ÚµãΪ¸¸½ÚµãµÄÓÒ×Ó½Úµã*/
}
}
}
return NULL;
}
b_tree DeleteNode(b_tree root,int node)
{
b_tree parent;
b_tree child;
b_tree pointer;
int position;
parent=SearchBiTree(root,node,&position);
if(parent==NULL)
return root;
else
{
switch(position)
{
case -1 : pointer=parent->left;
break;
case 1 : pointer=parent->right;
break;
case 0 : pointer=parent;
break;
}
/*×óÓÒ×ÓÊ÷¶¼Îª¿Õ*/
if(pointer->left==NULL && pointer->right==NULL)
{
switch(position)
{
case -1: parent->left=NULL;
break;
case 1: parent->right=NULL;
break;
case 0: parent=NULL;
}
return root;
}
/*½ÚµãÎÞ×ó×ÓÊ÷ÓÐÓÒ×ÓÊ÷*/
if (pointer->left==NULL && pointer->right!=NULL)
{
if(position==-1)
parent->left=pointer->right;
else if(position==1)
parent->right=pointer->right;
else if(position==0)
root=root->right;
free(pointer);
return root;
}
/*½ÚµãÎÞÓÒ×ÓÊ÷ÓÐ×ó×ÓÊ÷*/
else if (pointer->left!=NULL && pointer->right==NULL)
{
if(position==-1)
parent->left=pointer->left;
else if(position==1)
parent->right=pointer->left;
else if(position==0)
root=root->left;
free(pointer);
return root;
}
/*½Úµã×óÓÒ×ÓÊ÷¶¼²»Îª¿Õ(ÓÃ×ó×ÓÊ÷×îÓұߵĽڵã´úÌæ)*/
else if (pointer->left!=NULL && pointer->right!=NULL)
{
child=pointer->left;
/*Ðèɾ³ý½ÚµãµÄ×ó×Ó½ÚµãÎÞÓÒ×ÓÊ÷*/
if(child->right==NULL)
{
pointer->left=child->left;
pointer->data=child->data;
}
/*Ðèɾ³ý½ÚµãµÄ×ó×Ó½ÚµãÓÐÓÒ×ÓÊ÷£¬ÕÒµ½×îÓұߵĽڵ㣬Ìæ»»²¢É¾³ý*/
else
{
parent=pointer;
while(child->right!=NULL)
{
parent=child;
child=child->right;
}
pointer->data=child->data;
if(child->left==NULL)
parent->right=child->right;
else
parent->right=child->left;
}
free(child);
return root;
}
}
}
b_tree SearchNode(b_tree pointer,int findnode)
{
while(pointer!=NULL)
{
if(pointer->data==findnode)
return pointer;
else if(pointer->data > findnode)
pointer=pointer->left;
else
pointer=pointer->right;
}
return NULL;
}
void main()
{
#define index 11
FILE *fp;
b_tree root=NULL;
b_tree pointer=NULL;
int nodelist[index];
int deletenode,select;
int i,temp;
if((fp=fopen("D:\\NewD\\BinaryTree\\Del\\tree.txt","r"))==NULL)
{
printf("The file can not open!!\n");
return;
}
while(!feof(fp))
{
for(i=0;i<index;i++)
{
fscanf(fp,"%d",&temp);
nodelist[i]=temp;
}
}
fclose(fp);
root=CreateBiTree(nodelist,index);
printf("(1) PreOrder ouput: \n");
printf("(2) InOrder output : \n");
printf("(3) PostOrder output : \n");
printf("Please input your select : ");
scanf("%d",&select);
printf("The orignal tree is : ");
printf("\n");
switch(select)
{
case 1:
PreOrder(root);
break;
case 2:
InOrder(root);
break;
case 3:
PostOrder(root);
break;
}
printf("\n");
printf("Please input the node you want to delete : ");
scanf("%d",&deletenode);
root=DeleteNode(root,deletenode);
while(pointer=SearchNode(root,deletenode)!=NULL)
root=DeleteNode(root,deletenode);
printf("(1) PreOrder ouput: \n");
printf("(2) InOrder output : \n");
printf("(3) PostOrder output : \n");
printf("Please input your select : ");
scanf("%d",&select);
printf("The deleted tree is : ");
printf("\n");
switch(select)
{
case 1:
PreOrder(root);
break;
case 2:
InOrder(root);
break;
case 3:
PostOrder(root);
break;
}
printf("\n");
}
