目录
树的基本性质
节点的度：该节点拥有的孩子个数
叶子节点：度为0的节点
层数：根节点为第一层，根的子节点为第二层，以此类推
所有树的性质：所有节点的总度数等于节点数减一
完全m 叉树性质
完全m 叉树，节点的度数最大为m ，且必须按照从上到下从左到右的顺序依次填满，叶子节点只出现在倒数第一层和倒数第二层。
常用性质如下
(1)第i 层最多拥有的节点个数为
(2)d 层的完全m 叉树最多拥有的节点个数为
假设完全m 叉树有n 个节点
(3) n 个结点的完全m 叉树的深度为
, ceil 表示向上取整
(4) 当i<d 时，第i 层节点个数为
第d 层的节点个数为
(5)在满m 叉树中，一个编号为p 的结点(编号从1开始)，它的深度是
，它的父节点编号为
，易得该结点的第k-1 个孩子的编号为p*k ，所以推导出该结点的第i 个孩子的编号为
(6)对于n 个结点的二叉树，按从上到下，从左到右依次给结点编号
i 的双亲结点为i//2 ，若n<2i ，则i 是叶子结点，若n≥2i ，则其左孩子为2i ，若n≥2i+1 ，则其右孩子是结点2i+1 ,若n<2i+1 ，则其无左孩子
(7) n 个结点的不同二叉树有
种
二叉树
定义树结点结构体
typedef struct BiNode{
char data; //数据域
struct BiNode *lchild; //定义lchild变量为指向Node结构体的指针，指向左子树根结点
struct BiNode *rchild; //rchild指向右子树根结点
}BiNode;
建树
根据二叉树的层次遍历建树
空的结点用#表示
BiNode *CreateTree(char a[], int size, int index){
if(index >= size || a[index] == '#') //如果下标超过或者本来该结点为空
return NULL;
BiNode *node = (BiNode* )malloc(sizeof(BiNode));//给node结点分配对应Node结构体的内存空间，然后将malloc返回的指针转换成Node
node->data = a[index];
node->lchild = CreateTree(a, size, 2*index+1); //创建node结点的左子树
node->rchild = CreateTree(a, size, 2*index+2); //创建node结点的右子树
//数组下标从0开始，所以2i+1是左孩子，2i+2是右孩子
//如果是从1开始的话，2i是左孩子，2i+1是右孩子
return node;
}
主函数调用
int n[]={'A','B','C','#','D' ,'E','#','F'};
//二叉树结点的数组表示，#表示该结点为空
BiNode *tree=CreateTree(n, 8 , 0); //创建二叉树tree，该树实质是一个结点，该结点直接或间接指向其它结点
根据前序或后序建树
已知二叉树的前序或后序或中序其中一个，其中空的节点要特别指出来，不然无法唯一确定一个树
例如先序为ABC##DE#G##F###
根节点是 A。接下来是 B，是 A 的左子节点。接下来是 C，是 B 的左子节点。两个 #，表明 C 的左右子节点为空。接下来是 D，是 B 的右子节点。接下来是 E，是 D 的左子节点。一个 #，表明 E 的左子节点为空。接下来是 G，是 E 的右子节点。两个 #，表明 G 的左右子节点为空。接下来是 F，是 D 的右子节点。三个 #，表明 F 的左右子节点以及 D 的右子节点为空。
已知前序序列a[]建树
BiNode *CreateTree(char a[],int size) {
if (i>=size)
return NULL;
if (a[i] == '#'){
i++;
return NULL;
}
BiNode *node = (BiNode*)malloc(sizeof(BiNode));
//malloc先新生成一个BiNode结点，然后用(BiNode*)强制转换为指向BiNode类型的指针
//根左右
node->data = a[i++];
node->lchild = CreateTree(a,size);
node->rchild = CreateTree(a,size);
return node;
}
ps：只知道中序是不能唯一确定一个树的
遍历二叉树
前序遍历
void PreOrder(BiNode* root){//先序遍历，根左右
if(root==NULL)
return;
printf("%c ",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
中序遍历
void InOrder(BiNode* root){//中序遍历，左根右
if(root==NULL)
return;
InOrder(root->lchild);
printf("%c ",root->data);
InOrder(root->rchild);
}
后序遍历
void PostOrder(BiNode* root){//后序遍历，左右根
if(root==NULL)
return;
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c ",root->data);
}
根据前序和中序序列输出后序序列
//全局变量
char pre[100] //前序序列
char in[100]; //后序序列
void build(int root,int start,int end){
if(start>end)
return;
int i=start;
while(in[i]!=pre[root])
i++;
build(root+1,start,i-1);
build(root+i-start+1,i+1,end);
printf("%c",pre[root]);
}
//主函数调用
build(0,0,strlen(pre)-1);
例如
先序：A B C D E F G H I J
中序：C D B F E A I H G J
一开始pre[root]是A，遍历in找到A，i指向A停下，这时A左右有两部分，CDBFE为左子树，范围为start到i-1，由先序序列得该树根为B，即root+1。IHGJ为右子树，范围为i+1到end，由先序序列得该树根为G，即root+i-start+1，依次类推。
根据后序和中序序列输出前序序列
同理可以根据后序和中序序列输出前序序列
// 全局变量
char post[100]; // 后序序列
char in[100]; // 中序序列
void build(int root, int start, int end) {
if (start > end)
return;
// 在中序序列中找到根节点的位置
int i = start;
while (in[i] != post[root])
i++;
// 根节点在前序序列中的位置
printf("%c", post[root]);
// 递归构建左子树和右子树
// 左子树的根节点在后序序列中的位置是 root - (end - i) - 1
build(root - (end - i) - 1, start, i - 1);
// 右子树的根节点在后序序列中的位置是 root - 1
build(root - 1, i + 1, end);
}
根据前序和后序判断树的个数
知道前序和后序是无法唯一确定一个树的，但是可以知道这样的树有多少个，如果一个结点只有一个孩子，那么这个孩子可以是它的左孩子或右孩子，如果这样的结点有n个，则树有2^n个
先定义一个寻找索引函数，用于返回一个数在数组的索引
int findIndex(char arr[], int size, int value) {
for (int i=0; i<size; i++){
if (arr[i]==value){
return i;
}
}
return -1;
}
有这样的性质：对于一个结点，它在后序的索引为Index，它的先序下一个结点在后序的索引为Indexnext，如果Indexnext=Index，则该结点只有一个孩子
计算只有一个孩子节结点有多少个
int fun(char pre[], char post[], int size) {
int count = 0;
int i;
for (i=0; i<size-1; i++) {//最后一个节点没有下一个节点，所以不用检查
int PreIndex=findIndex(post,size,pre[i]);
int nextPreIndex=findIndex(post,size,pre[i+1]);
if (PreIndex==nextPreIndex+1){
count++;
}
return count
}
最后输出2^count次方就是答案
求树的高度(DFS)
res参数保存当前的高度，如果大于deepth就让deepth等于res，最后deepth就会是最大高度
void dfs(BiNode *root,int res){
if(root==NULL)
return;
res=res+1;
if(root->lchild==NULL && root->rchild==NULL){
if(res>deepth)
deepth=res; // deepth是全局变量
}
dfs(root->lchild,res); //递归左子树
dfs(root->rchild,res); //递归右子树
}
//主函数调用
char a[]={'A','B','C','D','#','E','F','#','G'};
BiNode *root;
root=CreateTree(a,9,0); //根据层次遍历建树
dfs(root,0); //从0开始
求树的宽度
树的宽度是一层中结点数的最大值，定义一个nodenum数组用来存每层的结点数量，nodenum[i]的值表示第i+1层的结点数
void dfs(BiNode *root,int nodenum[],int h){
if(root!=NULL){
nodenum[h]++; //nodenum[]是全局变量
dfs(root->lchild,nodenum,h+1);
dfs(root->rchild,nodenum,h+1);
}
}
最后输出 nodenum数组的最大值就是树的宽度
求树的叶子结点个数
简单的dfs
void dfs(BiNode *root){
if(root==NULL)
return;
if(root->lchild==NULL && root->rchild==NULL)//如果左孩子和右孩子都为空则为叶子结点
leaf++; //leaf是全局变量
dfs(root->lchild);
dfs(root->rchild);
}
哈夫曼树
求哈夫曼树的WPL(带权路径长度)
例如有五个结点，它们的权值分别为1 2 2 5 9
先对所有结点进行降序排序9 5 2 2 1
选最后两个数即最小的两个数，记录它们和为3，然后加到总和WPL，把倒数第二个数赋值为3
即9 5 2 3 1，最后一个数不用管，即9 5 2 3，然后再进行降序排序，依次类推，需要n-1轮
int WPL=0;
for(i=n-1;i>0;i--){
Sort(a,i+1); //降序排序，对前i+1个数进行排序
WPL=WPL+a[i]+a[i-1];
a[i-1]=a[i]+a[i-1];
}
printf("%d\n",WPL);
Sort函数要自己实现，可以用最简单的冒泡排序
二叉排序树
二叉排序树是特殊的二叉树，每个结点的都满足：左孩子比父结点小，右孩子比父节点大
建立二叉排序树
BiNode* createTree(BiNode *node, int x) {//接受一个树的根节点指针和一个要插入的值
//建树
if (node==NULL) {
node=(BiNode*)malloc(sizeof(BiNode));
node->data = x;
node->lchild = NULL;
node->rchild = NULL;
}
//插入值
else if (x>node->data) { //如果比该结点大就插入为右孩子
node->rchild = createTree(node->rchild, x);
}
else if (x<node->data) { //如果比该结点小就插入为左孩子
node->lchild = createTree(node->child, x);
}
return node;
}
主函数调用
BiNode *root = NULL;
root = createTree(root, 10);
root = createTree(root, 5);
root = createTree(root, 13);
root = createTree(root, 14);
root = createTree(root, 19);