请教高手一个二叉树问题——焦急等待~
二叉树的建立、查询、打印和遍历的源程序：
#include<iostream.h>
#include<stdio.h>
//******************************************
//define the structure of an element of a tree
//******************************************
struct tree {
char info;
struct tree *left,*right;
};
//******************************************
//explanation the functions
//******************************************
struct tree *create_btree(struct tree *root,struct tree *r,char info);
struct tree *search_btree(struct tree *root,char key);
void print_btree(struct tree *r,int l);
void PreOrder(struct tree *T); //先序递归遍历二叉树
void InOrder(struct tree *T); //中序递归遍历二叉树
void PostOrder(struct tree *T);
//******************************************
// the main function
//******************************************
void main()
{ char s[100], c ;
struct tree *root=0, *p;
printf("Input a letter for Creating the Binary_Tree ( Directly press <Enter> to stop ):\n");
do {
printf("Input a letter: ");
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btree(root,root,*s);
} while (*s) ;
while ( c!='!')
{
print_btree(root,0);
printf("Enter a character to find( '!' to stop ):");
scanf("%s",&c);
printf("\n");
p=search_btree(root,c);
printf("\n");
}
printf("\n先序遍历结果：");
PreOrder(root); //先序递归遍历二叉树
printf("\n中序遍历结果：");
InOrder(root);
printf("\n后序遍历结果："); //中序递归遍历二叉树
PostOrder(root);
printf("\n");
} /* Btree.C 结束 */
struct tree *create_btree(struct tree *root,struct tree *r,char info)
{ if (r ==0 )
{ r=new (struct tree);
if ( r == 0)
{ printf("Out of memory\n"); return 0 ; }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
}
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
//******************************************
//tree *search_btree(struct tree *root,char key)
//******************************************
struct tree *search_btree(struct tree *p,char key)
{ struct tree *root;
root=p;
if (!root)
{ printf("Empty btree\n"); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf("Search Failure\n");
return 0;
}
} /* while(root->info!=key) */
if (root !=0)
printf("Successful search\n key=%c\n",root->info);
return root ;
} /* *search_btree(root,key) */
//************************************
// print_btree
//************************************
void print_btree(struct tree *r,int l)
{ int i;
if (r == 0) return ;
print_btree(r->left,l+1);
for(i=0;i<l;i++) printf(" ");
printf("%c\n",r->info);
print_btree(r->right,l+1);
}
void PreOrder(struct tree *T)
{
if(T)
{
printf("%c",T->info); //访问结点
PreOrder(T->left); //遍历左子树
PreOrder(T->right); //遍历右子树
}
}
void InOrder(struct tree *T)
{if(T)
{
InOrder(T->left); //遍历左子树
printf("%c",T->info); //访问结点
InOrder(T->right); //遍历右子树
}
}
void PostOrder(struct tree *T)
{
if(T)
{
PostOrder(T->left); //遍历左子树
PostOrder(T->right); //访问结点
printf("%c",T->info); //遍历右子树
}
}
请帮我增加一个删除节点的函数
高分结贴~
问题点数：0、回复次数：4Top
1 楼leyt（思维机器）回复于 2003-11-04 18:13:05 得分 0
好的Top
2 楼plainsong（短歌)(）回复于 2003-11-04 18:28:07 得分 0
自己写吧：
找到要删除的节点N
if N无左子树 then
用N右子树根节点代替N，然后释放N
else if N无右子树
用N左子树根节点代替N，然后释放N
else
将N与N右子树中的最小节点交换然后删除N
endif
找一个树N的最小节点：
if N无左子树
Result = N
else
Result = N左子树的最小节点
endifTop
3 楼xinyue2002（星星）回复于 2003-11-04 19:25:49 得分 0
十万火急，还有吗？谢谢Top
4 楼hongfeeling（无烟亦如烟）回复于 2003-11-05 08:44:13 得分 0
没有现成的.Top
