我在前面的博客中解说了链表、栈和队列。这些数据结构事实上都是线性表，而且给出了具体的实现。
从今天開始。我们将要来学习树，树作为一种数据结构我们常常会用到，作为起步和基础。我们先来实现二叉树。也就是每一个节点有不超过2个子节点的树。对于树的操作，最主要的创建、遍历、求树高、节点数等。代码上传至 /chenyufeng1991/BinaryTree。
(1)节点的定义
typedef struct BTNode{
int data;
struct BTNode *lChild;
struct BTNode *rChild;
}BiTNode;
(2)二叉树的创建
//先序创建二叉树
int CreateBiTree(BiTNode **T)
{
int ch;
scanf("%d",&ch);
if (ch == -1)
{
*T = NULL;
return 0;
}
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode));
if (T == NULL)
{
printf("failed
");
return 0;
}
else
{
(*T)->data = ch;
printf("输入%d的左子节点：",ch);
CreateBiTree(&((*T)->lChild));
printf("输入%d的右子节点：",ch);
CreateBiTree((&(*T)->rChild));
}
}
return 1;
}
(3)先序遍历二叉树
//先序遍历二叉树
void PreOrderBiTree(BiTNode *T)
{
if (T == NULL)
{
return;
}
else
{
printf("%d ",T->data);
PreOrderBiTree(T->lChild);
PreOrderBiTree(T->rChild);
}
}
(4)中序遍历二叉树
//中序遍历二叉树
void MiddleOrderBiTree(BiTNode *T)
{
if (T == NULL)
{
return;
}
else
{
MiddleOrderBiTree(T->lChild);
printf("%d ",T->data);
MiddleOrderBiTree(T->rChild);
}
}
(5)兴许遍历二叉树
//兴许遍历二叉树
void PostOrderBiTree(BiTNode *T)
{
if (T == NULL)
{
return;
}
else
{
PostOrderBiTree(T->lChild);
PostOrderBiTree(T->rChild);
printf("%d ",T->data);
}
}
(6)二叉树的深度
//二叉树的深度
int TreeDeep(BiTNode *T)
{
int deep = 0;
if (T != NULL)
{
int leftdeep = TreeDeep(T->lChild);
int rightdeep = TreeDeep(T->rChild);
deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
(7)叶子节点个数
//叶子节点个数
int LeafCount(BiTNode *T)
{
static int count;
if (T != NULL)
{
if (T->lChild == NULL && T->rChild == NULL)
{
count++;
}
LeafCount(T->lChild);
LeafCount(T->rChild);
}
return count;
}
(8)測试函数
//主函数
int main(int argc,const char *argv[])
{
BiTNode *T;
int depth,leafCount = 0;
printf("请输入第一个节点的值，-1表示没有叶节点：
");
CreateBiTree(&T);
printf("先序遍历二叉树：");
PreOrderBiTree(T);
printf("
");
printf("中序遍历二叉树：");
MiddleOrderBiTree(T);
printf("
");
printf("兴许遍历二叉树：");
PostOrderBiTree(T);
printf("
");
depth = TreeDeep(T);
printf("树的深度为：%d
",depth);
leafCount = LeafCount(T);
printf("叶子节点个数:%d
",leafCount);
return 0;
}
如果觉得《用c语言编译二叉树 C语言实现二叉树的基本操作》对你有帮助，请点赞、收藏，并留下你的观点哦！
