当前位置：文档之家 › ch6树和二叉树

ch6树和二叉树

  • 格式：ppt
  • 大小：1.92 MB
  • 文档页数：74

下载文档原格式

  / 74

合集下载

二叉树知识点总结

二叉树知识点总结

二叉树知识点总结1. 二叉树的性质1.1 二叉树的性质一：二叉树的深度二叉树的深度是指从根节点到叶子节点的最长路径长度。

对于一个空树而言，它的深度为0；对于只有一个根节点的树而言，它的深度为1。

根据定义可知，深度为k的二叉树中，叶子节点的深度值为k。

由此可知，二叉树的深度为所有叶子节点深度的最大值。

1.2 二叉树的性质二：二叉树的高度二叉树的高度是指从根节点到叶子节点的最短路径长度。

对于一个空树而言，它的高度为0；对于只有一个根节点的树而言，它的高度为1。

由此可知，二叉树的高度总是比深度大一。

1.3 二叉树的性质三：二叉树的节点数量对于一个深度为k的二叉树而言，它最多包含2^k - 1个节点。

而对于一个拥有n个节点的二叉树而言，它的深度最多为log2(n+1)。

1.4 二叉树的性质四：满二叉树满二叉树是一种特殊类型的二叉树，它的每个节点要么是叶子节点，要么拥有两个子节点。

满二叉树的性质是：对于深度为k的满二叉树而言，它的节点数量一定是2^k - 1。

1.5 二叉树的性质五：完全二叉树完全二叉树是一种特殊类型的二叉树，它的所有叶子节点都集中在树的最低两层，并且最后一层的叶子节点从左到右依次排列。

对于一个深度为k的完全二叉树而言，它的节点数量一定在2^(k-1)和2^k之间。

2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。

二叉树的遍历主要包括前序遍历、中序遍历和后序遍历三种。

2.1 前序遍历（Pre-order traversal）前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

对于一个二叉树而言，前序遍历的结果就是按照“根-左-右”的顺序访问所有节点。

2.2 中序遍历（In-order traversal）中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

对于一个二叉树而言，中序遍历的结果就是按照“左-根-右”的顺序访问所有节点。

2.3 后序遍历（Post-order traversal）后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

二叉树——精选推荐

二叉树——精选推荐

⼆叉树⼆叉树 是n（n>=0）个结点的有限集合，该集合或者为空集（空⼆叉树），或者由⼀个根节点和两棵互不相交的、分别称为根节点的左⼦树和右⼦树的⼆叉树组成。

⼆叉树特点： 1）每个结点最多有两颗⼦树，所以⼆叉树中不存在度⼤于2的结点。

2）左⼦树和右⼦树是有顺序的，次序不能任意颠倒。

3）即使树中某结点只有⼀颗⼦树，也要区分是左⼦树还是右⼦树。

⼆叉树具有五种基本形态： 1）空⼆叉树 2）只有⼀个根结点 3）根结点只有左⼦树 4）根结点只有右⼦树 5）根结点既有左⼦树⼜有右⼦树。

三个结点的⼆叉树有5种形态：特殊⼆叉树：1.斜树 顾名思义，斜树⼀定是斜的，但是往哪还是有讲究的。

所有的结点都只有左⼦树的⼆叉树叫做左斜树。

所有的结点都只有右⼦树的⼆叉树叫做右斜树。

斜树有很明显的特点就是每⼀层都只有⼀个结点。

结点的个数与⼆叉树的深度相同。

左斜树 右斜树2.满⼆叉树 在⼀颗⼆叉树中，如果所有分⽀结点都存在左⼦树和右⼦树，并且所有叶⼦都在同⼀层上，这样的⼆叉树称为满⼆叉树。

单是每个结点都存在左右⼦树，不能算是满⼆叉树，还必须要所有的叶⼦都在同⼀层上，这就做到了整棵树的平衡。

因此，满⼆叉树的特点有： 1）叶⼦只能出现在最下⼀层。

出现在其它层就不可能达成平衡。

2）⾮叶⼦结点的度⼀定是2. 3）在同样深度的⼆叉树中，满⼆叉树的结点个数最多，叶⼦数最多。

3.完全⼆叉树 对⼀颗具有n个结点的⼆叉树按层序编号，如果编号为i（1 <= i <= n）的结点与同样深度的满⼆叉树中编号为i的结点在⼆叉树中位置完全相同，则这棵⼆叉树称为完全⼆叉树。

如图⽰：⼆叉树性质：性质1：在⼆叉树的第i层⾄多有2i-1个结点（i >= 1）。

性质2：深度为K的⼆叉树⾄多有2k-1个结点（k >= 1)。

性质3：对任何⼀颗⼆叉树T，如果其终端结点数为n0,度为2的结点树为n2,则n0 = n2 + 1。

性质4：具有n个结点的完全⼆叉树的深度为|log2n| + 1 (|x|表⽰不⼤于x的最⼤整数）。

《二叉树的概念》课件

《二叉树的概念》课件
过程中进行一些特定的操作。
05
二叉树的应用
Chapter
在数据结构中的应用
二叉搜索树
二叉搜索树是一种特殊的二叉树，它的每个节点的左子树上的所有元素都小于 该节点，右子树上的所有元素都大于该节点。这种数据结构可以用于快速查找 、插入和删除操作。
AVL树和红黑树
这两种二叉树都是自平衡二叉搜索树，它们通过调整节点的左右子树的高度来 保持树的平衡，从而在插入、删除等操作时具有较好的性能。
VS
详细描述
平衡二叉树的特点是，它的左右子树的高 度差不会超过1，且左右子树都是平衡二 叉树。平衡二叉树的性质还包括，它的所 有叶节点的层数相等，且所有非叶节点的 左右子树的高度差不超过1。平衡二叉树 的查找、插入和删除操作的时间复杂度为 O(log n)，其中n为节点数。
04
二叉树的遍历
Chapter
决策树
在机器学习和人工智能领域，决策树 是一种重要的分类和回归方法。其基 础结构就是二叉树，通过构建决策树 ，可以解决分类和回归问题。
THANKS
感谢观看
代码表示法
总结词：严谨规范
详细描述：使用编程语言的语法结构来表示二叉树，每个节点用对象或结构体表示，节点间的关系通 过指针或引用表示，严谨规范，易于编写和调试。
03
二叉树的性质
Chapter
深度最大的二叉树
总结词
深度最大的二叉树是指具有最大 可能深度的二叉树。
详细描述
在二叉树中，深度最大的二叉树 是满二叉树，即每个层级都完全 填满，没有空缺的节点。满二叉 树的深度等于其节点总数减一。
02
二叉树的表示方法
Chapter
图形表示法
总结词：直观明了
详细描述：通过图形的方式展示二叉树的结构，每个节点用圆圈或方框表示，节 点间的关系用线段表示，直观易懂，易于理解。

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

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

第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是⼆叉树的⼀个节点。

二叉树的知识点

二叉树的知识点

•
后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点
•
层序遍历（Level Order Traversal）：按层级从上到下，从左到右
遍历
二叉搜索树（Binary Search Tree，BST）：
•
二叉搜索树是一种特殊的二叉树，其中左子树的值都小于根节点的
值，右子树的值都大于根节点的值。
二叉树是一种常见的树状数据结构，它由节点组成，每个节点最多有两个子 节点，分别称为左子节点和右子节点。以下是关于二叉树的一些基本知识点：
二叉树的特点：每个节点最多有两个子点，左子节点和右子节点。子节点 的顺序不能颠倒。
二叉树的性质：
•
左子树和右子树都是二叉树。
•
二叉树可以为空树，即没有节点。
•
二叉树可以只有一个节点，没有子节点。
•
二叉搜索树的查找、插入和删除操作具有较高的效率。
平衡二叉树：
•
平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不
超过 1。
•
常见的平衡二叉树有红黑树、AVL 树等，可以提高查找、插入和删
除的效率。
这些是关于二叉树的一些基本知识点，了解它们可以帮助你理解和应用二叉 树数据结构。当然，二叉树还有更多的概念和应用，如平衡二叉查找树、线索二 叉树等，进一步学习可以深入了解。
•
二叉树的子树可以为空。
二叉树的分类：
•
满二叉树：每个节点要么没有子节点，要么有两个子节点。
•
完全二叉树：除了最后一层的节点外，其他层的节点都是满的，并
且最后一层的节点都靠左排列。
二叉树的遍历：
•
先序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树

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-期权定价的离散模型——二叉树模型(上财)

衍生品的价值等于其在风险中性世界的期望收益以无风险利率贴 现的贴现值
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 )可以解释为风险中性的上涨和下跌概率

二 叉 树


下图是1.2中所示的完全二叉树的顺序存储示意图。
例如，bt[3]
3=/12， 即在bt[1]中，其左
孩子在bt[2i]=bt[6]中，右孩子在bt[2i+1]=bt[7]中。
目录
二 叉 树
2）一般二叉树的顺序存储 一般的二叉树采取的办法是按完全二叉树的形式补齐 二叉树所缺少的结点，对补齐后的二叉树进行编号，将二 叉树的原有结点按编号存储到一维数组中。 下图给出了一棵一般二叉树改造后的完全二叉树形态 和其顺序存储状态示意图。
目录
二 叉 树
2021年1月30日星期六
性质3 对于一棵非空的二叉树，如果叶子结点数 为n0，度数为2的结点数为n2，则有n0=n2＋1。
性质4 具有n个结点的完全二叉树的深度k log2n +1。
性质5 对于具有n个结点的完全二叉树，如果按照 」 从上到下和从左到右的顺序对二叉树中的所有结点从1
则ki无左孩子结点，即ki是叶子结点。因此完全二叉
树中编号i＞ n / 2 的结点必定是叶子结点。 （3）若2i+1≤n，则ki的右孩子结点编号是2i+1；
否则ki无右孩子结点。
目录
二 叉 树
2021年1月30日星期六
可用一维数组bt[]存放一棵完全二叉树，将标号 为i的结点的数据元素存放在分量bt[i]中，bt[0]不 用或用来存储结点数目。
typedef struct BiTNode { // 结点结构
ElemType data;
2021年1月30日星期六
目录
二 叉 树
二叉树、树及有序树是有区别的，二叉树不是树的特 例，主要差别在于二叉树的子树有左右之分。
在有序树中，虽然一个结点的孩子之间是有左右次序 的，但若该结点只有一个孩子时，就无须区分其左右次序。

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)。

F G (14)
i 访问：C B E G D F A
访问：C B E G D F
A
p=NULL
B
C D
E
G
F
后序遍历非递归算法 i 访问：C B E G D F A
(15)
Ch5_4.c Ch5_40.C
遍历算法应用
按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C D E G F A
先序序列：A
B D C
printf(C); pre(T L); pre(T R);
T
返回
非递归算法
void inorder(JD *bt) { int i=0; JD *p,*s[M]; p=bt; do { while(p!=NULL) { s[i++]=p; p=p->lchild; } if(i>0) { p=s[--i]; printf("%d\t",p->data); p=p->rchild; } }while(i>0||p!=NULL); }
A
B
左子树为空
C 左、右子树 均非空
空二叉树
只有根结点 的二叉树
右子树为空
二叉树性质 i 2i 1 性质1：在二叉树的第层上至多有 个结点(i 1)
证明：用归纳法证明之 2 i=1时，只有一个根结点，i 1 2 0 1 是对的 j 1 假设对所有j(1j<i)命题成立，即第j层上至多有 2 个结点 那么，第i-1层至多有 2 i 2 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即 2 2 i 2 2 i 1 故命题得证
二叉链表
typedef struct node { datatype data; struct node *lchild, *rchild; }JD;
lchild data rchild
A ^ A B C E G 在n个结点的二叉链表中，有n+1个空指针域 ^ G ^ D F ^ E ^ C B ^ D
特点：
树中至少有一个结点——根
树中各子树是互不相交的集合
只有根结点的树
A
有子树的树
A C F G H
根
B E
D I J
K
L
M
子树
基本术语 结点(node)——表示树中的元素，包括数据项及若干 指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层， 它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m0)棵互不相交的树的集合
返回
6.43 编写递归算法，交换二叉树中所有结点的左右子树 注意：此题不能依中序遍历的次序进行
void swap( BiTree BT )
{ if (BT) {
BT->lchild BT->rchild; swap( BT->lchild);
swap( BT->rchild); } }
返回
线索二叉树 定义：
+ a * e
/ f
b c
d
先序遍历： - + a * b - c d / e f
中序遍历： a + b * c - d - e / f
后序遍历： a b c d - * + e f / 层次遍历：
-+/a*efb-cd
void preorder(JD *bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->lchild); preorder(bt->rchild); } }
p
非递归算法的实现
A
B C E G A p C E G B D F i D i F P->A (1)
p
B C E
A
D
i
F
G
P->B P->A (2)
A B
P->C P->B P->A (3)
C p=NULL E (4)
D F G
i
P->B P->A
访问：C
p B C E
A
B D i C P->A 访问：C B E (6)
二叉树的存储结构 顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数
据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树
a b d f e g
c
1 2 3 4 5 6 7 8 9 10 11 a b c d e 0 0 0 0 f g
链式存储结构
BiTree Build_Bitree(SqList sa) {// 由完全二叉树的顺序存储结构建二叉链表 bt = Build(sa,1); return bt; } BiTree Build(SqList sa, int i){ if (i>st) return NULL; else { b = new BiTNode; // 建根结点 b->data = sa.elem[i]; b->lchild = build(sa,2*i); // 递归建左子树 b->rchild = build(sa,2*i+1); // 递归建右子树 return b; } }//build
结点定义：
typedef struct node { int data; int lt, rt; struct node *lc, *rc; }JD;
lc
lt data rt
rc
T
A
B D 1 B 0
0 A 0
第六章 树和二叉树
树是一类重要的非线性数据结构，是以分支关系定 义的层次结构
6.1 树的定义
定义 定义：树(tree)是n(n>0)个结点的有限集T，其中：
有且仅有一个特定的结点，称为树的根(root)
当n>1时，其余结点可分为m(m>0)个互不相交的有限集
T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的 子树(subtree)
B
C D
E
G P=NULL A B
F
P->D P->A
访问：C B E G (10)
p D i
C F G
B D E F p i P->F P->A 访问：C B E G D
C
E (11)
P->A 访问：C B E G D
(12)
G
p A B A
B D
C i F p=NULL G D
C E
(13)
E P->A
A p D F G i
F
G
P->D P->A
访问：C B
(5)
A
A
i B P->E P->D P->A 访问：C B p C E G D i P->D P->A 访问：C B E (8)
B
C p (7) D
E
G
F
F
A
A i B P->G P->D P->A 访问：C B E (9) p A C E G D F i
^
F
^
三叉链表
typedef struct node lchild data parent rchild { datatype data; struct node *lchild, *rchild, *parent;^
^
^
E
D ^ ^ G F ^
性质2：深度为k的二叉树至多有 2 k 1个结点(k1)
证明：由性质1，可得深度为k 的二叉树最大结点数是
(第i层的最大结点数 2 i 1 2 k 1 )
i 1 i 1
k
k
性质3：对任何一棵二叉树T，如果其终端结点数为n0，
度为2的结点数为n2，则n0=n2+1
前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻
的结点互称为~ 线索：指向前驱或后继结点的指针称为~ 线索二叉树：加上线索的二叉链表表示的二叉树叫~ 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~
实现
在有n个结点的二叉链表中必定有n+1个空链域 在线索二叉树的结点中增加两个标志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驱 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后继
几种特殊形式的二叉树 满二叉树
定义： 一棵深度为 且有2 k k
1个结点的二叉树称为~
特点：每一层上的结点数都是最大结点数
完全二叉树
定义：深度为k，有n个结点的二叉树当且仅当其每一个结点
都与深度为k的满二叉树中编号从1至n的结点一一对应时， 称为~ 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为l，则其左 分支下子孙的最大层次必为l 或l+1 性质 性质4：具有n个结点的完全二叉树的 深度为log n 1
G
^
6.3 遍历二叉树和线索二叉树
遍历二叉树 方法
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树