树的一些基本特点
树的结点：
包括一个数据元素，和从这个元素，指向其各个子树的分支（但不包括指向其父树的分支）。结点拥有的子树数，称为结点的度（Degree），度为 0 的结点，称为叶结点（Leaf）或终端节点；度不为 0 的结点，称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度为树内各节点的度的最大值。
度：节点的子树个数；
树的度：树中任意节点的度的最大值；
兄弟：两节点的 parent 相同；
层：根在第一层，以此类推；
高度：叶子节点的高度为 1，根节点高度最高；
有序树：树中各个节点是有次序的；
森林：多个树组成
树的存储结构
- 双亲表示法:（自下往上）
- 孩子表示法：（自下往下）
- 双亲表示法：以双亲作为索引的关键词的一种存储方式（可以双向）
结构设计的代码可以如下所示：
#define MAX_REE_SIZE //孩子结点的数据 typedef struct CTNode { int ChildPos; //孩子结点的下标 struct CTNode *next; //指向下一个孩子的指针 }*ChildPtr; //表头 typedef struct { int data; //存放在树中结点的数据 int Parent Pos; //存放双亲的下标 ChildPtr Child; //指向第一个孩子的指针 }Parent； //数结构 typedef struct { Parent Node[MAX_TREE_SZIE]; //结点数组 int NodeNum; //结点数 int RootPos; //根的位置 }Tree；
二叉树(Binary Tree)
定义：
二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2i-1 个结点；深度为 k 的二叉树至多有 2k 个结点。
以下是二叉树的特点：
- 在非空二叉树中，第 i 层的结点总数不超过 2i-1, i>=1;
- 深度为 h 的二叉树最多有 2h-1 个结点(h>=1)，最少有 h 个结点;
- 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
- 具有 n 个结点的完全二叉树的深度为 log2(n+1);
- 有 N 个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若 I 为结点编号则 如果 I>1，则其父结点的编号为 I/2；
如果 2I<=N，则其左儿子（即左子树的根结点）的编号为 2I；若 2I>N，则无左儿子；
如果 2I+1<=N，则其右儿子的结点编号为 2I+1；若 2I+1>N，则无右儿子。
- 给定N个节点，能构成h(N)种不同的二叉树，其中h(N)为卡特兰数的第N项，h(n)=C(2*n,n)/(n+1)。
- 设有 i 个枝点，I 为所有枝点的道路长度总和，J 为叶的道路长度总和 J=I+2i。
满二叉树与完全二叉树
- 完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
- 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
二叉树的结构设计
typedef struct BiTNode { char data; //存储的数据 struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode, *BiTress;
树的遍历
所谓树的遍历，是指对树中所有结点的信息的访问。
其重点有 2 个：
①对所有结点进行访问（假如有结点没有被访问，肯定算不上遍历了）
②对每个结点只访问一次；
二叉树的遍历方法主要有三种：
①前序遍历（访问根结点——》访问左子树——》访问右子树）
②后序遍历（访问左子树——》访问右子树——》访问根结点）
③中序遍历（先访问左子树——》再访问根——》再访问右子树）
例子：
其前序遍历为：ABDHIECFJKG
其中序遍历为：HDIBEAJFKCG
其后序遍历为：HJDEBJKFGCA
如何根据前序中序遍历写出后序遍历，或者根据后中序遍历写出前序遍历？
可以点击这里：链接
以下的二叉树创建遍历节点高度复制计算的分析代码，也可以忽略直接看总代码：
总代码链接，点这里
前序创建和遍历树例子：
其中前中后创建一棵树只是顺序有所不同，树的遍历显示也是同样如此，稍加修改便可。
typedef struct Tree { char data; struct Tree *lchild, *rchild; }Tree; Tree* FrontCreateTree() //前序创建一棵树 { char c; Tree *T; scanf("%c",&c); if(' ' == c) T = NULL; else { T = (Tree *)malloc(sizeof(Tree)); T->data = c; T->lchild = FrontCreateTree(); T->rchild = FrontCreateTree(); } return T; } Tree* FrontCreateTree() //后序创建一棵树 { char c; Tree *T; scanf("%c",&c); if(' ' == c) T = NULL; else { T = (Tree *)malloc(sizeof(Tree)); T->lchild = FrontCreateTree(); T->data = c; T->rchild = FrontCreateTree(); } return T; } Tree* FrontCreateTree() //前序创建一棵树 { char c; Tree *T; scanf("%c",&c); if(' ' == c) T = NULL; else { T = (Tree *)malloc(sizeof(Tree)); T->lchild = FrontCreateTree(); T->rchild = FrontCreateTree(); T->data = c; } return T; }
前序遍历：
void FrontShowTree(Tree *T) { if( T ) { printf("%c",T->data); FrontShowTree(T->lchild); FrontShowTree(T->rchild); } }
中序遍历：
void MiddleShowTree(Tree *T) { if( T ) { FrontShowTree(T->lchild); printf("%c",T->data); FrontShowTree(T->rchild); } }
后续遍历：
void LastShowTree(Tree *T) { if( T ) { FrontShowTree(T->lchild); FrontShowTree(T->rchild); printf("%c",T->data); } }
测试代码如下：
int main() { Tree* T = FrontCreateTree(); FrontShowTree(T); return 0; }
测试结果如下：
计算树节点个数：
//计算结点个数,与遍历类似 int count = 0; //全局变量 void CountTreeNode(Tree *T) //通过中序遍历计算 { if (tree) { count += 1; //计数 CountTree(tree->lchild); CountTree(tree->rchild); } }
复制一棵二叉树
思路：
这个就和创建二叉树的思路差不多，只不过将需要你输入权值那个步骤，变成了直接从另外一颗树上获取权值。
//复制二叉树 Tree *CopyBinaryTree(Tree *T) { if(T) { Tree *NewTree = (Tree* )malloc(sizeof(Tree)); NewTree->data = T->data; NewTree->lchild = CopyBinaryTree(T->lchild); //复制左子树 NewTree->rchild = CopyBinaryTree(T->rchild); //复制右子树 return NewTree; } else return NULL; }
计算树的高度
代码如下：
int DepTreeHeight(Tree *T) { int LeftTreeHight = 0, RightTreeHight = 0; if(T == NULL) return 0; else { LeftTreeHight = DepTreeHeight(T->lchild); RightTreeHight = DepTreeHeight(T->rchild); if( LeftTreeHight > RightTreeHight ) return LeftTreeHight + 1; else return RightTreeHight + 1; } }
例子：
分析如下：
- 首先，程序一直的递归，执行到D处，对D进行分析，由于D左子树为空，dl=0；D右子树也为空，dr=0；所以直接进行比较，返回dr+1，也就是返回1给b的左子树。
- 此时B的左子树为1，接下来进行B的有子树遍历。同样的，到了E处，E的左子树为空，El=0；E的右子树不为空，继续执行；
- 但是E的右子树左右均为空，所以Gl=0，Gr=0，返回Gr+1，也就是返回了1。
- 此时回到了E处，由于E的左子树为空直接返回0，而右子树返回了1，接下来进行比较，由于Er>El，所以返回Er+1，也就是返回了2到B处。
- 此时回到了B处，由于B的左子树为1，而右子树为2，由于Br>Bl，所以返回Br+1，也就是返回了3回到了A处。
- 此时回到了A，届时A的左子树全部遍历完成，Al = 3，接下来遍历A的右子树。此时来分析C，由于C的左子树为空，所以直接返回0，而C的有子树非空，继续判断。
- 此时来到F出，由于F左右子树均为空，所以Fl = Fr = 0，所以返回Fr+1，也就是返回1回到C处，所以Cr = 1.
- 此时回到C，对C的左右子树进行比较，Cl = 0，Cr =1，所以返回Cr+1，也就是返回了2到A的右子树。
- 此时回到A，届时A的左子树Al = 3，而Ar = 2，所以返回Al + 1，也就是返回了4.
- 最终的结果是4.
统计每层结点个数
思路：
定义一个数组，LevNum[1]保存第一层所以结点个数，LevNum[2]保存第二层所有结点个数。
代码如下：
//每层结点个数 void CountStateNode(Tree *T, int level, int *levelbuf) { if( T ) { levelbuf[level]++; CountStateNode(T->lchild,level + 1,levelbuf); CountStateNode(T->rchild,level + 1,levelbuf); } }
避免篇幅过长，总代码链接如下：点这里
参考链接：http://blog.csdn.net/jopus/article/details/19109495
