文档介绍：概述
图
查找
排序

第二章常用的数据结构及其运算
概述

树与二叉树
数组
栈与队列
线性表
树与二叉树
数据结构:
线性结构:……(线性表、栈、队列等等。)
非线性结构:至少存在一个数据元素有不止一个直接前驱或直接后继(树、图)。

一、树的定义基本术语
树是由 n(n>=0)个数据元素组成的有限集合(记为T),对于任意一棵树T:
(1) 存在唯一一个称为根的数据元素;
(2) 当 n>1时其它数据元素可分为m(m>0)个互不相交的有限集合 T1,T2,…,Tm,而其中每个集合Ti(i=1,2,…,m)本身又是一棵树,并称Ti是根的子树。

树的结点(node) :树中的数据元素和指向其子树的分支。
结点的度(degree):一个结点的子树的个数称为该结点的度,度为0 的结点称为叶结点
树的度:树的所有结点中最大的度称为树的度。
结点的层次(level):根结点为第一层,其他任何结点的层数等于它的父结点的层数加1。
树的深度( depth ) :树的所有结点中最大的层次称为树的深度或高度。
森林(Forest ) :m (m≥0)棵互不相交的树的集合。
一、树的定义基本术语

二、二叉树及其性质
1、二叉树的定义
二叉树:是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树,它的特点是:
每个结点最多只有两棵子树,即不存在度大于2的结点。
是有序树,子树有左右之分,不能颠倒。
思考:二叉树和度为2的树有何区别?
A
E
D
C
B
F

2、二叉树的基本性质
【性质1】第i层上最多有2i-1(i>=1)个结点
证明:
当i=1,即根结点,结点数为21-1=1,成立;
假设第i-1层上的结点数最多有2(i-1)-1=2i-2个,则:
由于二叉树中每一个结点度数最大为2,故第i层上结点数至多为i-1层上结点数的2倍,即2×2i-2=2i-1。
由归纳法,性质得证。
二、二叉树及其性质

【性质2】深度为h的二叉树最多有2h-1个节点
证明:
利用性质(1)的结论,在深度为h的二叉数中至多含有的结点数:
二、二叉树及其性质

【性质3】二叉树中,若有n0个叶子结点, n2个度为2的结点,则必有n0=n2+1
证明:设n1为度为1的结点数,则总结点数n为:
n=n0+n1+n2
在二叉树中除根结点外,其他n-1个结点都是度为1或度为 2 的结点的孩子,度为1的结点有一个孩子,度为 2 的结点有 2个孩子,因而又有:
n-1 =n1+2×n2

n0=n2+1
二、二叉树及其性质

3、几种特殊形式的二叉树
(1)满二叉树:深度为k, 结点个数为2k-1 的二叉树。
每一层的结点数都达到最大值.
没有度为1的结点(只有度为0和2的结点),叶子都分布在最后一层上。
编号: 自上而下,自左至右。
二、二叉树及其性质
k=4
n=24-1=15

(2)完全二叉树
如果一棵有n个结点的二叉树,按与满二叉树相同的方式对结点进行编号,若树中n个结点和满二叉树1~n编号完全一致,则称该树为完全二叉树。
二、二叉树及其性质