Tag Archives:

数据结构重读 – 树和森林

树的存储,不再限于二叉树了。

1、双亲标示法
虽然每个结点可能有多个孩子,但是每个孩子只可能有一个双亲,这是固定的。
于是有了双亲标示法。
每个孩子存在数组中,孩子记录其双亲的位置。
如果根据某个孩子找双亲,可以几乎在常数时间搞定(反复调用PARENT(T, X),直到X为根为止)。
但是如果要从树根往下遍历求孩子结点,则需要遍历整个数组,会很慢。

typedef struct PTNode
{
int data;
int parent;
};

typdef[……]

继续阅读

数据结构重读 – 树的定义和基本术语

1、树是n(n>=0)个结点的有限集合。树中有且仅有一个结点为根(Root)。

2、当定义1中的n>1时,其余结点可以分为m个互不相交的有限集合T1、T2。。。每一个子集都是一颗树,并且是根的子树。

3、树中结点的:结点拥有子树的个数(分叉数)称为结点的度(Degree)

4、度为0的结点称为叶子(Leaf)结点。度非0的结点是分支结点或非终端结点。

5、公式:树中结点的数量 = 所有结点的度之和 + 1

6、结点的子树的根称为该结点的孩子。该结点[……]

继续阅读

数据结构 – 树的度和结点数的关系

一、概念

与图论中的“度”不同,树的度是如下定义的:有根树T中,结点x的子女数目称为x的度。也就是:在树中,结点有几个分叉,度就是几。

一个有用的小公式:树中结点数 = 总分叉数 +1。(这里的分叉数就是所有结点的度之和)

二、度的计算

1.设树T的度为4,其中度为1,2,3,4的节点个数分别为4,2,1,1,则T中的叶子数为?

解:

叶子的度数为0;那么设叶子数为x,则此树的总分叉数为1*4+2*2+3*1+4*1=15;此树的节点个数为16(此处涉及到一个[……]

继续阅读

树的双亲存储之Java实现