树的存储结构

文章目录树的逻辑结构双亲表示法顺序存储孩子表示法顺序 链式存储孩子兄弟表示法链式存储树的逻辑结构树是一种递归定义的数据结构。树是n (n≥0)个结点的有限集合n0时称为空树这是一种特殊情况。在任意一棵非空树中应满足有且仅有一个特定的称为根的结点。当n1时其余结点可分为mm0个互不相交的有限集合T1,T2,…Tm其中每个集合本身又是一棵树并且称为根结点的子树。二叉树一个分支结点最多可能有两棵子树。树一个分支结点可以有多棵子树。【只依靠数组下标无法反映结点之间的逻辑关系】在树当中除了根结点外其他任何一个结点都有且仅有一个双亲结点有且仅有一个父结点。双亲表示法顺序存储如何实现树的存储结构用一维数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点父节点的“指针”。#defineMAX_TREE_SIZE100// 树中最多结点树// 树的结点定义typedefstruct{ElemType data;// 数据域 存储数据元素intparent;// 父结点在数组中的下标根结点 parent -1}PTNode;// 树的类型定义typedefstruct{PTNode nodes[MAX_TREE_SIZE];// 数组存储所有结点intn;// 当前结点个数}PTree;双亲表示法的优缺点优点查找双亲父节点极其方便O(1)。缺点查找某个结点的所有孩子必须遍历整个数组O(n)效率较低。适用于“找父亲”多“找孩子”少的应用场景。如并查集拓展双亲表示法存储“森林”每棵树的根节点双亲指针 -1孩子表示法顺序 链式存储孩子表示法用数组顺序存储各个结点。每个结点中保存数据元素、孩子链表头指针。将每个结点的所有孩子用一个单链表串起来。// 1. 孩子链表结点存储数组下标typedefstructCTNode{intchild;// 孩子在数组中的下标structCTNode*next;// 指向下一个兄弟}*ChildPtr;// 2. 表头结构数组元素typedefstruct{ElemType data;// 数据域ChildPtr firstChild;// 指向第一个孩子的指针}CTBox;typedefstruct{CTBox nodes[MAX_TREE_SIZE];// 数组intn,r;// 结点总数 和 根的位置}CTree;孩子表示法的优缺点优点查找某个结点的所有孩子非常方便。。缺点查找父结点需要遍历整个结构O(n)。适用于“找孩子”多“找父亲”少的应用场景。如服务流程树拓展孩子表示法存储“森林”。【注】用孩子表示法存储森林需要记录多个根的位置孩子兄弟表示法链式存储树的孩子兄弟表示法与二叉树类似采用二叉链表实现。每个结点内保存数据元素和两个指针但两个指针的含义与二叉树结点不同。// 树的存储——孩子兄弟表示法typedefstructCSNode{ElemType data;// 数据域structCSNode*firstchild,*nextsibling;// 左指向第一个孩子右指向右边一个兄弟}CSNode,*CSTree;// 二叉树结点链式存储typedefstructBiTNode{ElemType data;structBiTNode*lchild,*rchild;// 左子树 右子树}BiTNode,*BiTNode;拓展孩子兄弟表示法存储“森林”。【注】用“孩子兄弟表示法”存储 树或森林 时从存储视角来看形态上与二叉树类似。森林中的每棵树的根节点是为平级的兄弟关系。