//二叉链表的结构定义 typedef char ElemType;//元素类型为字符类型 typedef struct BTNode { ElemType data; struct BTNode *lchild, *rchild; }BTNode; typedef struct BTNode bitree; /*函数声明从此处开始*/ //以递归方式创建二叉树（需扩展）,如输入：ABD##E##C#FHJ##K##I## bitree * CreateBTree1(); //以递归方式创建二叉树（需扩展）,如输入：ABD##E##C#FHJ##K##I## void CreateBTree2(bitree *&root); //销毁二叉树：释放动态分配的空间 void DestroyBTree(bitree *root); /*函数声明到此处结束*/ /*函数定义从此处开始*/ //以递归方式创建二叉树（需扩展）,如输入：ABD##E##C#FHJ##K##I## bitree * CreateBTree1() { bitree *root ;char ch; ch=getchar(); if (ch == '#') root = NULL; else { root=(bitree*)malloc(sizeof(bitree)); root->data=ch; root->lchild = NULL; root->rchild = NULL; root->lchild =CreateBTree1(); root->rchild= CreateBTree1(); } return root; } //以递归方式创建二叉树（需扩展）,如输入：ABD##E##C#FHJ##K##I## void CreateBTree2(bitree *&root) { char ch; ch=getchar(); if (ch == '#') root = NULL; else { root=(bitree*)malloc(sizeof(bitree)); root->data=ch; root->lchild = NULL; root->rchild = NULL; CreateBTree2(root->lchild); CreateBTree2(root->rchild); } } //销毁二叉树：释放动态分配的空间 void DestroyBTree(bitree *root) { if( root != NULL) { if (root->lchild != NULL) DestroyBTree(root->lchild); if (root->rchild != NULL) DestroyBTree(root->rchild); free(root); } }

CEG###FH##I##，表示根节点为A，A的左子树为B的子树，B的左子树为空，右子树为D的子树，D的左右子树为空，A的右子树为C的子树，C的左子树为空，右子树为E的子树，E的左右子树为空，C的右子树为F的子树，F的左子树为空，右子树为空，A到F中间不含节点（即空节点记为#） bitree *CreatBTree(); //层次遍历输出二叉树 void LevelOrder(bitree *root); //前序遍历递归版 void PreOrder_Traversal(bitree *root); //前序遍历非递归版 void Pre_Order_Traversal(bitree *root); //中序遍历递归版 void InOrder_Traversal(bitree *root); //中序遍历非递归版 void In_Order_Traversal(bitree *root); //后序遍历递归版 void PostOrder_Traversal(bitree *root); //后序遍历非递归版 void Post_Order_Traversal(bitree *root); //计算二叉树的深度 int Tree_Depth(bitree *root); //统计二叉树中叶子节点的个数 int Leaf_Count(bitree *root); //统计二叉树中节点的个数 int Node_Count(bitree *root);

以上是二叉链表的结构定义和一些常用操作函数的函数声明。其中包括以递归和非递归方式实现的前序、中序、后序遍历函数、层次遍历函数、计算二叉树深度函数、统计叶子节点个数函数和统计节点个数函数。其中，以递归方式实现的遍历函数通常使用较简单，但非递归方式实现的遍历函数能够充分发挥栈的作用，具有一定的优势。-------------------------------------------------------------------------------------------------------------------------------------------------------------

English version:

The structure definition of binary linked list is shown below:

typedef char ElemType; //Element type is character

typedef struct BTNode {
ElemType data;
struct BTNode *lchild, *rchild;
} BTNode;

typedef struct BTNode bitree;

The following functions are included in the program:

bitree *CreatBTree(); //create binary tree recursively (to be expanded)
void LevelOrder(bitree *root); //traverse binary tree in level order
void PreOrder_Traversal(bitree *root); //preorder traversal recursively
void Pre_Order_Traversal(bitree *root);//preorder traversal non-recursively
void InOrder_Traversal(bitree *root);//inorder traversal recursively
void In_Order_Traversal(bitree *root);//inorder traversal non-recursively
void PostOrder_Traversal(bitree *root);//postorder traversal recursively
void Post_Order_Traversal(bitree *root);//postorder traversal non-recursively
int Tree_Depth(bitree *root);//calculate the depth of binary tree
int Leaf_Count(bitree *root);//count the number of leaf nodes in binary tree
int Node_Count(bitree *root);//count the number of nodes in binary tree

The above functions include recursive and non-recursive versions of preorder, inorder, and postorder traversal functions, level order traversal function, function to calculate the depth of the binary tree, function to count the number of leaf nodes, and function to count the number of nodes. Recursive traversal functions are usually simpler to implement, but non-recursive traversal functions can fully utilize the stack and have certain advantages.