本文共 2304 字,大约阅读时间需要 7 分钟。
必须做到唯一反映树中各节点之间的逻辑关系
。树的常用的表示方法有三种,分别是双亲表示法、孩子表示法和孩子兄弟表示法
。以一组连续的存储单元存储树的结点,每个结点除了数据域 data 外,还设有 parent 域用于指示其双亲结点
,形式如下: typedef struct TreeNode{ int data; int parent;};typedef struct Tree{ TreeNode nodes[size]; int n;};
对于树,数组下标代表结点编号,下标中所存的内容指示了各节点之间的关系;对于二叉树,数组下标既代表节点编号又指示了各节点之间的关系。
二叉树都可用树的存储结构来存储,但树不能用二叉树的存储结构来存储。其实,树与二叉树就是一般与个别的关系,个别所有的性质在一般里都可以找到,但一般有的性质在个别里就不一定有
。该法,是将每个结点的孩子结点都用单链表链接起来形成一个线性结构
,n 个节点就有 n 个孩子链表,其形式如下:
上图对应的二叉树如下:
这种存储结构,对寻找子女的操作极其方便,却不利于寻找双亲,寻找双亲需要遍历n个节点中孩子链表指针域所指向的 n 个孩子链表
。
二叉树表示法
,以二叉链表作为树的存储结构
。第一个孩子节点和下一个兄弟节点
。 typedef struct TreeNode{ int data; TreeNode *firstchild, *nextsibling;};
进行树转换二叉树的操作极其方便,且易于查找结点的孩子
;不足之处在于查找当前节点的双亲。二叉树和树都可以用二叉链表表示
,故而通过二叉链表可以找到树与二叉树的一一对应关系。每个节点左指针指向它的第一个孩子,右指针指向它在树中相邻的右兄弟
,此规则称为左孩子右兄弟
规则。根据该规则,由于根节点没有兄弟,所以对应的二叉树是没有右子树
的。先间森林中的每棵树转为二叉树,由于树对应的二叉树都是没有右子树的,因此可以将森林中的第二棵二叉树视为目标二叉树的根节点的右子树,将第三棵视为第二棵的右子树……以此类推
。 树转换成二又树的画法
:①在兄弟结点之间加一连线;②对每个结点,只保留它与第一个孩子的连线,而与其他孩子的连线全部抹掉;③以树根为轴心,顺时针旋转45°。先根遍历和后根遍历
。若根非空,则先访问根节点,再依次遍历根节点每棵树
。 2)遍历子树时,遵循先根遍历原则
。若树非空,先依次遍历根节点的每棵子树,再访问根节点
。 2)遍历子树时遵循后根遍历原则
。先序遍历和中序遍历
。访问森林中第一棵树的根结点
; ②先序遍历第一棵树的根结点的子树森林
; ③先序遍历除去第一棵树之后剩余的树构成的森林
。中序遍历森林中第一棵树的根结点的子树森林
; ②访问第一棵树的根结点
; ③中序遍历除去第一棵树之后剩余的树构成的森林
。 把集合S中的子集合Root2并入子集合Root1.要求Root1和Rot2互不相交,否则不执行合并
。 2)Find(S,x):査找集合s中单元素x所在的子集合,并返回该子集合的名字
。 3) Initial(S):将集合S中的每个元素都初始化为只有一个单元素的子集合
。转载地址:http://hqqgn.baihongyu.com/