//二叉树的基本操作///////////////////////////
#include <stdio.h>
#include <malloc.h>
//定义二叉树
typedef struct bitnode
{
int data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
//创建二叉树利用先序创建
void createbitree(bitree *T)
{
int dat;
printf("Please Input data:");
scanf("%d",&dat);
if(dat==0) (*T) = NULL;
else
{
(*T) = (bitree)malloc(sizeof(bitnode));
(*T)->data=dat;
createbitree(&((*T)->lchild));
createbitree(&((*T)->rchild));
}
}
//二叉树的先序周游递归算法
void postorder10(bitree T)
{
if (T != NULL)
{
printf("%d\t",T->data);
postorder10(T->lchild);
postorder10(T->rchild);
}
}
//二叉树的先序周游非递归算法
void postorder11(bitree t)
{ bitree s[100];
int top=0;
while (t!=NULL || top!=0)
{
while (t!=NULL)
{
printf("%d\t",t->data); s[++top]=t; t=t->lchild ;
}
if (top!=0)
{
t=s[top--]->rchild;
}
}
}
//二叉树的中序周游递归算法
void postorder20(bitree T)
{
if (T != NULL)
{
postorder20(T->lchild);
printf("%d\t",T->data);
postorder20(T->rchild);
}
}
//二叉树的中序周游非递归算法
void postorder21(bitree t)
{
bitree s[100];//指针数组（栈），存放按中序访问的节点的地址
int top=0;
while (t!=NULL || top!=0)
{
while (t!=NULL)
{
s[++top]=t; t=t->lchild ;
}
if (top!=0)
{
t=s[top--]; printf("%d\t",t->data); t=t->rchild;
}
}
}
//二叉树的后序周游递归算法
void postorder30(bitree T)
{
if (T != NULL)
{
postorder30(T->lchild);
postorder30(T->rchild);
printf("%d\t",T->data);
}
}
//二叉树的后序周游非递归算法
void postorder31(bitree t)
{
typedef struct node
{ bitree t; int tag;
} stack;
stack s[100] ;
int top=0;
while (t!=NULL|| top!=0)
{while (t!=NULL)
{s[++top].t=t; s[top].tag=0; t=t->lchild; }
while (top!=0 && s[top].tag==1)
printf("%d\t" ,s[top--].t->data);
if (top)
{ s[top].tag=1; t=s[top].t->rchild ; }
}
}
|
第1楼
//在二叉树t中查找值为x的结点
void locate(bitree t, int x)
{
bitree p;
p=t;
if (t == NULL)
printf("0\n");
else if( t->data == x)
printf("%d\n",p->data);
else
{
p=t->lchild;
if (p)
locate(t->lchild, x);
else
locate(t->rchild, x);
}
}
//以二叉链表作存储结构，试编写求二叉树深度的算法
int BinTreeDetth(bitree T)
{
int l,r;
if(T==NULL)return 0;
else
{
l=BinTreeDetth(T->lchild);
r=BinTreeDetth(T->rchild);
return((l>r?l:r)+1);
}
}
//以二叉链表作为存储结构，试编写求二叉树中叶子数的算法
int LeafCount1(bitree T)
{
int i,j;
if(!T) return 0; //空树没有叶子
else if(T->lchild==NULL&&T->rchild==NULL)
{
return 1; //叶子结点
}
else
{
i=LeafCount1(T->lchild);
j=LeafCount1(T->rchild);
return (i+j);
}
//左子树叶子数加上右子树叶子数
}
//以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。
int num=0;
void LeafCount2(bitree T)
{
if(T)
{LeafCount2(T->lchild) ; //中序遍历左子树
if(!T->lchild && !T->rchild) num++; //访问根结点
LeafCount2(T->rchild) ; //中序遍历右子树
}
}
//以二叉链表作为存储结构，设计算法拷贝二叉树
bitree copy(bitree T)
{bitree T1;
if(T==NULL) T1=NULL;
else
{T1=(bitree)malloc(sizeof(bitnode)); //申请结点
T1->data=T->data;
T1->lchild=copy(T->lchild);
T1->rchild=copy(T->rchild);
}
|
|
|
第2楼
return T1;
}
//以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树
bitree change(bitree T)
{
bitree t;
if(T!=NULL)
{
change(T->lchild);
change(T->rchild);
t=T->lchild;
T->lchild=T->rchild;
T->rchild=t;
}
return T;
}
void main()
{
bitree T;int n,m;
createbitree(&T);
printf("Create Success!\n\n");
while(1)
{
printf("请输入你要执行的操作:\n");
printf("0------------------------结束此次操作\n");
printf("1----------------------------先序遍历\n");
printf("2----------------------------中序遍历\n");
printf("3----------------------------后序遍历\n");
printf("4----------------------查找你要的结点\n");
printf("5---------------求此二叉排序树的深度\n");
printf("6---------求此二叉排序树的叶子结点数\n");
printf("7---------------拷贝二叉树并中序访问\n");
printf("8----交换所有结点的左右子树并中序访问\n");
scanf("%d",&n);
switch(n)
{
case 0:
return;
case 1:
printf("先序遍历为:\n");
printf("put out the diguai DLR:\n");
postorder10(T);
printf("\n");
printf("put out the not diguai DLR:\n");
postorder11(T);
printf("\n");
break;
case 2:
printf("中序遍历为:\n");
printf("put out the diguai DLR:\n");
postorder20(T);
printf("\n");
printf("put out the not diguai DLR:\n");
postorder21(T);
printf("\n");
break;
case 3:
printf("后序遍历为:\n");
printf("put out the diguai DLR:\n");
postorder30(T);
printf("\n");
printf("put out the not diguai DLR:\n");
postorder31(T);
printf("\n");
break;
case 4:
printf("请输入你要查找的结点:\n");
scanf("%d",&m);
printf("你要查找的结点为: \n");
locate(T,m);
break;
case 5:
printf("树的深度为:\n");
printf("%d\n",BinTreeDetth(T));
break;
case 6:
printf("此树的叶子结点数为:\n");
printf(" using the first way the result is:\n");
printf("%d\n",LeafCount1(T));
printf("using the second way the result is:\n");
LeafCount2(T);
printf("%d\n",num);
break;
case 7:
printf("拷贝二叉树并中序访问为:\n");
postorder21(copy(T));
printf("\n");
break;
case 8:
printf("(注意：（进行二次交换以便恢复到原来的状态）交换所有结点的左右子树并中序访问:\n");
printf("the first change is:\n");
postorder21(change(T));
printf("\n");
printf("the second change is:\n");
postorder21(change(T));
printf("\n");
break;
}
}
}
| |
