当前位置：文档之家 › 数据结构ch6树与二叉树

数据结构ch6树与二叉树

  • 格式：ppt
  • 大小：3.10 MB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

数据结构-6 树和二叉树

数据结构-6 树和二叉树

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

树与二叉树的相关概念、特点

树与二叉树的相关概念、特点

树与二叉树的相关概念、特点
树与二叉树是数据结构中常见的两种类型。

树是一种非线性的数据结构，由若干个节点组成。

每个节点都可以连接到多个子节点，形成分层结构。

树中有一个特殊的节点，称为根节点，用于表示整个树的起始点。

树的节点之间的关系是具有层次性的，即一个节点可以有多个子节点，但每个节点只能有一个父节点（除了根节点）。

二叉树是一种特殊的树结构，每个节点最多只能有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空，此时表示为空树。

二叉树的子节点有左右之分，可以用于表示有序关系的数据结构，例如二叉查找树。

二叉树可以前序、中序和后序遍历，分别表示以根节点为中心，先处理根节点、先处理左子树和先处理右子树。

树与二叉树的特点包括：
1. 树和二叉树都是非线性结构，可以表示复杂的关系。

2. 树和二叉树都采用层次性的结构，节点之间有明确的父子关系。

3. 树中的节点可以拥有任意多个子节点，而二叉树中的节点最多只能有两个子节点。

4. 二叉树的左子节点和右子节点之间是有序的，可以用于实现查找等操作。

5. 二叉树可以方便地进行前序、中序和后序遍历操作，对数据的处理更加灵活。

6. 树和二叉树在实际应用中有广泛的应用，如数据库索引、文件系统、组织结构等。

数据结构—— 树和二叉树知识点归纳

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树6.1 知识点概述树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。

在计算机科学中具有广泛的应用。

1、树的定义树（Tree）是n（n≥0）个数据元素的有限集合。

当n＝0时，称这棵树为空树。

在一棵非空树T中：（1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。

（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。

树T1，T2，…，Tm称为这个根结点的子树。

2、树的基本存储结构（1）双亲表示法由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的存储空间（即一维数组）存储树中的结点。

每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。

（2）孩子表示法将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。

（3）双亲孩子表示法双亲表示法是将双亲表示法和孩子表示法相结合的结果。

其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。

（4）孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。

链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。

3、二叉树的定义二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

当集合为空时，称该二叉树为空二叉树。

数据结构之树和二叉树

数据结构之树和二叉树

数据结构之树和⼆叉树⼀树1 什么是树树状图是⼀种，它是由n（n>=1）个有限节点组成⼀个具有层次关系的。

把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

它具有以下的特点：每个节点有零个或多个⼦节点；没有⽗节点的节点称为根节点；每⼀个⾮根节点有且只有⼀个⽗节点；除了根节点外，每个⼦节点可以分为多个不相交的⼦树；树（tree）是包含n（n>0）个结点的有穷集，其中：（1）每个元素称为结点（node）；（2）有⼀个特定的结点被称为根结点或树根（root）。

（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每⼀个集合Ti（1<=i<=m）本⾝也是⼀棵树，被称作原树的⼦树（subtree）。

2 相关术语节点的度：⼀个节点含有的⼦树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；⾮终端节点或分⽀节点：度不为0的节点；双亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；孩⼦节点或⼦节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点；兄弟节点：具有相同⽗节点的节点互称为兄弟节点；树的度：⼀棵树中，最⼤的节点的度称为树的度；节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；树的⾼度或深度：树中节点的最⼤层次；堂兄弟节点：双亲在同⼀层的节点互为堂兄弟；节点的祖先：从根到该节点所经分⽀上的所有节点；⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。

森林：由m（m>=0）棵互不相交的树的集合称为森林；3 树模拟⽂件系统⽰例class Node:def__init__(self, name, type='dir'): = nameself.type = type # "dir" or "file"self.children = []self.parent = Nonedef__repr__(self):return class FileSystemTree:def__init__(self):self.root = Node("/")self.now = self.root # 当前⽬录def mkdir(self, name):# name已/结尾的⽂件夹if name[-1] != "/":name += "/"node = Node(name)self.now.children.append(node)node.parent = self.nowdef ls(self):return self.now.childrendef cd(self, name):if name[-1] != "/":name += "/"if name == "../":self.now = self.now.parentreturnfor child in self.now.children:if == name:self.now = childreturnraise ValueError("invalid dir")tree = FileSystemTree()tree.mkdir("var/")tree.mkdir("bin/")tree.mkdir("usr/")print(tree.root.children)print(tree.ls())tree.cd('bin/')tree.mkdir('python/')print(tree.ls())tree.cd("../")print(tree.ls())⼆、⼆叉树⼆叉树的链式存储：将⼆叉树的节点定义为⼀个对象，节点之间通过类似链表的链接⽅式来连接* 度不超过2的树* 每个节点最多有两个孩⼦节点* 两个孩⼦节点被区分为左孩⼦节点和右孩⼦节点满⼆叉树：⼀个⼆叉树如果每⼀个层的节点数达到最⼤值,则这个⼆叉树就是满⼆叉树完全⼆叉树：叶节点只能出现在最下层和次下层，并且最下⾯⼀层的节点都集中在该层最左边的若⼲位置的⼆叉树⼆叉树的遍历⽅式：前序遍历： EACBDGF中序遍历： ABCDEGF后序遍历： BDCAFGE层次遍历： EAGCFBDfrom collections import dequeclass BiTreeNode:def__init__(self, data):self.data = dataself.lchild = Noneself.rchild = Nonedef level_order(root):queue = deque()queue.append(root)while len(queue) > 0: # 只要栈不空node = queue.popleft()print(node.data, end=',')if node.lchild:queue.append(node.lchild)if node.rchild:queue.append(node.rchild)root = BiTreeNode(100)root.lchild = BiTreeNode(30)root.rchild = BiTreeNode(102)level_order(root)三⼆叉搜索树⼆叉搜索树是⼀棵⼆叉树且满⾜性质：设X是⼆叉树的⼀个节点。

Ch6树和二叉树-4

Ch6树和二叉树-4

rchild -1
4 -1 5 -1
-1 4 -1 5 -1
4
5
-1
-1
-1
-1
4
5 2
3 i 2 4 k 5 6
3
5
-1
0 -1 1 -1 -1
-1
3 -1 4 -1 -1
12
9
-1
-1
过程
6.7 赫夫曼树及赫夫曼编码
9 4 5 2 5 0 weight parent 2 lchild -1 rchild -1
6.7 赫夫曼树及哈夫曼编码
相关概念
叶子结点的权值：对叶子结点赋予的一个有意义 的数值量。 二叉树的带权路径长度：设二叉树具有n个带权值 的叶子结点，从根结点到各个叶子结点的路径长 度与相应叶子结点权值的乘积之和。 记为： WPL=
k =1
wk lk
从根结点到第k个叶子的路径长度
1
n
第k个叶子的权值；
lchild：指针域，结点的左孩子结点在数组中的下标； rchild：指针域，结点的右孩子结点在数组中的下标； parent：指针域，该结点的双亲结点在数组中的下标。
8
6.7 赫夫曼树及赫夫曼编码
伪代码
1. 数组huffTree初始化，所有元素结点的双亲、左 右孩子都置为-1； 2. 数组huffTree的前n个元素的权值置给定值w[n]； 3. 进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点， 其下标分别为i1, i2； 3.2 将二叉树i1、i2合并为一棵新的二叉树k；
i1
lchild -1
rchild -1
0 1 2 3
2
4 -1 -1
-1 4 -1 -1

金融工程学CH06-期权定价的离散模型——二叉树模型(上财)

金融工程学CH06-期权定价的离散模型——二叉树模型(上财)
衍生品的价值等于其在风险中性世界的期望收益以无风险利率贴 现的贴现值
Su
S0
VTu
V0
Sd
VTd
书上例子回顾
Su = 22 ƒu = 1 S ƒ Sd = 18 ƒd = 0
p是风险中性概率 20e0.12 ´0.25 = 22p + 18(1 – p ); p = 0.6523
或者我们可以用以下公式求出：
期权V的空头和D份基础资产S组成组合P
DSTu – Vu
P DS -V
DSTd – Vd
假设存在D使得P是无风险的，即使得PT= DST –VT无风险，即P的收益等于 无风险的债券的收益
PT P0
BT B0
PT
P0 DST
- VT
P0
求解D和V0
形成方程组 解得：
DS0u -VTu DS0 -V0
举一个例子，某人投一次硬币。那么样本空间就是正 面和反面。此外如果该硬币是工整的，那么这个试验， 也就是投一次硬币的概率测度就可以确定了。它是： Prob({正面})=Prob({正面})=0.5 Prob(空集)=0 Prob({正面,反面})=1
概率测度Q
定义新的概率测度Q
qu =ProbQ{ST
DS0d
- VTd
DS0
-V0
D VTu - VTd
S0 u - d
V0
-
1
PT
DS0
1
u
-d -d
VTu
u u
-
d
VTd
d u
股票预期收益的无关性
当根据股票价格为期权估值时，我们不需要考 虑股票的预期收益
风险中性定价
VT =e-rT [ p VTu + (1 – p )VTd ] 变量 p 和(1 – p )可以解释为风险中性的上涨和下跌概率

数据结构Ch6习题答案

Ch6树一、选择题：1．下列关于哈夫曼树的叙述，错误的是( C )。

A．哈夫曼树根结点的权值等于所有叶结点权值之和。

B．具有n个叶结点的哈夫曼树共有2n-1个结点。

C．哈夫曼树是一棵二叉树，因此它的结点的度可以为0，1，2。

D．哈夫曼树是带权路径长度最短的二叉树。

2．由3个结点可以构成多少棵不同形态的二叉树( C )。

A．3 B．4 C．5 D．6（3．如果一棵二叉树结点的前序序列是A，B，C，后序序列是C，B，A，则该二叉树结点的中序序列是( D )。

A．A，B，C B．A，C，B C．B，C，A D．不能确定4．如图所示的4棵二叉树中，( B )不是完全二叉树。

A．B．C．D．5．二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法( B )A．正确B．错误若结点有左子树，则令其lchild指针指示其左孩子；若结点没有左子树，则令其lchild指针指示其前驱；若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。

)6．二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法( A)。

A．正确B．错误7．对一棵70个结点的完全二叉树，它有( A )个叶子结点。

A．35 B．40 C．30 D．448．设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为( D )。

A．10 B．11 C．12 D．不确定n0=n2+19．假定根结点的层次为0，含有15个结点的二叉树最小高度为( A )。

A．3 B．4 C．5 D．6）假定根结点的层次为1，含有15个结点的二叉树最小高度为410．若一棵二叉树中，度为2的结点数为9，该二叉树的叶子结点的数目为( A )。

A．10 B．11 C．12 D．不确定n0=n2+111．设根结点的层次为0，则高度为k的二叉树的最大结点数为(C )。

A．2k-1 B．2k C．2k+1-1 D．2k+1若设根结点的层次为1，则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2k+1-1 12．以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为( D )。

数据结构第六章树和二叉树习题及答案

习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

数据结构课件CH6

树是一类重要的非线性数据结构，是以分支关系 定义的层次结构。
§6.1 树的定义
定义：
树(tree)是n(n>0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n>1时，其余结点可分为m(m>0)个互不相交的有 限集T1,T2,……Tm，其中每一个集合本身又是一棵树， 称为根的子树(subtree)
• 每个结点至多有二棵子树(即不存在度大于2的结点) • 二叉树的子树有左、右之分，且其次序不能任意颠倒
★ 基本形态

A
A
A
A
只有根结 空二叉树 点的二叉树
B 右子树为空
B
B
C
左子树为空
左、右子 树均非空
二叉树的基本运算
① 构造一棵二叉树 CreateBTree ( BT) ② 清空以BT为根的二叉树 ClearBTree(BT) ③ 判断二叉树是否为空 BTreeEmpty(BT) ④ 获取给定结点的左孩子和右孩子
遍历的过程就是把非线性结构的二叉树中的结点排 成一个线性序列的过程。
二叉树遍历方法可分为两大类，一类是“宽度优先 ”法，即从根结点开始，由上到下，从左往右一层一层 的遍历；另一类是“深度优先法”，即一棵子树一棵子 树的遍历。
按根、左子树和右子树三部分进行遍历
• 方法
★ 先序遍历：先访问根结点,然后分别先序遍历左子树、 右子树
★ 特点：
» 叶子结点只可能在层次最大的两层上出现; » 对任一结点，若其右分支下子孙的最大层次为L，则
其左分支下子孙的最大层次必为L或L+1。
1
2
3
4
5
6
7
8 9 10 11 12 13 14 15

ch6树与二叉树共62页


结点A的孩子：B，C，D 结点B的孩子：E，F
树的度：3
B
叶子：K，L，F，G，M，I，J
结点I的双亲：D
A
结点L的双亲：E
C
D
结点B，C，D为兄弟 结点K，L为兄弟
E
KL 结点A的层次：1 结点M的层次：4
F GH M
IJ
树的深度：4
结点F，G为堂兄弟 结点A是结点F，G的祖先
6.2 二叉树
a 浪费空间，适于存满二叉树和完全二 叉树
b
c
1 2 3 4 5 6 7 8 9 10 11
abcde0000fg
d
e
f
g
链式存储结构
二叉链表
typedef struct node { datatype data;
struct node *lchild, *rchild; }JD;
A
B
第六章 树和二叉树
树是一类重要的非线性数据结构，是以分支关 系定义的层次结构
6.1 树的定义
定义
定义：树(tree)是n(n>=0)个结点的有限 集T，其中：
N=0时，为空树。 对一个非空树，有且仅有一个特定的结点， 称为树的根(root)
当n>1时，其余结点可分为m(m>0)个 互不相交的有限集T1,T2,……Tm，其中 每一个集合本身又是一棵树，称为根的子 树(subtree)
(1) 如果i=1，则结点i是二叉树的根，无双 亲；如果i>1，则其双亲是i/2
(2) 如果2i>n，则结点i无左孩子；如果 2in，则其左孩子是2i
(3) 如果2i+1>n，则结点i无右孩子；如果 2i+1n，则其右孩子是2i+1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
缺点： 等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。
data link 1 link 2 ...
...
link n
困惑：到底应当开多少个链域?
补充：树的5种表示法：
❖ 图形表示法 ❖ 嵌套集合表示法 ❖ 广义表表示法 ❖ 凹入表示法 ❖ 左孩子－右兄弟表示法
6.1 树的基本概念
6.1.1 树的定义 6.1.2 若干术语 6.1.3 逻辑结构 6.1.4 存储结构 6.1.5 树的运算
6.1.1 树的定义
由一个或多个(n≥0)结点组成的有限集合T，有且仅有一 个结点称为根（root），当n>1时，其余的结点分为m(m≥0) 个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是 棵树，被称作这个根的子树 。
6.2 二叉树
为何要重点研究每结点最多只有两个 “叉” 的树？ ✓ 二叉树的结构最简单，规律性最强； ✓ 可以证明，所有树都能转为唯一对应的二叉树，
不失一般性。
6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构
注：二叉树最重要的运算是：遍历！
整理ppt
19
6.2.1 二叉树的定义
注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是 树”的说法，但现在树的定义已修改。
注2：树的定义具有递归性，即“树中还有树”。
6.1.2 若干术语
A
B
C
D
根 ——即根结点(没有前驱)
叶子 ——即终端结点(没有后继)
E
F G HI J
森林 ——指m棵不相交的树的集
合(例如删除A后的子树个数) K
——仍然有顺序存储、链式存储等方式。
讨论2：树的顺序存储方案应该怎样制定？ 可否规定为： 从上至下、从左至右将树的结点依次存入内存。
有重大缺陷： 复原困难
不能唯一复原就没有实用价值！
可讨用论多3：重树链的表链：式一存个储前方趋案指应针该，怎n样个制后定继？指针。
细节问题： 树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？
凹入表示法
又称目录表示法
左孩子－右兄弟表示法
data 左孩子 右兄弟
A
B
C
D
E
F
G
HI
J
K
L
M
意义：多叉树转为二叉树！
树转二叉树举例：
方法：加线—抹线—旋转
兄弟相连
长兄为父
a
b
c
i
d
e
f
g
h
特点是？ 根结点没有右孩子！
孩子靠左 a
b
d
c
e
i
f g h
讨论：二叉树怎样还原为树？
要点：逆操作，把所有右孩子变为兄弟！
② Dj∩Dk= Φ //关于子树不相交的说明
③ ……
//关于数据元素的说明
基本操作 P：//至少有15个，如求树深，求某结点的双亲 }ADT Tree
6.1.3 树的逻辑结构
特点： 一对多（1:n），有多个直接后继（如家谱 树、目录树等等），但只有一个根结点， 且子树之间互不相交。
6.1.4 树的存储结构 讨论1：树是非线性结构，该怎样存储？
目录
第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序
第6章 树和二叉树（Tree & Binary Tree）
特点：非线性结构，一个直接前驱，但可能有多个 直接后继。（一对多，或称1:n）
6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用
A
结点 ——即树的数据元素 结点的度——结点挂接的子树数
B
C
D
E
F G HI J
ቤተ መጻሕፍቲ ባይዱ
（有几个直接后继就是几度，亦称“次数”）K
L
F
结点的层次 ——从根到该结点的层数（根结点算第一层） 终端结点 ——即度为0的结点，即叶子 分支结点 ——即度不为0的结点（也称为内部结点）
树的度 ——所有结点度中的最大值（Max{各结点的度}） 树的深度——指所有结点中最大的层数（Max{各结点的层次}） (或高度)
L
F
有序树 ——结点各子树从左至右有序，不能互换（左为第一）
无序树 ——结点各子树可互换位置。
双亲 ——即上层的那个结点(直接前驱) 孩子 ——即下层结点的子树的根(直接后继) 兄弟 ——同一双亲下的同层结点（孩子之间互称兄弟） 堂兄弟 ——即双亲位于同一层的结点（但并非同一双亲） 祖先 ——即从根到该结点所经分支的所有结点 子孙 ——即该结点下层子树中的任一结点
问：右上图中的结点数＝13；树的度＝ 3；树的深度＝ 4
树的抽象数据类型定义 （见教材P118-119）
ADT Tree{ 数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 若D为空集，则称为空树；//允许n=0
若D中仅含一个数据元素，则R为空集；
其他情况下的R存在二元关系：
① root 唯一 //关于根的说明
a
a
b
d
c
e
i
f g h
b
c
i
d
e
f gh
6.1.5 树的运算
要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难
实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序
等，但这些操作必须建立在对树结点能够“遍历”的 基础上！ 遍历——指每个结点都被访问且仅访问一次，不遗漏不重复
本章重点： 二叉树的表示和实现
定义：是n（n≥0）个结点的有限集合，由一个根结点以及两 棵互不相交的、分别称为左子树和右子树的二叉树组成 。
逻辑结构： 一对二（1:2）
基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。
基本形态：
问：具有3个结点的二叉树可能有几种不同形态？有5种
一般的树 有几种？
整理ppt
20
二叉树的抽象数据类型定义（见教材P121-122）
ADT BinaryTree{
数据对象D: D是具有相同特性的数据元素的集合。
数据关系R: 若D=Φ，则R= Φ ；
意义：把一般的树转化为最简单、最有规律 的二叉树再研究，然后设法从二叉树再转回 多叉树。
图形表示法
湖北理工学院
根
计算机系
教师
学生
其他人员
计算机系 控制系 … …
……
2005级 2006级 2007级 2008级
子树
叶子
嵌套集合表示法
广义表表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 约定： 根作为由子树森林组成的表的名字写在表的左边