第6章二叉树和树 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第6章树和二叉树 胡建华 2021/2/19 计算机教研室 第 1 页 第 6 章 二叉树和树
树型结构是一类重要的非线性结构。树型结 构是结点之间有分支,并且具有层次关系的结构, 它非常类似于自然界中的树。树结构在客观世界 中是大量存在的。例如家谱、行政组织机构都可 用树形象地表示。 树结构在计算机领域中也有着广泛的应用, 例如在编译程序中,用树结构来表示源程序的语 8法结构;在数据库系统中,可用树结构来组织信 意息;在分析算法的行为时,可用树结构来描述其 执行过程等等。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第2页 树型结构是一类重要的非线性结构。树型结 构是结点之间有分支，并且具有层次关系的结构， 它非常类似于自然界中的树。树结构在客观世界 中是大量存在的。例如家谱、行政组织机构都可 用树形象地表示。 树结构在计算机领域中也有着广泛的应用， 例如在编译程序中，用树结构来表示源程序的语 法结构；在数据库系统中，可用树结构来组织信 息；在分析算法的行为时，可用树结构来描述其 执行过程等等
6.1二叉树 二叉树在树结构的应用中起着非常重要的作 用,因为对二叉树的许多操作算法简单,而任何 树都可以与二叉树相互转换,这样就解决了树的 存储结构及其运算中存在的复杂性。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第3页 6.1 二叉树 二叉树在树结构的应用中起着非常重要的作 用，因为对二叉树的许多操作算法简单，而任何 树都可以与二叉树相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性
6.1.1二叉树的定义 ·二叉树( Binary Tree)是由n(n≥0)个结点的 有限集合构成,此集合或者为空集,或者由 个根结点及两棵互不相交的左右子树组成,并 且左右子树都是二叉树 ·这是一个递归定义。二叉树可以是空集合,根 章和吕风街 可以有空的左子树或空的右子树 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第4页 6.1.1 二叉树的定义 • 二叉树（Binary Tree）是由n(n≥0)个结点的 有限集合构成，此集合或者为空集，或者由一 个根结点及两棵互不相交的左右子树组成，并 且左右子树都是二叉树。 • 这是一个递归定义。二叉树可以是空集合，根 可以有空的左子树或空的右子树
@基本术语 结点(node)表示树中的元素, 包括数据项及若干指向其子树的 分支 结点的度( degree)结点拥有的 子树数 叶子ean)度为0的结点 ·的子子的为①画间画 双亲( parents)孩子结点的上层 结点叫该结点的~ 意·兄弟bing)同一双亲的孩子 ,树的度一棵树中最大的结点度数 结点的层次(evel)—从根结点算起,根为第一层,它的孩子为第二 层 深度( depth)树中结点的最大层次数 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第5页 基本术语 • 结点(node)——表示树中的元素， 包括数据项及若干指向其子树的 分支 • 结点的度(degree)——结点拥有的 子树数 • 叶子(leaf)——度为0的结点 • 孩子(child)——结点子树的根称为 该结点的孩子 • 双亲(parents)——孩子结点的上层 结点叫该结点的~ 1 2 3 11 4 5 8 9 12 6 7 10 •兄弟(sibling)——同一双亲的孩子 •树的度——一棵树中最大的结点度数 •结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二 层…… •深度(depth)——树中结点的最大层次数
@二叉树的5种形式 二叉树结点的子树要区分左子树和右子树,即使只有一棵 子树也要进行区分,说明它是左子树,还是右子树。这是二 叉树与树的最主要的差别。下图列出二差树的5种基本形态, 图(C)和图(d)是不同的两棵二叉树 A A A A B B B C e 章和吕风街 回空二又树根和空的左根和左子树根和右子树 根和左右子树 二叉树的5种形式示意 计算机教研宦 第6页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第6页 二叉树结点的子树要区分左子树和右子树，即使只有一棵 子树也要进行区分，说明它是左子树，还是右子树。这是二 叉树与树的最主要的差别。下图列出二差树的5种基本形态， 图(C) 和图（d）是不同的两棵二叉树。 (a) 空二叉树 A A B A B A C B (b) 根和空的左 右子树 (c) 根和左子树 (d) 根和右子树 (e) 根和左右子树 二叉树的5种形式示意 二叉树的5种形式
⑨特殊形态的二叉树:满二叉树、完全二叉树 1、满二叉树(Fu1 Binary Tree) 棵深度为k且由2k-1个结点组成的二叉树称为满二 叉树。下图就是一棵满二叉树,对结点进行了顺序编号。 2 4 6 满二叉树示例 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第7页 1、满二叉树(Full Binary Tree) 一棵深度为k且由2 k -1个结点组成的二叉树称为满二 叉树。下图就是一棵满二叉树，对结点进行了顺序编号。 满二叉树示例 2 4 5 3 6 7 1 特殊形态的二叉树：满二叉树、完全二叉树
@2、完全二叉树( Complete Binary Tree) 如果一棵二叉树各层都是“满的”,只是最下一层从 右边起连续缺少几个结点,称此二叉树为完全二叉树。 可见,满二叉树是完全二叉树的特例。 1 465(6(4(7 完全二叉树示例 非完全二叉树示例 计算机教研宦 第8页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第8页 2、完全二叉树(Complete Binary Tree) 如果一棵二叉树各层都是“满的”，只是最下一层从 右边起连续缺少几个结点，称此二叉树为完全二叉树。 可见，满二叉树是完全二叉树的特例。 1 2 3 5 6 完全二叉树示例 4 1 2 3 4 5 7 1 2 3 6 7 非完全二叉树示例
满二叉树: 2 ③⑨@④① 完全二叉树: ⑨⑩⑩⑩
满二叉树： 完全二叉树： 1 2 4 5 8 9 10 11 3 6 7 12 13 14 15 1 2 4 5 8 9 10 11 3 6 7 12
@二叉树的操作 、建立一棵空二叉树: Initialbtree(BT) 初始条件:无; 操作结果:构造一棵空树BT。 2、按某种规则建立一棵二叉树: CreateBTree(BT) 初始条件:无; 操作结果:按某种规则构造一棵二叉树BT。 3、求二叉树BT的树根结点: RootBTree ( bt) 初始条件:二叉树BT已存在; 操作结果:返回二叉树BT的根结点。 、求二叉树BT中结点p的双亲: ParentBTree(BT,p) 初始条件:二叉树BT已经存在,且p是二叉树BT中的一个结点; 操作结果:若结点p不是二叉树BT的根结点,则返回结点p的双亲结点; 否则,返回NULL 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第10页 二叉树的操作 1、建立一棵空二叉树：InitialBTree(BT) 初始条件：无； 操作结果：构造一棵空树BT。 2、按某种规则建立一棵二叉树：CreateBTree(BT) 初始条件：无； 操作结果：按某种规则构造一棵二叉树BT。 3、求二叉树BT的树根结点：RootBTree(BT) 初始条件：二叉树BT已存在； 操作结果：返回二叉树BT的根结点。 4、求二叉树BT中结点p的双亲：ParentBTree(BT，p) 初始条件：二叉树BT已经存在，且p是二叉树BT中的一个结点； 操作结果：若结点p不是二叉树BT的根结点，则返回结点p的双亲结点； 否则，返回NULL