第六章二叉树和树 6.1树的基本概念 6.2二叉树 63二叉树遍历和线索二叉树 6.4树和森林 6.5*树的等价问题/树的应用 6.6霍夫曼树及其应用 是3 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历和线索二叉树 6.4树和森林 6.5 *树的等价问题/树的应用 6.6霍夫曼树及其应用
6.1树的基本概念 A , B D F H 四测刚木悦：州十H川丁丁石以的取八云人姒 是 ypb@ustc.edu.cn 2 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 树的定义 （无序树） n(n>=0)个数据元素（结点）的有限集D，若D为空集， 则为空树。否则： 在D中存在唯一的称为根的数据元素 当n>1时，其余结点可分为m（m>0）个互不相交的 有限子集T1，T2，......，Tm，其中每个子集本身又 是一颗树，并称为根的子树 结点间关系: 孩子，双亲，兄弟，堂兄弟，祖先，子 孙 结点的度：子树(孩子)的个数 叶子结点：度为0结点；（终端结点、分支结点） 层次：根的层次为1，层次为k的结点其孩子层次为 k+1 树的深度：树中叶子结点的最大层次数 6.1树的基本概念
S ADT Tree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系：若D为空或一个元素时，R为空集。否则R={H,H 是如下二元关系： 1)在D中存在唯一元素称根root,它在关系H下无前驱； 2)若D-{root}≠φ，则存在D-{root)的一个划分D1,D2,.Dm(m>0) 对任意j≠k(1j,k≤m)有D∩Dk=中，且对任意i(1≤i≤ m),存在唯一元素x∈D,有∈H; 3)对应于D-{root的一个划分，H-{,.,}有唯 一的一个划分H1,H2.Hm(m>0),对任意j≠k（1≤j,k≤m） 有H∩H=b,且对任意i(1≤i≤m),H是Di上的二元关系， (Di,{Hi)是一个符合本定义的树，称根root的子树。 基本操作： ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 ADT Tree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系：若D为空或一个元素时，R为空集。否则R={H}，H 是如下二元关系： 1）在D中存在唯一元素称根root，它在关系H下无前驱; 2）若D-{root}≠ɸ,则存在D-{root}的一个划分D1 ,D2 ,…Dm(m>0), 对任意j≠ k（1≤j,k ≤ m）有Dj∩Dk=ɸ,且对任意i(1 ≤ i ≤ m),存在唯一元素xi∈Di ,有∈H; 3)对应于D-{root}的一个划分，H-{,…,}有唯 一的一个划分H1 ,H2 ,…Hm(m>0),对任意j≠ k（1≤j,k ≤ m） 有Hj∩Hk=ɸ,且对任意i(1 ≤ i ≤m),Hi是Di上的二元关系， （Di,{Hi}）是一个符合本定义的树，称根root的子树。 基本操作：
InitTree(&T); Assign(&T,cur e,val); Destroy Tree(&T): Parent(T,cur e); CreateTree(&T.definition): FirstChild(T,cur_e); ClearTree(&T); RightSibling(T,cur_e); TreeEmpty(T); InsertChild(&T,p,i,c); TreeDepth(T); DeleteChild(&T,p,i); Root(T); TraverseTree(T); Value(T,cur e); //ADT Tree ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 InitTree(&T); DestroyTree(&T); CreateTree(&T,definition); ClearTree(&T); TreeEmpty(T); TreeDepth(T); Root(T); Value(T,cur_e); }//ADT Tree Assign(&T,cur_e,val); Parent(T,cur_e); FirstChild(T,cur_e); RightSibling(T,cur_e); InsertChild(&T,p,i,c); DeleteChild(&T,p,i); TraverseTree(T);
6.2二叉树 6.2.1二叉树定义(binary Tree) n个元素的有限集，或为空集，或含有唯一的根元素， 其余元素分成两个互不相交的子集，每个子集本身也 是一颗二叉树。分别称为根的左子树、右子树，集合 为空的二叉树称空树 二叉树的元素又称结点 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 - 结点的度：非空子树的个数 -叶子结点：左右子树均空的结点；度为零 层次：根的层次为1，层次为k的结点其孩子层次为k+1 二叉树的深度：二叉树中叶子结点的最大层次数 ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 6.2.1二叉树定义（binary Tree） – n个元素的有限集，或为空集，或含有唯一的根元素， 其余元素分成两个互不相交的子集，每个子集本身也 是一颗二叉树。分别称为根的左子树、右子树，集合 为空的二叉树称空树 – 二叉树的元素又称结点 – 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 – 结点的度：非空子树的个数 – 叶子结点：左右子树均空的结点；度为零 – 层次：根的层次为1，层次为k的结点其孩子层次为k+1 – 二叉树的深度：二叉树中叶子结点的最大层次数 6.2二叉树
-满二叉树(full binary tree):所有非叶子结点度为2， 叶子结点在同一层次 -完全二叉树(complete binary tree):深度h,h-l为 满二叉树，h层的结点都集中在左侧 一二叉树的基本操作 (a)满二叉树 (b)完全二叉树 ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 •LeftSibling(T,e) •RightSibling(T,e) •InsertChild(T,p,LR,C) •DeleteChild(T,p,LR) •PreOrderTraverse(T,visit()) •InOrderTraverse(T,visit()) •PostOrderTraverse(T,visit()) •Traverse(T) •InitBiTree(&T) •DestroyBiTree(&T) •CreateBiTree(&T,definition) •BiTreeEmpty(T) •BiTreeDepth(T) •Parent(T,e) •LeftChild(T,e) •RightChild(T,e) – 满二叉树（full binary tree）：所有非叶子结点度为2， 叶子结点在同一层次 – 完全二叉树（complete binary tree）：深度h，h-1为 满二叉树，h层的结点都集中在左侧 – 二叉树的基本操作
6.2.2二叉树的几个基本性质 ,性质1在二叉树的第层的结点个数最多2(1) 。 性质2深度为k的二叉树的最大结点数为2k1 性质3任一二叉树T,如果其叶子结点数为no, 度 为2的结点数为n2,则n=n2+1 no+n1+n2=n=2n2+n1+1 ·性质4具有n个结点的完全二叉树深度为logn+1 「log(n+1) ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 • 性质1 在二叉树的第i层的结点个数最多2 (i-1) • 性质2 深度为k的二叉树的最大结点数为2 k -1 • 性质3 任一二叉树T，如果其叶子结点数为n0， 度 为2的结点数为n2，则n0=n2+1 n0+n1+n2=n=2n2+n1+1 • 性质4 具有n个结点的完全二叉树深度为logn+1 log(n+1) 6.2.2二叉树的几个基本性质
性质5如果对一个有n个结点的完全二叉树T的结 点按层序（从第一层到第logn]+1层，层内从左到 右)从1开始编号，则对任意一个编号为11,则其双亲结点Parent(i)的编号为[i/2] -如果2心n,则编号为i的结点没有左孩子，为叶子结 点；否则其左孩子LChild(i)的编号为2i 如果2+1>n,则编号为i的结点没有右孩子；否则其 右孩子RChild(i)的编号为2i+1 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 • 性质5 如果对一个有n个结点的完全二叉树T的结 点按层序（从第一层到第[logn]+1层，层内从左到 右）从1开始编号，则对任意一个编号为i(11，则其双亲结点Parent(i)的编号为[i/2] – 如果2i>n，则编号为i 的结点没有左孩子，为叶子结 点；否则其左孩子LChild(i)的编号为2i – 如果2i+1>n，则编号为i 的结点没有右孩子；否则其 右孩子RChild(i)的编号为2i+1
6.2.3二叉树的存储结构 顺序存储结构 Const MAXSIZE=100 A B F 01234567 01234567 ()完全二叉树 (b)一般二叉树 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 • 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data; int nodenum; }SqBiTree 6.2.3二叉树的存储结构
root A 链式存 -二叉 A B 域，找父亲 必须} N 囚 - 三叉 rent四个域， 找父 H囚 (a)二叉链表 root rchild da 结点结构 Ichild data rchild A (a)结点 结点结构 AGA )三又链表 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 • 链式存储结构 – 二叉链表 包涵data，lchild，rchild三个域，找父亲 必须从根开始 – 三叉链表 包涵data，lchild，rchild，parent四个域， 找父亲容易 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;