数据结构之树的超详细讲解(附C实现代码)

树的基本性质

二叉树

定义树结点结构体

建树

根据二叉树的层次遍历建树

根据前序或后序建树

遍历二叉树

前序遍历

中序遍历

后序遍历

根据前序和中序序列输出后序序列

根据后序和中序序列输出前序序列

根据前序和后序判断树的个数

求树的高度(DFS)

求树的宽度

求树的叶子结点个数

哈夫曼树

二叉排序树

树的基本性质

节点的度：该节点拥有的孩子个数

叶子节点：度为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);