二叉树程序设计

二叉树的程序设计结点的增加删除修改查询

这样的代码网上有很多，这里我再VS运行成功的C语言代码供参考吧。也是自己学习二叉树创建查找的资料。

/*************************************************************************
这是一个二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、查找、
查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度
均为o(h),其中h是树的高度
注释很详细，具体内容就看代码吧
*************************************************************************/
#include
#include
//二叉查找树结点描述
typedefintKeyType;
typedefstructNode
{
KeyTypekey;//关键字
structNode*left;//左孩子指针
structNode*right;//右孩子指针
structNode*parent;//指向父节点指针
}Node,*PNode;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
voidinseart(PNode*root,KeyTypekey)
{
//初始化插入结点
PNodep=(PNode)malloc(sizeof(Node));
p->key=key;
p->left=p->right=p->parent=NULL;
//空树时，直接作为根结点
if((*root)==NULL){
*root=p;
return;
}
//插入到当前结点（*root）的左孩子
if((*root)->left==NULL&&(*root)->key>key){
p->parent=(*root);
(*root)->left=p;
return;
}
//插入到当前结点（*root）的右孩子
if((*root)->right==NULL&&(*root)->keyp->parent=(*root);
(*root)->right=p;
return;
}
if((*root)->key>key)
inseart(&(*root)->left,key);
elseif((*root)->keyinseart(&(*root)->right,key);
else
return;
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
PNodesearch(PNoderoot,KeyTypekey)
{
if(root==NULL)
returnNULL;
if(key>root->key)//查找右子树
returnsearch(root->right,key);
elseif(keykey)//查找左子树
returnsearch(root->left,key);
else
returnroot;
}
//查找最小关键字,空树时返回NULL
PNodesearchMin(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->left==NULL)
returnroot;
else//一直往左孩子找，直到没有左孩子的结点
returnsearchMin(root->left);
}
//非递推查找最小关键字
PNodesearchMin2(PNoderoot)
{
if(root==NULL)
returnNULL;
while(root->left!=NULL)
root=root->left;
returnroot;
}
//查找最大关键字,空树时返回NULL
PNodesearchMax(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->right==NULL)
returnroot;
else//一直往右孩子找，直到没有右孩子的结点
returnsearchMax(root->right);
}
//查找某个结点的前驱
PNodesearchPredecessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有左子树、左子树中最大的那个
if(p->left)
returnsearchMax(p->left);
//无左子树,查找某个结点的右子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找前驱
while(p){
if(p->parent->right==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//查找某个结点的后继
PNodesearchSuccessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有右子树、右子树中最小的那个
if(p->right)
returnsearchMin(p->right);
//无右子树,查找某个结点的左子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找后继
while(p){
if(p->parent->left==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//根据关键字删除某个结点,删除成功返回1,否则返回0
//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
intdeleteNode(PNode*root,KeyTypekey)
{
PNodeq;
//查找到要删除的结点
PNodep=search(*root,key);
KeyTypetemp;//暂存后继结点的值
//没查到此关键字
if(!p)
return0;
//1.被删结点是叶子结点，直接删除
if(p->left==NULL&&p->right==NULL){
//只有一个元素，删完之后变成一颗空树
if(p->parent==NULL){
free(p);
(*root)=NULL;
}else{
//删除的结点是父节点的左孩子
if(p->parent->left==p)
p->parent->left=NULL;
else//删除的结点是父节点的右孩子
p->parent->right=NULL;
free(p);
}
}
//2.被删结点只有左子树
elseif(p->left&&!(p->right)){
p->left->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->left;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->left;
else//删除的结点是父节点的右孩子
p->parent->right=p->left;
free(p);
}
//3.被删结点只有右孩子
elseif(p->right&&!(p->left)){
p->right->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->right;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->right;
else//删除的结点是父节点的右孩子
p->parent->right=p->right;
free(p);
}
//4.被删除的结点既有左孩子，又有右孩子
//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)
//删掉后继结点,后继结点的值代替该结点
else{
//找到要删除结点的后继
q=searchSuccessor(p);
temp=q->key;
//删除后继结点
deleteNode(root,q->key);
p->key=temp;
}
return1;
}
//创建一棵二叉查找树
voidcreate(PNode*root,KeyType*keyArray,intlength)
{
inti;
//逐个结点插入二叉树中
for(i=0;iinseart(root,keyArray[i]);
}
intmain3(void)
{
inti;
PNoderoot=NULL;
KeyTypenodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
create(&root,nodeArray,11);
for(i=0;i<2;i++)
deleteNode(&root,nodeArray[i]);
printf("%d\n",searchPredecessor(root)->key);
printf("%d\n",searchSuccessor(root)->key);
printf("%d\n",searchMin(root)->key);
printf("%d\n",searchMin2(root)->key);
printf("%d\n",searchMax(root)->key);
printf("%d\n",search(root,13)->key);
system("pause");
return0;
}

用c语言编程实现二叉树的建立和遍历二叉树？