1、二叉链的定义
LinkBinTree.h文件
/** 二叉树结点结构 */
typedef struct _binnode
{
int data;
struct _binnode * lchild;
struct _binnode * rchild;
}BinNode;
/** 二叉树结构 *///可以定义，也可以不定义，主要使用其中的根结点
typedef struct _bintree
{
BinNode * root; //二叉树根结点
int length; //结点总数
int depth; //树的深度
}BinTree;
2、基本操作函数声明
LinkBinTree.h文件
/** 初始化二叉链 */
void InitLinkBinTree(BinTree * tree);
/** 创建二叉链*/
int CreatLinkBinTree(BinNode ** root);
/** 先序遍历 */
void PreOrderTraverse(BinNode * root);
/** 中序遍历 */
void InOrderTraverse(BinNode * root);
/** 后序遍历 */
void PostOrderTraverse(BinNode * root);
/** 层序遍历 */
void ZOrderTraverse(BinNode * root);
/** 二叉树的深度 */
int BinTreeDepth(BinNode * root);
/** 二叉树结点数量 */
int BinTreeNodeNumber(BinNode * root);
/** 二叉树叶结点数量 */
int BinTreeLeafNodeNumber(BinNode * root);
3、实现操作函数
LinkBinTree.c文件
1、初始化二叉树
void InitLinkBinTree(BinTree * tree)
{
tree->root = NULL;
tree->depth = 0;
tree->length = 0;
}
2、创建二叉树
创建二叉树大概分为4步：
<1>、接收用户输入数据
<2>、判断用户输入数据，是否结束当前子树的创建
<3>、如果输入0就返回上一层，反之为该结点分配空间，并存储输入数据
<4>、然后递归调用，构建结点的左右子树，重复上述操作
在创建二叉链时，需要在子函数里面为结点分配空间，那么函数传参时，就需要传入结点指针的地址
！！重点 ！！
因为在主函数定义一个树结点时，就只是一个结点指针(BinNode * tree)，结点指针并没有在堆中被分配空间，所以在创建二叉链函数中就需要为结点分配空间，但是在子函数如果要操作一个变量，那么就需要传入这个变量的地址，所以函数参数需要传入结点指针的指针，也就是结点指针的地址
int CreatLinkBinTree(BinNode ** root)
{
int input;
scanf("%d",&input);
if(input == 0)
{
*root = NULL;
return 0;
}
else
{
*root = (BinNode *)malloc(sizeof(BinNode));
if(!root)
printf("Creat Fail!\n");
(*root)->data = input;
CreatLinkBinTree(&((*root)->lchild)); //构建左子树
CreatLinkBinTree(&((*root)->rchild)); //构建右子树
}
}
3、遍历
详细的遍历方式
4、二叉树的深度
分别递归根结点的左右孩子结点，比较左右子树深度，最后深度大的+1(根结点)就为树的深度
int BinTreeDepth(BinNode * root)
{
if(root == NULL)
return 0;
int maxLeft = BinTreeDepth(root->lchild);
int maxRight = BinTreeDepth(root->rchild);
if(maxLeft > maxRight)
return maxLeft + 1;
else
return maxRight + 1;
}
5、二叉树总结点数量
还是递归左右孩子结点，左右子树结点之和+1(根结点)，就为树总结点数量
int BinTreeNodeNumber(BinNode * root)
{
if(root == NULL)
return 0;
return BinTreeNodeNumber(root->lchild) + BinTreeNodeNumber(root->rchild) + 1;
}
6、二叉树叶结点数量
递归左右孩子结点，遇到度为0的返回1，最后将左右子树度为0的数量相加，就为叶结点数量
int BinTreeLeafNodeNumber(BinNode * root)
{
if(root == NULL)
return 0;
if(root->lchild == NULL && root->rchild == NULL)
return 1;
else
return BinTreeLeafNodeNumber(root->lchild) + BinTreeLeafNodeNumber(root->rchild);
}
总之，无论是创建、遍历还是结点数量的统计，都与递归密不可分，代码简单，但理解还是需要多下功夫！！
