资讯详情

深入了解 · 专业解读

数据结构06-树结构

发布时间：2026/7/6 0:11:07
数据结构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叶子节点数13811333 27142.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 1get_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 1get_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; }④ makefileOBJa.out SRCmain.c tree.c linkqueue.c CCgcc $(OBJ) : $(SRC) $(CC) $^ -o $ clean: rm $(OBJ)

相关新闻