数据结构第6章复习线性结构：数据与数据之间的关系
第一个元素，无前驱，有一个后继最后一个元素，有一个前驱，无后继中间的任何一个元素有一个前驱和一个后继
第6章树与二叉树树型结构是一类重要的非线性结构。其中以树和二叉树最为常用。树是以分支关系定义的层次结构。
树型结构在客观世界中广泛存在，如人类社会的族谱和各种社
会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构；又如在数据库系统中，
树形结构也是信息的重要组织形式之一。
一
、树的定义与基本术语1.树的基本概念树：是n(n≥0)个结点的有限集。在任意一棵非空树中：（1）有且仅有
一个特定的称为根的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又
是一棵树，并且称为根的子树。空树：无结点的树（n=0）
ABCDEFGHIJMKLAT1T3T2树根例如:
T1T2T3(B(E,F
(K,L)),C(G),D(H,I,J(M)))线
性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点
(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)2.对比树型结构和线性结构的结构
特点3.树的基本术语结点:数据元素+若干指向子树的分支结点的度:分支的个数树的度:树中所有结点的度的最大值叶子结
点:度为零的结点分支结点:度大于零的结点
D
HIJM孩子结点双亲结点兄弟结点祖先结点子孙结点(从根到结点的)路径：由从根到该结点所经分
支和结点构成。结点的层次:假设根结点的层次为1，第l层的结
点的子树根结点的层次为l+1树的深度：树中叶子结点所在的最大层次。森林：是m（m≥0）棵互不相交的树的集合。
ABCDEFGHIJMK
LABCDEFGHIJMKL二、二叉树1.二叉树的定义二叉树是另一种树型结构，它的
特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
ABCDEFGHK根结点左子树右
子树2.二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为
空树3.二叉树的抽象数据类型定义ADTTree{数据对象D：D是具有相同特性的数据元素的集
合。数据关系R：若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素roo
t；(2)当n>1时，其余结点可分为2个互不相交的有限集T1,T2，其中每一棵子集本身又是一
棵符合本定义的二叉树，T1称为根root的左子树，T2称为根root的右子树。
二叉树的主要基本操作：Root(T);
Value(T,e);Parent(T,e);LeftChild(T,e);Righ
tChild(T,e);LeftSibling(T,e);RightSibling(T,e);
BiTreeEmpty(T);BiTreeDepth(T);PreOrderTravers
e(T,Visit());InOrderTraverse(T,Visit());PostOrd
erTraverse(T,Visit());LevelOrderTraverse(T,Visit());
InitBiTree(&T);Ass
ign(T,&e,value);CreateBiTree(&T,definition);InsertChil
d(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);Del
eteChild(T,p,LR);
4.二叉树的性质（1）性质1在二叉树的第i层上至多有2i-1个结点（i≥1)。用归纳法证明：归
纳基：i=1层时，只有一个根结点：2i-1=20=1；归纳假设：
假设对所有的j，1≤j?i，命题成立；归纳证明：二叉树上每个结点至多有两棵子树，则第i层的结点数=2
i-2?2=2i-1。
（2）性质
2深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉
树上的结点数至多为20+21+??????+2k-1=2k-1。（3）性质3对任何一棵二叉
树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：
设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2
而b=n-1=n0+n1+n2-
1由此，n0=n2+1。
两类特殊的二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。
完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。
1234567891011121
3141512345678910111213141234567891011
12131415cfgabdehij12345678910jdfgab
dehi12345678910（4）性质4具有n个结点的完全二叉树的深度为?l
og2n?+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k即
k-1≤log2n
（5）性质5若对含n个结点的完全二叉树从上到下且
从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，
否则，编号为?i/2?的结点为其双亲结点；(2)若2i>n，则该结点无左孩子，否则，编号为2i的
结点为其左孩子结点；(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。完全
二叉树中双亲结点与其左孩子结点、右孩子结点编号值的关系。i2i2i+1三、二叉树的存储结构1.顺序存储结构所
谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。为了能唯一确定结点与结点之间的关系，在此约定：按照完全二叉树从
上至下、从左到右对结点从1开始连续编号，编号为i的结点存储在数组下标为i-1的单元中。二叉树的特点可知，完全二叉树和满二叉树采用
顺序存储比较合适
例如:ABECFH25137DIGJ468910ABCDEFGHIJ012345678910111213 |
|
