概述
二叉树为每个节点最多有两个儿子节点（左儿子节点和右儿子节点）的树。
前序遍历：根结点 ---> 左子树 ---> 右子树。
中序遍历：左子树---> 根结点 ---> 右子树。
后序遍历：左子树 ---> 右子树 ---> 根结点。
节点深度：节点ni的深度（depth）为从根到ni的唯一路径的长。根的深度为0。
节点的高：节点ni的高（height）为从ni到一片树叶的最长路径。所有的树叶（没有儿子节点的节点）的高都为0。一棵树的高等于它的根的高。
代码实现
// 二叉树的实现（C语言）// 链表，递归实现// 编译环境：visual studio 2017// 操作系统：win8.1#include#include #include typedef char Elementtype; // 定义数据类型，可根据需要自行定制typedef struct TreeNode * Node; // Node相当于struct treeNode *// 定义数节点结构typedef struct TreeNode { Elementtype Element; Node left; // 树节点的左子节点 Node right; // 树节点的右子节点}TREE,*PTREE;// 函数声明void CreatTree(PTREE *); // 树的先序创建函数void PreOrderTree(PTREE ); // 树的前序遍历函数void InOrderTree(PTREE ); // 树的中序遍历void PostOrderTree(PTREE ); // 树的后序遍历void LeafOfTree(PTREE ); // 打印树的叶子节点函数int Get_Leaf_Num(PTREE ); // 获取树叶子节点个数int Get_Height(PTREE ); // 获取树的高度// 主函数int main() { PTREE Root; printf("请先序输入二叉树的节点数据： "); CreatTree(&Root); printf("\n前序遍历结果为："); PreOrderTree(Root); printf("\n中序遍历结果为："); InOrderTree(Root); printf("\n后序遍历结果为："); PostOrderTree(Root); printf("\n打印叶子节点为："); LeafOfTree(Root); printf("\n叶子节点个数为：%d", Get_Leaf_Num(Root)); printf("\n二叉树的高度为：%d", Get_Height(Root)); printf("\n"); return 0;}// 定义树先序创建函数void CreatTree(PTREE *Root) { char val=0; // 用于下面存放数据 val=getchar(); // 输入数据值 // 如果输入'*'，则指向为空 if (val == '*') (*Root) = NULL; // 如果输入非'*'，则给数据域赋值 else { (*Root) = (PTREE)malloc(sizeof(TREE)); // 申请内存空间 if ((*Root) == NULL) { printf("创建节点失败，无法分配可用内存..."); exit(-1); } else { (*Root)->Element = val; // 给节点数据域赋值 CreatTree(&(*Root)->left); CreatTree(&(*Root)->right); } } }// 树的前序遍历函数定义void PreOrderTree(PTREE Root) { if (Root == NULL) return; else { putchar(Root->Element); PreOrderTree(Root->left); PreOrderTree(Root->right); }}// 树的中序遍历函数定义void InOrderTree(PTREE Root) { if (Root == NULL) return; else { InOrderTree(Root->left); putchar(Root->Element); InOrderTree(Root->right); }}// 树的后序遍历函数定义void PostOrderTree(PTREE Root) { if (Root==NULL) return ; else{ PostOrderTree(Root->left); PostOrderTree(Root->right); putchar( Root->Element); }}// 打印树的叶子节点函数定义void LeafOfTree(PTREE Tree) { if (Tree == NULL) return ; else { if (Tree->left == NULL&&Tree->right == NULL) putchar(Tree->Element); else { LeafOfTree(Tree->left); LeafOfTree(Tree->right); } } }// 获取树的叶子节点个数函数定义int Get_Leaf_Num(PTREE Tree) { if (Tree == NULL) return 0; if (Tree->left == NULL&&Tree->right == NULL) return 1; //递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数 return Get_Leaf_Num(Tree->left) + Get_Leaf_Num(Tree->right);}// 获取树高的函数定义int Get_Height(PTREE Tree) { int Height = 0; if (Tree == NULL) return 0; //树的高度 = max(左子树的高度，右子树的高度) + 1 else { int L_Height = Get_Height(Tree->left); int R_Height = Get_Height(Tree->right); Height = L_Height >= R_Height ? L_Height + 1 : R_Height + 1; } return Height;}
运行结果
