数据结构树和二叉树pptVIP免费

树的概念树的遍历及存储二叉树二叉树的遍历线索二叉树哈夫曼树及其应用树的递归定树的递归定义义树是由树是由nn((nn0)0)个结点个结点组成的有限集合

如果组成的有限集合

如果nn==00，称为空树；如果，称为空树；如果nn>0>0，，则则有一个特定的称之为有一个特定的称之为根根(root)(root)的结点，它只有直接后的结点，它只有直接后继，但没有直接前驱；继，但没有直接前驱；除根以外的其它结点划除根以外的其它结点划分为分为mm((mm0)0)个互不相交个互不相交的有限集合的有限集合TT00,,TT11,…,,…,TTmm-1-1，每，每个集合又是一棵树个集合又是一棵树，，并且称之并且称之为根的为根的子树子树

树的概念树的概念ACGBDEFKLHMIJ树的逻辑结构树的逻辑结构••除了根结点外，每个结点有且除了根结点外，每个结点有且仅有一个直接前驱

仅有一个直接前驱

••所有结点可以有多个直接后继所有结点可以有多个直接后继

1--1--多多树的表示(1)树形表示法

这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象

下图就是采用这种表示法

ACGJBEDFIHMKL树形表示法(2)文氏图表示法

使用集合以及集合的包含关系描述树结构

下图就是树的文氏图表示法

HLDKIMCGJEBF文氏图表示法A(3)凹入表示法

使用线段的伸缩描述树结构

下图是树的凹入表示法

FCABDEGJHIKLM凹入表示法(4)括号表示法

将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构

下图是树的括号表示法

括号表示法A(B(E,F),C(G(J)),D(H,I(K,L,M)))ADTTree{数据对象:D={ai|1in,n0,ai属Elemtype类型数据关系:R1={|ai,ajD,1in,1jn