二叉树的三种常用存储结构

树的三种常用存储结构孩子兄弟表示法、孩子表示法、双亲表示法各有特点适用于不同场景。其核心定义、优缺点及适用场景对比如下表示法核心定义优点缺点典型适用场景孩子兄弟表示法每个节点包含数据域、指向其第一个孩子的指针、指向其下一个兄弟的指针。1.结构统一便于实现树与二叉树的相互转换。2. 便于实现大多数树的操作如遍历、查找孩子。1. 查找指定节点的双亲效率较低需要遍历。1. 需要将树转换为二叉树处理的场景。2. 文件系统目录结构。3. 需要频繁进行先根/后根遍历的场景。孩子表示法每个节点的所有孩子节点链接成一个单链表节点本身包含数据域和指向该孩子链表头部的指针。1. 查找某个节点的所有孩子非常方便、高效。2. 直观反映了节点的孩子关系。1. 查找节点的双亲困难同样需要遍历。2. 若每个节点的孩子链表都单独存储空间开销可能较大。1. 需要频繁查找或遍历某个节点所有孩子的场景如任务调度、家谱查询子孙。双亲表示法使用一组连续空间如数组存储所有节点每个节点包含数据域和指向其双亲节点在数组中位置的索引根节点的双亲索引为-1。1.查找任意节点的双亲速度极快O(1)。2. 结构简单存储紧凑。1. 查找某个节点的所有孩子效率低需要遍历整个数组。2. 不便于实现树的遍历等操作。1.并查集Union-Find数据结构。2. 需要频繁查找节点祖先或双亲的场景如组织架构向上汇报。1. 孩子兄弟表示法二叉链表表示法这是最常用的树存储结构之一又称“左孩子右兄弟表示法”。它将一棵普通的树转换为一棵二叉树进行存储。数据结构定义C语言typedef struct CSNode { ElemType data; // 节点数据 struct CSNode *firstChild; // 指向第一个孩子节点左孩子 struct CSNode *nextSibling; // 指向下一个兄弟节点右兄弟 } CSNode, *CSTree;示例对于下图所示的树A / | \ B C D / \ \ E F G其孩子兄弟表示法对应的二叉树形态为A / B / \ E C \ \ F D / G节点A的firstChild指向BnextSibling为NULL根节点无兄弟。节点B的firstChild指向EnextSibling指向C。节点E的firstChild为NULLE无孩子nextSibling指向F。核心操作示例先根遍历void PreOrderTraverse(CSTree T) { if (T) { visit(T-data); // 访问根节点 PreOrderTraverse(T-firstChild); // 递归遍历子树第一个孩子链 PreOrderTraverse(T-nextSibling);// 递归遍历兄弟链 } } // 此遍历顺序等价于原树的先根遍历。2. 孩子表示法此方法将每个节点的孩子组织成一个链表。数据结构定义C语言#define MAX_TREE_SIZE 100// 孩子链表节点 typedef struct CTNode { int childIdx; // 孩子在数组中的位置索引 struct CTNode *next; // 指向下一个孩子} *ChildPtr; // 表头节点typedef struct { ElemType data; // 节点数据 ChildPtr firstChild; // 指向第一个孩子的指针 } CTBox; // 树结构 typedef struct { CTBox nodes[MAX_TREE_SIZE]; // 节点数组 int rootIdx; // 根节点位置 int nodeNum; // 节点数 } CTree;存储示意图对于上述示例树假设节点按A(0), B(1), C(2), D(3), E(4), F(5), G(6)顺序存储nodes[0]AdataA,firstChild- 链表[1]-[2]-[3](B, C, D)。nodes[1]BdataB,firstChild- 链表[4]-[5](E, F)。nodes[3]DdataD,firstChild- 链表[6](G)。3. 双亲表示法此方法通过存储每个节点的双亲位置来隐式表示树结构。数据结构定义C语言#define MAX_TREE_SIZE 100 typedef struct PTNode { ElemType data; // 节点数据 int parentIdx; // 双亲节点在数组中的索引根节点通常设为-1 } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; // 节点数组 int nodeNum; // 节点数 } PTree;存储示例对于上述示例树其双亲表示法数组存储内容如下数组索引dataparentIdx0A-11B02C03D04E15F16G3核心操作示例查找节点所有孩子// 在双亲表示法中查找节点p的所有孩子效率较低 void FindChildren(PTree tree, int p) { printf(节点%c的孩子有, tree.nodes[p].data); for (int i 0; i tree.nodeNum; i) { if (tree.nodes[i].parentIdx p) { // 遍历整个数组寻找双亲为p的节点 printf(%c , tree.nodes[i].data); } } printf( ); }总结与选择建议需要频繁进行树与二叉树转换、或进行先根/后根遍历时优先选择孩子兄弟表示法。需要频繁查找节点的所有孩子时孩子表示法更高效。需要频繁查找节点的双亲或祖先如并查集操作双亲表示法是首选并可结合路径压缩等优化技术。在实际工程中可根据主要操作类型混合使用这些表示法或在双亲表示法的基础上增加孩子链表指针形成“带孩子链的双亲表示法”以兼顾双亲与孩子的查找效率。参考来源从AnyView习题到实战树与并查集核心算法深度剖析树与二叉树学习笔记【数据结构】图解树与二叉树从底层逻辑到数学性质的深度重构【数据结构·考研】左孩子右兄弟解锁树与二叉树转换的算法密码数据结构课设救星手把手教你用C语言搞定Anyview树与并查集习题附完整代码