数据结构06-树结构

一、树的介绍

①树：由一个根节点和若干个分支节点构成的具有一对多关系的数据的集合。每一棵树必有一特定的节点，称做根节点(root);根节点之下可以有零个以上的子节点（可以没有），而各子节点也可为子树，拥有自己的子节点。

② 树的相关名称

• 根节点：位于树结构最顶层的节点；A
• 分支节点：有子节点的节点；B、C、D
• 叶子节点（终端节点）：没有子节点的节点；E、F、G、H、I、J
• 树的深度（层数）：树结构的层级总数；3层
• 树的广度（度）：树中节点的度最大的值即为该树的度；3
• 节点的度：节点的子节点个数；3

二、二叉树

2.1 二叉树介绍

① 二叉树(Binary tree)是树的一种，二叉树中的节点至多只能有两个子节点（度为2的树）。

② 二叉树的定义

• 由有限个节点所构成之集合，此集合可以为空的。
• 二叉树的根节点下可分成两个子树，称为左子树和右子树，左子树和右子树亦称二叉树。

2.2 两种特殊的二叉树

① 满二叉树：

• 一树中所有叶子节点均在同一阶层，而其它非终端节点之分支度均为2，则此树为一满二叉树。（在不增加层数的前提下，无法增加一个节点，这种二叉树是一个满二叉树）
• 满二叉树第k层的节点数：2^(k-1) ； K层·总的节点数：(2^k)-1

② 完全二叉树：

• 在满二叉树的基础上，按照从上至下，从左至右的方式增加若干个连续的节点。
• 满二叉树一定是一棵完全二叉树

③ 计算题：一个完全二叉树的节点总数为5428，求其叶子节点的个数：

解题步骤：

一个12层的满二叉树的节点总数： 2^12-1 = 4095

（完全二叉树比满二叉树多的节点数）最后一层叶子节点：5428-4095 = 1333

第12层节点数：2^(12-1) = 2048

倒数第二层非叶子节点1333/2 = 667
倒数第二层叶子节点 2048-667 = 1381
叶子节点数：1381+1333 = 2714

2.3 二叉树的遍历

2.3.1 深度优先算法

① 前序遍历：遍历顺序--> 根，左子树，右子树，如 ABEFIDHMJ

② 中序遍历：遍历顺序--> 左子树，根，右子树，如 EBFIAMHDJ

③ 后序遍历：遍历顺序--> 左子树，右子树，根，如 EIFBMHJDA

• 已知一个前序遍历和中序遍历结果，可以确定一棵唯一的二叉树；
• 已知一个后序遍历和中序遍历结果，可以确定一棵唯一的二叉树；

2.3.2广度优先算法

① 层序遍历：遍历顺序--> 从上至下，从左至右，逐层遍历，如 ABDEFHJIM

三、二叉树的实现

3.1 二叉树的声明

typedef char TDataType_t; typedef struct trnode { TDataType_t data; //存储树节点的数据值 struct trnode *pl; //指向左子树（left child）的指针 struct trnode *pr; //指向右子树（right child）的指针 }TNode_t;

3.2 创建二叉树

//根据前序遍历序列（用 # 表示空节点）创建二叉树 TDataType_t tree[] = {"ABE##F#I##DHM###J##"}; //字符数组 tree int idx = 0; //全局索引变量 TNode_t *create_bin_tree() //无参数，依赖全局变量 tree 和 idx { TDataType_t data = tree[idx++]; //idx++ 是后置自增：先取值，再让 idx 加1 if ('#' == data) //如果读到的字符是 #，表示该位置没有节点 { return NULL; //直接返回 NULL，结束当前递归分支 } //使用 malloc 动态分配一个 TNode_t 结构体大小的内存。 TNode_t *pnode = malloc(sizeof(TNode_t)); if (NULL == pnode) { printf("malloc error\n"); return NULL; } pnode->data = data; //将当前读取到的数据存入节点 pnode->pl = create_bin_tree(); //递归调用创建左子树 pnode->pr = create_bin_tree(); //递归调用创建右子树 return pnode; }

3.3 前序遍历二叉树

//前序遍历二叉树函数，按照 根节点 → 左子树 → 右子树 的顺序访问二叉树的所有节点 void pre_order(TNode_t *proot) //TNode_t *proot，指向当前要遍历的子树根节点 { if (NULL == proot) //查当前节点是否为空 { return ; //直接返回，结束当前递归分支 } printf("%c", proot->data); //打印根 pre_order(proot->pl); //递归访问左子树 pre_order(proot->pr); //递归访问右子树 }

3.4 中序遍历二叉树

void mid_order(TNode_t *proot) { if (NULL == proot) { return ; } mid_order(proot->pl); //递归访问左子树 printf("%c", proot->data); //打印根 mid_order(proot->pr); //递归访问右子树 }

3.5 后序遍历二叉树

void pos_order(TNode_t *proot) { if (NULL == proot) { return ; } pos_order(proot->pl); //递归访问左子树 pos_order(proot->pr); //递归访问右子树 printf("%c", proot->data); //打印根 }

3.6 获取二叉树的节点个数

//递归实现的二叉树节点计数函数，通过后序遍历的方式统计整棵树的总节点数 int get_tree_node_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } return 1+get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr); }

3.7 获取二叉树的最大深度（层数）

//递归实现的二叉树高度计算函数，返回以 proot 为根的子树的最大层数（深度） int get_tree_layer_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } //递归计算左子树的高度（层数） int cntl = get_tree_layer_cnt(proot->pl); //递归计算右子树的高度（层数） int cntr = get_tree_layer_cnt(proot->pr); //条件运算符（三目运算符） return cntl > cntr ? cntl + 1 : cntr + 1; }

3.8 销毁二叉树

//递归实现的二叉树内存释放函数 void destroy_bin_tree(TNode_t *proot) { if (NULL == proot) { return ; } destroy_bin_tree(proot->pl); //递归销毁左子树的所有节点 destroy_bin_tree(proot->pr); //递归销毁右子树的所有节点 free(proot); //释放当前节点 proot 所指向的内存 } //释放顺序：E → I → F → B → M → H → J → D → A（后序遍历顺序）

3.9 层序遍历二叉树

① 使用队列实现的二叉树层序遍历（广度优先遍历）函数，按照从上到下、从左到右的顺序访问所有节点。

② 思路：

创建队列、将根节点入队、出队节点、 打印出队节点的值、入队左右子节点、当队列为空，循环结束、销毁队列

void layer_order(TNode_t *proot) { LQueue_t *pque = NULL; //指向链式队列的指针，初始化为 NULL DataType_t outdata; //用于存储从队列中弹出的数据 pque = create_linkqueue(); //创建一个空队列 if (NULL == pque) { return ; } push_linkqueue(pque, proot); //将二叉树的根节点指针 proot 入队 while (!is_empty_linkqueue(pque)) //遍历所有节点 { pop_linkqueue(pque, &outdata); //从队列中取出一个节点指针，存入 outdata printf("%c", outdata->data); //打印该节点的数据 if (outdata->pl != NULL) //如果当前节点的左子节点不为空，将其入队 { push_linkqueue(pque, outdata->pl); } if (outdata->pr != NULL) //如果当前节点的右子节点不为空，将其入队 { push_linkqueue(pque, outdata->pr); } } //遍历完成后，释放队列内存 destroy_linkqueue(&pque); return ; }

3.10 附件代码

① tree.h

#ifndef __TREE_H__ #define __TREE_H__ typedef char TDataType_t; typedef struct trnode { TDataType_t data; struct trnode *pl; struct trnode *pr; }TNode_t; extern TNode_t *create_bin_tree(); extern void pre_order(TNode_t *proot); extern void mid_order(TNode_t *proot); extern void pos_order(TNode_t *proot); extern int get_tree_node_cnt(TNode_t *proot); extern int get_tree_layer_cnt(TNode_t *proot); extern void destroy_bin_tree(TNode_t *proot); extern void layer_order(TNode_t *proot); #endif

② tree.c

#include "tree.h" #include <stdio.h> #include <stdlib.h> #include "linkqueue.h" TDataType_t tree[] = {"ABE##F#I##DHM###J##"}; int idx = 0; TNode_t *create_bin_tree() { TDataType_t data = tree[idx++]; if ('#' == data) { return NULL; } TNode_t *pnode = malloc(sizeof(TNode_t)); if (NULL == pnode) { printf("malloc error\n"); return NULL; } pnode->data = data; pnode->pl = create_bin_tree(); pnode->pr = create_bin_tree(); return pnode; } void pre_order(TNode_t *proot) { if (NULL == proot) { return ; } printf("%c", proot->data); pre_order(proot->pl); pre_order(proot->pr); } void mid_order(TNode_t *proot) { if (NULL == proot) { return ; } mid_order(proot->pl); printf("%c", proot->data); mid_order(proot->pr); } void pos_order(TNode_t *proot) { if (NULL == proot) { return ; } pos_order(proot->pl); pos_order(proot->pr); printf("%c", proot->data); } int get_tree_node_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } return 1+get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr); } int get_tree_layer_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } int cntl = get_tree_layer_cnt(proot->pl); int cntr = get_tree_layer_cnt(proot->pr); return cntl > cntr ? cntl + 1 : cntr + 1; } void destroy_bin_tree(TNode_t *proot) { if (NULL == proot) { return ; } destroy_bin_tree(proot->pl); destroy_bin_tree(proot->pr); free(proot); } void layer_order(TNode_t *proot) { LQueue_t *pque = NULL; DataType_t outdata; pque = create_linkqueue(); if (NULL == pque) { return ; } push_linkqueue(pque, proot); while (!is_empty_linkqueue(pque)) { pop_linkqueue(pque, &outdata); printf("%c", outdata->data); if (outdata->pl != NULL) { push_linkqueue(pque, outdata->pl); } if (outdata->pr != NULL) { push_linkqueue(pque, outdata->pr); } } destroy_linkqueue(&pque); return ; }

③ main.c

#include "tree.h" #include <stdio.h> int main(int argc, const char *argv[]) { TNode_t *proot = create_bin_tree(); if (NULL == proot) { return -1; } pre_order(proot); printf("\n"); mid_order(proot); printf("\n"); pos_order(proot); printf("\n"); printf("node cnt = %d\n", get_tree_node_cnt(proot)); printf("layer cnt = %d\n", get_tree_layer_cnt(proot)); layer_order(proot); destroy_bin_tree(proot); return 0; }

④ makefile

OBJ=a.out SRC=main.c tree.c linkqueue.c CC=gcc $(OBJ) : $(SRC) $(CC) $^ -o $@ clean: rm $(OBJ)