《《数据结构a》第05章——01》由会员分享，可在线阅读，更多相关《《数据结构a》第05章——01（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 Data Structures in C+Data Structures in C+第第5 5章章 树树5.1 树的基本概念 5.2 二叉树 5.3 二叉树的遍历 5.4 二叉树遍历的非递归算法 5.5 树和森林 5.6 堆和优先权队列 5.7 哈夫曼树和哈夫曼编码 5.8 并查集和等价关系5.1 5.1 树的基本概念树的基本概念 树形结构是元素之间有着分层关系的结构 ，它类似于自然界中的树。这是一类很重要 的非线性数据结构。一方面，计算机应用中，常常出现嵌套的 数据，树结构提供了对该类数据的自然表示 。另一方面利用树结构，我们可以有效地解 决一些算法问题。图5-1 西欧语言
2、谱系图原始印欧语古意大利语日耳曼语西日耳曼语拉丁语西 班 牙 语法语意 大 利 语希腊语北日耳曼语冰岛语瑞典语挪威语英语荷兰语德语古希腊语5.1.1 5.1.1 树的定义树的定义定义定义5.15.1 树是包括n个结点的有限 非空集合D，R是D中元素的序偶 的集合，R满足以下特性： （1）有且仅有一个结点rD，不 存在任何结点vD，vr，使得 R，称r为树的根根 ； （2）除根r以外的所有结点uD， 都有且仅有一个结点vD，vu ，使得R。这样定义的树也称有根树，简称 树。 定义定义5.25.2 树是包括n个结点的有限非空集合T ，其中，一个特定的结点r称为根，其余结 点 T-r划分成m（m0）
3、个互不相交的子 集T1,T2,Tm，其中，每个子集都是树， 被称为树根r的子树子树。 5.1.2 5.1.2 基本术语基本术语树中元素常称为结点 。根和它的子树根（如 果存在）之间形成一条 边 。如果从某个结点 沿着树中的边可到达另 一个结点，则称这两个 结点间存在一条路径 。若一个结点有子树，那 么该结点称为子树根的双 亲，子树的根是该结点的 孩子。有相同双亲的结点 互为兄弟。一个结点的所 有子树上的任何结点都是 该结点的后裔。从根结点 到某个结点路径上的所有 结点都是该结点的祖先 。一个结点拥有的子树数称 为该结点的度。度为零的 结点称为叶子，其余结点 称为分支结点。树中结点 的最大的度称为树的度。 树是层次结构的，规定根 结点的层次为1，其结点 的层次等于其双亲结点的 层次加1。树中结点的最 大层次称为该树的高度。如果树中结点的各子树之间的次序是不重要的， 可以交换位置，这样的树称为无序树。也就是我 们通常所说的树。如果将树中结点的各棵子树看 成是从左到右有次序的，则称该树为有序树。从 左到右，可分别称这些子树为第一子树，第二子 树等等。森林是树的集合。果园或称有序森林是有序树 的有序集合。
