1.概念
树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树。
严蔚敏．数据结构（C语言版）：清华大学出版社，1997-4-1
2.定义
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
*图中的树由结点的有限集T={A，B，C，D，E，F，G，H，I，J}所构成，
其中A是根结点，T中其余结点可分成三个互不相交的子集：
T1={B，E，F，I，J}， T2={C}， T3={D，G，H}。即T(A(B(E,F(I,J)),C,D(G,H)))*
3.基本术语
结点的度(Degree)：树中的一个结点拥有的子树数目。如：A结点的度为3
树的度：是指该树中结点的最大度数。如树T的度为3。
叶子结点(Leaf)或终端结点：度为零的结点。如：E I J C G H都是叶子结点
分支结点或非终端结点：度不为零的结点。如：A B F D都是分支结点
孩子结点或儿子：树中某个结点的子树之根。如A的孩子结点为B、C、D
双亲结点或父亲：孩子结点的上层结点。如B的双亲结点为A，J的父亲为F
兄弟结点(Sibling)：同一个双亲的孩子。如B C D为兄弟结点，E F为兄弟结点
结点的层数(Level)：从根起算，根的层数为1，它的孩子的层数为2……若某结点在第i层，它的孩子结点就在第i+1层。如A的层数为1、BCD的层数为2、IJ的层数为4
树的高度(Height)或深度(Depth)：树中结点的最大层数。如树T的高度为4
有序树(OrderedTree)：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，二叉树就是典型的有序树。
4.应用
树最常见的于我们的文件系统目录的实现，就是一个典型的树，此外还在系统内存管理、数据库建模等领域应用。
5.二叉树
二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
*(a) 为空树
(b) 为仅有一个结点的二叉树，
(c) 是仅有左子树而右子树为空的二叉树，
(d) 是仅有右子树而左子树为空的二叉树，
(e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 6.3(c) 与图 6.3(d) 就是两棵不同的二叉树。*
1 二叉树第n层上的结点数目最多为2^(n-1);(n≥1)。
2 深度为n的二叉树至多有2^n-1个结点(n≥1)。
满二叉树
满二叉树，在一棵深度为n的满二叉树，有2^n-1个结点。 完全二叉树，若一棵深度为n的二叉树，其前n-1层是一个棵满二叉树， 而第n层的结点都集中在该层最左边的若干位置上。6.C语言实现
//树的基本实现
/*树的结构如下: A / \ B C / \ / D E F / / \ G H I / J */
#include <stdio.h>
#include <malloc.h>
#define N 10 /* 定义树的结点个数 */
typedef char DATATYPE; /* 数据类型重定义 */
typedef struct tagBTNODE
{
DATATYPE ch;
struct tagBTNODE *lChild;
struct tagBTNODE *rChild;
}BTNODE;
/* 上下对应，下面等位置的为上面的父结点，我们把根节点的父结点定为0 */
DATATYPE elemArray[N] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
DATATYPE elemRelationArray[N] = { 0, 'A', 'A', 'B', 'B', 'C', 'E', 'F', 'F', 'G'};
//函数声明
BTNODE * GetNodeParent(DATATYPE elem, BTNODE** pElemArray, int sizeofpElemArray);
//创建树
//创建树的算法：
//1、建立离散的树节点
//2、利用上下级关系将树节点进行链接
BTNODE * CreateTree()
{
BTNODE *pElem[N]; /* 用于保存N个树节点 */
BTNODE *pParent; /* 保存父节点 */
BTNODE *pRoot; /* 树根节点 */
int i = 0;
for(i = 0; i < sizeof(elemArray) / sizeof(DATATYPE); i++) //创建N个离散的节点
{
pElem[i] = (BTNODE *)malloc(sizeof(BTNODE)); /* 动态的创建树节点 */
pElem[i]->ch = elemArray[i]; /* 为每一个```````树节点赋值 */
pElem[i]->lChild = NULL; /* 初始时每一个树节点的左右孩子为空 */
pElem[i]->rChild = NULL;
}
/* 为每一个节点找父节点 */
for(i = 0; i < sizeof(elemArray) / sizeof(DATATYPE); i++)
{
pParent = GetNodeParent(pElem[i]->ch, pElem, N); //找到每个节点的父节点，将离散的节点连接起来
if(pParent == NULL) //如果为NULL，则表示它找不到父节点，即是根节点
{
pRoot = pElem[i];
}
else if(pParent->lChild == NULL) /* 如果父节点的左子树为空，挂在左边 */
{
pParent->lChild = pElem[i];
}
else if(pParent->rChild == NULL) /* 如果父节点的左子树不为空，挂在右边 */
{
pParent->rChild = pElem[i];
}
}
return pRoot;
}
/* 函数功能：查找输入节点的父节点 形参：elem -- 节点的数据域 pElemArray -- 输入要查找的节点 sizeofpElemArray -- 节点总个数 返回值：返回输入节点的父节点地址 */
BTNODE * GetNodeParent(DATATYPE elem, BTNODE** pElemArray, int sizeofpElemArray)
{
int i = 0;
int j = 0;
for(i = 0; i < sizeofpElemArray; i++)
{
if(elem == elemArray[i]) /* 先找到该节点对应的elemArray的位置i，获得与之对应位置上的elemRelationArray[i] */
{
for(j = 0; j < sizeofpElemArray; j++)
{/* 遍历整个elemArray，找与elemRelationArray[i]相等的即为pElem[i]的父节点 */
if(elemRelationArray[i] == pElemArray[j]->ch)
return pElemArray[j];
}
}
}
return NULL; /* 如果没有找到，说明是根节点 */
}
//先根遍历 (根-->左-->右)
/*算法 1、 根左右 前序遍历(先根遍历) AB(DE)C(F) void POrder(根) //递归调用 { if (根节点是空) return; 打印 根节点 POrder(左节点) POrder(右节点) } */
void PrintByFirstRoot(BTNODE *pRoot)
{
if(pRoot == NULL) return ;
printf("%c ",pRoot->ch); //先输出节点
PrintByFirstRoot(pRoot->lChild); //遍历左孩子
PrintByFirstRoot(pRoot->rChild); //遍历右孩子
}
//中根遍历 (左-->根-->右)
/*算法 2、 左根右 中序遍历(中根遍历) (D)B(E)A(F)C void MOrder(根) //递归调用 { if (根节点是空) return; MOrder(左节点) 打印 根节点 MOrder(右节点) } */
void PrintByMiddleRoot(BTNODE *pRoot)
{
if(pRoot == NULL) return ;
PrintByMiddleRoot(pRoot->lChild); //先遍历左孩子
printf("%c ",pRoot->ch); //输出节点
PrintByMiddleRoot(pRoot->rChild); //遍历右孩子
}
//后根遍历 (左-->右-->根)
/*算法 3、 左右根 后序遍历(后根遍历) (DE)B(F)CA void BOrder(根) //递归调用 { if (根节点是空) return; BOrder(左节点) BOrder(右节点) 打印 根节点 } */
void PrintByLastRoot(BTNODE *pRoot)
{
if(pRoot == NULL) return ;
PrintByLastRoot(pRoot->lChild); //遍历左孩子
PrintByLastRoot(pRoot->rChild); //遍历右孩子
printf("%c ",pRoot->ch); //输出节点
}
//计算树的深度
/* 普通算法思想如下： 1、初始深度为0 2、每经历一个节点，深度＋1 3、直到第一个树叶 4、将深度保存下来做为最大深度 5、每返回一次，深度－1 6、直到再一个树叶 7、判断现在的深度跟最大深度，如果大于最大深度，则替换最大深度 8、循环直到遍历完毕 */
//求二叉树的深度（高度）
//算法如下：
//(1) 若二叉树为空，则高度为0；
//(2) 若二叉树不为空，则高度应为其左、右子树高度的最大值加上1
int BiTreeDepth(BTNODE * pRoot)
{
int lH = 0; //记录左边遍历的最大深度
int rH = 0; //记录右边遍历的最大深度
int max = 0; //比较左右，取大的那个再加上根节点的一个
if(pRoot == NULL) return 0;
lH = BiTreeDepth(pRoot->lChild); //遍历左边
rH = BiTreeDepth(pRoot->rChild); //遍历右边
max = lH > rH ? lH : rH;
return (max + 1); //加1表示根节点
}
//或C++中：
/* int BiTreeDepth(BTNODE * pRoot) { if(pRoot == NULL) return 0; int lH = BiTreeDepth(pRoot->lChild); //遍历左边, 记录左边遍历的最大深度 int rH = BiTreeDepth(pRoot->rChild); //遍历右边, 记录右边遍历的最大深度 int max = lH > rH ? lH : rH; //比较左右，取大的那个再加上根节点的一个 return (max + 1); //加1表示根节点 } */
//求二叉树节点的个数
//计算节点数
/* 算法思想如下： 1、初始节点为0 2、每经历一个节点，个数＋1 */
int NodeCount = 0;//1、初始节点为0
int CountNode(BTNODE * pRoot)
{
if (pRoot == 0) return 0;
//2、每经历一个节点，个数＋1
NodeCount++;
CountNode(pRoot->lChild);
CountNode(pRoot->rChild);
return NodeCount;
}
//或者
/* int CountNode(BTNODE * pRoot) { int NodeCount = 0; if(pRoot == 0) return 0; NodeCount++; NodeCount += CountNode(pRoot->lChild); NodeCount += CountNode(pRoot->rChild); return NodeCount; } */
void main()
{
BTNODE *pRoot = CreateTree();
//先根遍历
printf("先根遍历:");
PrintByFirstRoot(pRoot);
printf("\n");
//中根遍历
printf("中根遍历:");
PrintByMiddleRoot(pRoot);
printf("\n");
//后根遍历
printf("后根遍历:");
PrintByLastRoot(pRoot);
printf("\n");
printf("树的深度为:%d\n",BiTreeDepth(pRoot));
printf("树的节点总数为:%d\n",CountNode(pRoot));
}备注
所谓二叉树的遍历是指按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次并且仅被访问一次。
