数据结构树-二叉树的定义和二叉树性质与存储本

第六章树和二叉树（一）6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7

树和森林的遍历6.8哈夫曼树与哈夫曼编码数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：树的类型定义

基本操作：查找类

插入类删除类

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(&T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树基本术语树（Tree)：是n个结点的有限集（n>=0)。在任意一棵非空树中，有且仅有一个特定的称为根的结点（root)；当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合Ti本身又是一棵符合本定义的树，并且称为根root的子树。ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),D(H,I,J(M)))T1T3T2树根例如:1、结点:2、结点的度:3、树的度:4、叶子结点:5、分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM（终端结点）（非终端结点）6、(从根到结点的)路径：7、孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点8、结点的层次:9、树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，依次加1树中叶子结点所在的最大层次树的示意图：根结点叶子结点分支结点子树子树子树Level1Level2Level3Level4结点的层次任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点

F被称为子树森林10、森林：是m（m≥0）棵互不相交的树的集合。ArootBCDEFGHIJMKLF(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，否则就成为另一棵树了。子树之间存在确定的次序关系。无序树：树中结点的各子树之间的先后次序无意义，可以互换。子树之间不存在确定的次序关系。二叉树的类型定义二叉树是树的基础，一般的树可以转化为二叉树来处理。1、二叉树的定义：

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成（即左、右子树次序不能颠倒）。ABCDEFGHK根结点左子树右子树2、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树

二叉树的主要基本操作：查找类插入类删除类

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

InitBiTree(&T);Assign(&T,&e,value);CreateBiTree(&T,definition);InsertChild(&T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(&T,p,LR);二叉树的重要特性

性质1

：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对所有的j，1≤j

i，命题成立；由归纳假设知：第i-1层上至多有2i-2个结点。又因为二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1

。性质2

：

深度为i的二叉树上至多有2i-1个结点（i≥1）。证明：[证明用求等比数列前i项和的公式]

基于上一条性质，深度为i的二叉树上的结点数至多为

20+21+

+2i-1=2i-1

。

性质3

：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为

2

的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。两类特殊形态的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij性质4

：

具有n个结点的完全二叉树的深度为

log2n+1。证明：设完全二叉树的深度为k，则由性质2和完全二叉树的定义知：深度为k-1的二叉树应该是一棵满二叉树，故结点数为2k-1-1；深度为k的完全二叉树当为满二叉树时结点数最多为2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即

k-1≤log2n<k因为k只能是整数，因此，k=log2n

+1。性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1

至n

的编号，则对完全二叉树中任意一个编号为i

的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。6.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示（适合存储完全二叉树）即用一组地址连续的存储单元依次从上至下，从左至右存储完全二叉树上的结点元素。也就是说，将完全二叉树上编号为i的结点存放在数组下标为（i-1)的分量中。若要存储一棵一般的二叉树，结点的存放应与完全二叉树上的结点对照，存储在数组的相应分量中。用“0”表示不存在该结点。可能会浪费很多存储空间，单支树就是一个极端情况。一、二叉树的顺序存储表示完全二叉树的数组表示一般二叉树的数组表示数组表示顺序存储的C语言描述#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点ADEBCFrootlchilddatarchild结点结构1.二叉链表二、二叉树的链式存储表示二叉链表的C语言描述typedefstruct

BiTNode

{

//结点结构

TElemTypedata;

struct

BiTNode

*lchild,*rchild;

//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:ADEBCFroot2．三叉链表parent

lchilddatarchild结点结构三叉链表的C语言描述typedefstructTriTNode{