二叉树
树是一种多对一的树状结构。
1.二叉树的建立：
#include<stdio.h>
#include<malloc.h>
struct tree
{
char data;
struct tree *lchild,*rchild;//左孩子指针和右孩子指针
} node;
这是树的大致结构。左右指针域指向左右两个孩子的值。
void createtree(struct tree **P)//传递的指针要在此过程中发生改变
{
char ch;
scanf("%c",&ch);
if(ch=='#')
(*P)=NULL;
else
{
(*P)=(struct tree*)malloc(sizeof(node));
(*P)->data=ch;
createtree(&(*P)->lchild);//先序建立，先坐后右
createtree(&(*P)->rchild);
}
}
变量传递如果要更改那个变量的话要将它的指针传递到下一个函数，对于指针也是一样的，所以上面代码的传递就有了**P这样的存在。
2.二叉树的遍历
二叉树的遍历有四种，第一种为先序遍历：
void Xrintftree(BiTree T)
{
if(T==NULL)
return ;
printf("%c",T->data);
Zrintftree(T->lchild);
Zrintftree(T->rchild);
}
第二种为中序
void Zrintftree(BiTree T)
{
if(T==NULL)
return ;
Zrintftree(T->lchild);
printf("%c",T->data);
Zrintftree(T->rchild);
}
第三种为后序
void Hrintftree(BiTree T)
{
if(T==NULL)
return;
Hrintftree(T->lchild);
Hrintftree(T->rchild);
printf("%c",T->data);
}
最后一种是层次遍历
void crintftree(BiTree T)
{
if (T==NULL)
return;
BiTree s[5000];
s[0]=T;
int j=0,k=1;
while (j<k)
{
printf("%c",s[j]->data);
if (s[j]->lchild)
s[k++]=s[j]->lchild;
if (s[j]->rchild)
s[k++]=s[j]->rchild;
j++;
}
}