叶子结点.ppt

树、二叉树
2008赛前知识点梳理
历届试题(选)
(13tg)已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号,以下同),中根遍历是4 2 6 5 1 7 3,则该二叉树的后根遍历是( )。 6 5 2 7 3 1 6 5 2 1 3 7  2 3 1 5 4 7 6 5 3 1 7 2
(12tg_多项)已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号,以下同),后根遍历是3 2 5 6 4 1,则该二叉树的可能的中根遍历是( ) A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
(11tg _多项)二叉树T的宽度优先遍历序列为A B C D E F G H I,已知A是C的父结点,D 是G 的父结点,F 是I 的父结点,树中所有结点的最大深度为3(根结点深度设为0),可知E的父结点可能是( )。 A. A B. B C. C D. D E. F
树状结构是一种重要的非线性结构。它的形状类似于现实中倒立的树,结点间呈现分支和层次关系,能够方便地描述数据之间一对多的联系。
石油大学
计算系
数学专业
数理系
外语系
物理专业
树的基本概念
树是一种重要的非线性数据结构,很象自然界中的树那样,从树根到大分枝、小分枝、直到叶子把数据联系起来,这种数据结构就叫做树结构,简称树。
树中每个分叉点称为结点,起始结点称为根结点,任意两个结点间的连接关系称为树枝,结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲",结点的后趋结点称为该结点的"子女"或"孩子",同一结点的"子女"之间互称"兄弟"。
树结构的特点
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。
树结构(除了一个称为根的结点外)每个元素都有且仅有一个直接前趋,有且仅有零个或多个直接后继。
J
I
A
C
B
D
H
G
F
E
根结点
树形结构常用的术语
根结点:最上层的没有前件结点的结点。
叶子结点:没有后件结点的结点。
内部结点:既有前件结点又有后件结点的结点。
父结点:某一结点的前件结点称为该结点的父结点。
子结点:某一结点的后件结点称为该结点的子结点。
子树:以某个结点的一个子结点为根的树称为该结点的子树。
结点的度:某个结点连接的子结点的个数称为该结点的度。
树的度:一颗树包含的所有结点的度的最大值称为这棵树的度。
树的深度:树的最大层次数称为树的深度。
概念细化
①结点的度和树的宽度
一个结点拥有的子树的个数称为是该结点的度
树的所有结点中的最大度为该树的宽度
②分支结点和叶结点
度为0的结点称为叶结点或端结点
度大于0的结点称作分支结点(根结点除外)
概念细化
③树的深度
在树的结构中,结点的层数从树根开始定义,根结点在第一层,其子结点在第二层,以此类推。树中结点最大的层号为树的深度。
④有序树和无序树
若结点的子树有次序排列,且先后次序不能互换,这样的树称为有序树,反之为无序树。
第一层
第二层
第三层
第四层
A
B
C
D
E
F
G
H
I
J
K
L
M
结点A的度: 3
结点B的度: 2
结点M的度:0
叶子结点:K,L,F,G,M,I,J
结点A的子结点:B,C,D
结点B的子结点:E,F
结点I的父结点: D
结点L的父结点:E
树的度:3
树的深度:4
根结点:A
子树
2. 二叉树的定义
二叉树是一种重要的树状结构。
二叉树是n(n0)个结点的有限集合,具有两个特点:
如果二叉树非空,则有且只有一个根结点;
每个结点最多有两个子结点,分别以这两个子结点作为根结点组成该结点的左子树和右子树。
二叉树的度最大为2。
A
F
G
E
D
C
B
右子树
左子树
根结点