没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示


试读
64页
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; //二叉树结点类型BitNode,指向二叉树结点的指针类型BiTree typedef BiTree SElemType; //顺序栈中的元素为指向二叉树结点的指针 typedef BiTree QElemType; //循环队列中的元素为指向二叉树结点的指针 #include "循环队列头文件.h" #include "顺序栈头文件.h" //含自定义顺序栈操作函数
资源推荐
资源详情
资源评论




6.1 树的定义和基本术语
6.1.1 树的定义
递归定义:
树 (tree) 是 n(n≥0) 个结点的有限集。在任意一棵非空树中:
(1) 有且仅有一个特定的称为根 (root) 的结点;
(2) 当 n>1 时 , 其余结点可分为 m(m>0) 个互不相交的有限集 T1,T2,…,T
m, 其中每个集合本身又是一棵树,且称为根的子树 (SubTree) 。
形式化定义:
树: T = {K,R} 。 K 是包含 n(n≥0) 个结点的有限集合,关系 R 满足以下条件:
(1) 有且仅有一个结点 k0 K,∈ 它对于关系 R 来说没有前驱结点,结
点 k0 称作树的根。
(2) 除结点 k0 外 ,K 中的每个结点对于关系 R 来说都有且仅有一个
前驱结点。
(3)K 中每个结点对于关系 R 来说可以有多个后继结点。
树与线性表的比较
线性表 树
第一个数据元素 ( 无前驱 ) 根结点 ( 无前驱 )
最后一个数据元素 ( 无后继 ) 多个叶子结点 ( 无后继 )
其它数据元素 ( 一个前驱、一个后继 ) 树中其它结点 ( 一个前驱、多个后继 )

6.1.2 树的表示
(1) 树形表示法。这是树的最基本的表示,使用一棵倒置的树表示
树结构,非常直观和形象。见图 6.1(a) 。
(2) 文氏图表示法。使用集合以及集合的包含关系描述树结构。见
图 6.1(b) 。
(3) 凹入表示法。使用线段的伸缩描述树结构。见图 6.1(c) 。
(4) 括号表示法。将树的根结点写在括号的左边 , 除根结点之外的
其余结点写在括号中并用逗号间隔来描述树结构。见图 6.1(d) 。
A
C
G
J
B
E
D
F
I
H
M
K
L
树形表示法
H
L
D
K
I
M
C
G
J
E
B
F
(b) 文氏图表示法
A

F
C
A
B
D
E
G
J
H
I
K
L
M
(c)凹入表示法
(d)括号表示法
A(B(E,F),C(G(J)),D(H,I(K,L,M)))

6.1.3 树的基本术语
1. 结点的度与树的度:
树的结点包含一个数据元素及若干指向其子树的分支。树中结点拥
有的子树数称为结点的度 (Degree) 。树中各结点的度的最大值
称为树的度。度为 m 的树称为 m 次树。
2. 分支结点与叶结点:
度不为零的结点称为非终端结点 , 又叫分支结点。度为零的结点称
为叶子 (Leaf) 结点或终端结点。在分支结点中 , 每个结点的分支
数就是该结点的度。如对于度为 1 的结点 , 其分支数为 1, 被称为
单分支结点;对于度为 2 的结点 , 其分支数为 2, 被称为双分支结
点 , 其余类推。
3. 路径与路径长度:
对于任意两个结点 ki 和 kj, 若树中存在一个结点序列 ki,ki1,ki2,…,
kin,kj, 使得序列中除 ki 外的任一结点都是其在序列中的前一个
结点的后继 , 则称该结点序列为由 ki 到 kj 的一条路径 , 用路径所
通过的结点序列 (ki,ki1,ki2,…,kj) 表示这条路径。路径的长度等
于路径所通过的结点数目减 1( 即路径上分支数目 ) 。可见 , 路径
就是从 ki 出发“自上而下”到达 kj 所通过的树中结点序列。显然 ,
从树的根结点到树中其余结点均存在一条路径。

4. 孩子、双亲和兄弟结点:
结点的子树的根称为该结点的孩子 (Child) ,相应地 , 该结点称为孩
子的双亲 (Parent) 。同一双亲的孩子之间互称兄弟( Sibling )。
以某结点为根的子树中任一结点都称为该结点的子孙。从根结点
到达某结点的路径上所经过的所有结点称为该结点的祖先。
5. 结点的层次和树的深度:
树中的每个结点都处在一定的层次上。结点的层次 (Level) 从树根
开始定义 , 根为第 1 层,根的孩子为第 2 层,以此类推,一个结
点所在的层次为其双亲结点所在的层次加 1 。树中结点的最大层
次称为树的深度 (Depth) 或高度。其双亲在同一层的结点互为堂
兄弟。
6. 有序树和无序树:
若树中各结点的子树是按从左至右有次序的 ( 即不能互换 ) ,则称
该树为有序树,否则称为无序树。
7. 森林:
森林 (Forest) 是 m(m≥0) 棵互不相交的树的集合。
森林的概念与树的概念十分相近 , 因为只要把树的根结点删去就成
了森林。反之,只要给 n 棵独立的树加上一个结点,并把这 n 棵
树作为该结点的子树,则森林就变成了树。
剩余63页未读,继续阅读
资源评论

- kobe_mvp_kobe2013-03-05二叉树的其他几种方式在实现方面和这个二叉链表方式的区别在哪?
- fancyyesnot2011-11-10数据结构的资料还是蛮好的

xnzxchun
- 粉丝: 1
- 资源: 21
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


安全验证
文档复制为VIP权益,开通VIP直接复制
