二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
二叉树的建立需要用到结构体:
typedef struct BiTNode
{
char data;
struct BiTNode *leftChild,*rightChild;
}BiTNode,*BiTree;
这里我用递推进行建立二叉树:
BiTree Create(BiTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->leftChild=Create(T->leftChild);
T->rightChild=Create(T->rightChild);
}
return T;
}
二叉树的遍历有三种方式:
DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。
先根次序遍历:
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->leftChild);
Preorder(T->rightChild);
}
}
中根次序遍历:
void zhongxu(BiTree T)
{
if(T)
{
zhongxu(T->leftChild);
printf("%c",T->data);
zhongxu(T->rightChild);
}
}
后根次序遍历:
void houxu(BiTree T)
{
if(T)
{
houxu(T->leftChild);
houxu(T->rightChild);
printf("%c",T->data);
}
}
然后树的深度:
int Depth(BiTree T)
{
int dep=0,depl,depr;
if(!T) dep=0;
else
{
depl=Depth(T->leftChild);
depr=Depth(T->rightChild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
还有树的节点:
int Sumleaf(BiTree T)
{
int sum=0,m,n;
if(T)
{
if((!T->leftChild)&&(!T->rightChild))
sum++;
m=Sumleaf(T->leftChild);
sum+=m;
n=Sumleaf(T->rightChild);
sum+=n;
}
return sum;
}
完整代码:
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define NULL 0
typedef struct BiTNode
{
char data;
struct BiTNode *leftChild,*rightChild;
}BiTNode,*BiTree;
BiTree Create(BiTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->leftChild=Create(T->leftChild);
T->rightChild=Create(T->rightChild);
}
return T;
}
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->leftChild);
Preorder(T->rightChild);
}
}
int Sumleaf(BiTree T)
{
int sum=0,m,n;
if(T)
{
if((!T->leftChild)&&(!T->rightChild))
sum++;
m=Sumleaf(T->leftChild);
sum+=m;
n=Sumleaf(T->rightChild);
sum+=n;
}
return sum;
}
void zhongxu(BiTree T)
{
if(T)
{
zhongxu(T->leftChild);
printf("%c",T->data);
zhongxu(T->rightChild);
}
}
void houxu(BiTree T)
{
if(T)
{
houxu(T->leftChild);
houxu(T->rightChild);
printf("%c",T->data);
}
}
int Depth(BiTree T)
{
int dep=0,depl,depr;
if(!T) dep=0;
else
{
depl=Depth(T->leftChild);
depr=Depth(T->rightChild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
int main()
{
BiTree T;
int sum,dep;
T=Create(T);
Preorder(T);
printf("\n\n");
zhongxu(T);
printf("\n\n");
houxu(T);
printf("\n\n");
sum=Sumleaf(T);
printf("sum=%d",sum);
dep=Depth(T);
printf("\ndep=%d\n",dep);
return 0;
}
例如输入序列ABC##DE#G##F###(其中的“#”表示空,并且输入过程中不要加回车,因为回车也有对应的ASCII码,是要算字符的,但是输入 完之后可以按回车退出),这时候就能够看到结果了。
0