第六章 二叉树和树 6.1二叉树 6.2二叉树遍历 6.3树和森林 6.4树的应用.

Presentation on theme: "第六章 二叉树和树 6.1二叉树 6.2二叉树遍历 6.3树和森林 6.4树的应用."— Presentation transcript:

1 第六章 二叉树和树 6.1二叉树 6.2二叉树遍历 6.3树和森林 6.4树的应用

2 6.1二叉树 6.1.1二叉树的定义和基本术语 二叉树（binary Tree）
二叉树的元素又称结点 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 结点的度：子树的个数 叶子结点：左右子树均空的结点；度为零 层次：根的层次为1，层次为k的结点其孩子层次为k+1 二叉树的深度：二叉树中叶子结点的最大层次数

3 满二叉树（full binary tree）：所有结点度为2，叶子结点在同一层次
完全二叉树（complete binary tree）：深度h，h-1为满二叉树，h层的结点都集中在左侧 二叉树的基本操作 InitBiTree(&T) DestroyBiTree(&T) CreateBiTree(&T,definition) BiTreeEmpty(T) BiTreeDepth(T) Parent(T,e) LeftChild(T,e) RightChild(T,e) LeftSibling(T,e) RightSibling(T,e) InsertChild(T,p,LR,C) DeleteChild(T,p,LR) Traverse(T)

4 6.1.2二叉树的几个基本性质 性质1 在二叉树的第i层的结点个数最多 2 (i-1) 性质2 深度为k 的二叉树的最大结点数为2k-1
性质3 任一二叉树T，如果其叶子结点数为n0， 度为2的结点数为n2，则n0=n n0+n1+n2=n=2n2+n1+1 性质4 具有n个结点的完全二叉树深度为[logn]+1

5 性质5 如果对一个有n个结点的完全二叉树T的结点按层序（从第一层到第[logn]+1层，层内从左到右）从1开始编号，则对任意一个编号为i(1<=i<=n)的结点有：
如果i＝1，则该结点是二叉树的根，无双亲；如果i>1，，则其双亲结点Parent(i)的编号为[i/2] 如果2i>n，则编号为i 的结点没有左孩子，为叶子结点；否则其左孩子LChild(i)的编号为2i 如果2i+1>n，则编号为i 的结点没有右孩子；否则其右孩子RChild(i)的编号为2i+1

6 6.1.2二叉树的存储结构 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data;
int nodenum; }SqBiTree

7 链式存储结构 二叉链表 包涵data，lchild，rchild三个域，找父亲必须从根开始
三叉链表 包涵data，lchild，rchild，parent四个域，找父亲容易       typedef BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;

8 6.2二叉树遍历 6.2.1问题的提出 二叉树遍历 对所有结点进行访问，且仅被访问一次
LDR、LRD、DLR、DRL、RLD、RDL六种次序 先序（根）DLR、中序（根）LDR、后序（根）LRD 例：右图得三种遍历序列 先序遍历：ABDEC 中序遍历：DBEAC 后序遍历：DEBCA A B C D E

9 6.2.2遍历算法的描述 算法6.1 递归实现 算法6.2 非递归实现
算法6.1 递归实现 void preorder(BiTree T,void (* visit)(BiTree)) 算法6.2 非递归实现 typedef enum {Travel=1,Visit=0} TaskType; typedef struct { BiTree ptr; TaskType task; }SElemType; void InOrder_iter (BiTree BT,void (* visit)(BiTree)) 用栈实现遍历

10 6.2.3二叉树应用举例 例6.1 建立二叉树的存储结构－二叉链表 例6.2求二叉树的深度 递归算法 例6.3复制二叉树 递归算法
算法6.3 void CreateBiTree(BiTree &T) 递归 先序 例6.2求二叉树的深度 递归算法 算法6.4 void BiTreeDepth(BiTree T,int h,int &depth)先序 算法6.5 int BiTreeDepth(BiTree T) 后序 例6.3复制二叉树 递归算法 算法6.6 void CopyTree(BiTNode *T) 后序 例6.4求存于二叉树中的数学表达式的值 算法6.7 double Value(BiTree T,float opnd[]) 后序

11 补充6.1：求一二叉树中所有结点数和叶子结点数 （先序）
void Count(BiTree T,int &C1, int &C2) { if(!T)return; C1++; if(T->lchild==NULL && T->rchild==NULL)C2++; count(T->lchild,C1,C2); count(T->rchild,C1,C2); }

12 6.2.4线索二叉树 在二叉链表的结点中增加两个指针域，分别指向“前驱”和“后继”，该指针称线索。加上线索的二叉树成为线索二叉树
typedef BiTHrNode{ ElemType data; struct BiTHrNode *lchild,*rchild; struct BiTHrNode *pred,*succ; }BiTHrNode,*BiThrTree; 线索二叉树的遍历 算法6.8 Void InOrder(BiThrTree T,void (* visit)(BiTree)) 线索二叉树的中序建立 算法6.9 Void InOrderThreading(BiThrTree &H, BiThrTree T) 算法6.10 Void InThreading(BiThrTree p, BiThrTree &pre)

13 6.3树和森林 6.3.1树和森林的定义 树的定义 （无序树） 森林的定义
n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。否则： 在D中存在唯一的称为根的数据元素 当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，......，Tm，其中每个子集本身又是一颗树，并成为根的子树 森林的定义 是m(m>=0)颗互不相交的树的集合

14 树的基本操作： InitTree（&T） DestroyTree（&T） CreateTree(&T,definition)
TreeEmpty(T) TreeDepth(T) Parent(T, e) LeftChild（T，e） Rightsibling(T,e) InsertChild（&T,&p,i,C） DeleteChild（&T,&p,i） Traverse（T）

15 6.3.2 树和森林的存储结构 1）双亲表示法 Const MAX_TREE_SIZE=100 typedef struct PTNode{
Elem data; int parent; }PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r,n; }PTree; 例：前图的双亲存储示意图 r=0 n=11

16 data parent A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F
A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F G H I J K

17 2）孩子链表示法 例：前图孩子链表示，r=0,n=11 typedef struct CTNode{ int child;
struct CTNode *next; }CTNode,*Childptr; typedef struct { Elem data; Childptr firstchild; }CTBox; CTBox nodes[MAX_TREE_SIZE]; int n,r; }CTree; 例：前图孩子链表示，r=0,n=11

18 data pare A 1 B 2 C ^ 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 1 2 3 ^ 4 5 6 ^ A B C D E F G H I J K 7 8 ^ 9 10 ^

19 3）树的二叉链表（孩子－兄弟）表示法 typedef struct CSNode{ Elem data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

20 A A B C D E F G H I J K B E C D F J G H I K

21 树与二叉树的变换 以树的结点为二叉树结点 树根与最左子树的父－子关系改为父－左子关系，去除根与其他子树的父－子关系
将其他各子树根（除最右子树）到其右兄弟之间的隐含关系以父－右子关系表示。 对于无右子树的二叉树可以实施逆变换

22 森林到二叉树的变换：F(T1,T2.....Tn)-> B
若森林F空，则二叉树B空。 由森林中的第一颗树的根结点ROOT（T1）作为二叉树的根，其子树转换为二叉树的左子树。 由森林中其余树构成的森林{T2，T Tn}转化得到的二叉树B的右子树 二叉树到森林的变换：B -> F（T1，T Tn） 若二叉树B空，则森林F空。 二叉树的根为森林中的第一颗树的根结点ROOT（T1），二叉树的左子树转化为T1的子树 二叉树的右子树转化为森林{T2，T Tn}

23 6.3.3 树和森林的遍历 树遍历的三种搜索路径（图6.13） 对森林遍历的两种方法：（图6.19） 先根次序遍历 ABCEHDFG
后根次序遍历 BHECFGDA 按层次序遍历 ABCDEFGH 对森林遍历的两种方法：（图6.19） 先序遍历：(ABCDEFGHIJ) 若森林非空 访问森林中的第一颗树根结点 先序遍历第一颗树中根结点的子树森林 先序遍历除去第一颗树之后剩余树构成的森林 中序遍历：(BCDAFEHJIG) 若森林非空 中序遍历第一颗树中根结点的子树森林 中序遍历除去第一颗树之后剩余树构成的森林

24 树的先根遍历和后根遍历可利用二叉树的先序和中序遍历算法实现 森林的先序遍历和中序遍历即是对应二叉树的先序和中序遍历 例6.5求森林的深度
算法6.11 int TreeDepth(CsTree T) 后序 Max(左分支的森林深度＋1，右分支的森林深度) 例6.6 输出树中从根结点到所有叶子结点的路径 算法6.12（a） void OutPath(CSTree T,Stack &S) 递归用来遍历左分支，即真正的孩子 while循环用来遍历右分支几兄弟 栈底到栈顶为一条路径

25 例6.7 建立树的存储结构――孩子－兄弟链表 算法6.12（b） void OutPath(CSTree T,Stack &S)
注意：仅对www为叶结点的路径输出；输出加“.”分割 例6.7 建立树的存储结构――孩子－兄弟链表 可以按照例6.1的方法先序遍历建立对应的二叉树，输入序列一样。 本例输入是父－子对输入方式 算法6.13 void CreateTree(CSTree T) 循环加队列 按层次遍历

26 6.4树的应用 6.4.1堆排序的实现 排序的实现： typedef SqTable HeapType;
调整为堆 ，从结点[n/2]到1依次调整 交换数据，再调整堆顶元素，恢复成堆 typedef SqTable HeapType; 算法6.14 void HeapAdjust(HeapType &H,int s,int m) 调整H.r[s..m]为大顶堆,其中仅H.r[s]不满足大顶堆条件 算法6.15 void HeapSort(HeapType &H) 从结点[n/2]到1依次调整，使H为大顶堆 交换堆顶与堆底记录，再利用HeapAdjust重新调整为堆 重复进行第二步，知道所有元素有序

27 6.4.2二叉排序树 二叉排序树定义： 或空树，或满足如下特征 若左子树不空，则左子树上的所有结点值均小于根结点值
若右子树不空，则右子树上的所有结点值均大于或等于根结点值 左右子树分别也是二叉排序树

28 利用二叉排序树对顺序表排序 typedef TelemType RcdType; typedef KeyType int;
算法6.16 void Insert_BST(BiTree &T, TElemType e) 在二叉排序树中插入一个结点 【更正】keytype 应为TElemType 利用二叉排序树对顺序表排序 算法6.17 void BSTSort(SqTable &L)

29 补充6.3：求排序二叉树的最大元素 keytype getmax(BiTree &T) { if(!T) errormessage(“NULL Tree,Can’t get value!”); return 0; } p=T; while(p->rchild)p=p->rchild; return p->data.key;

30 6.4.3赫夫曼(huffman)树及其应用 路径：树中一个结点到另一结点之间的分支 路径长度：路径上分支的数目
树的路径长度：树根到每个结点的路径长度之和 结点带权路径长度：从树根到该结点之间的路径长度与该结点上所带权值的乘积 树的带权路径长度：WPL＝Σωklk (叶子结点) 最优二叉树（赫夫曼树）: 给定n个权值{w1,w wn}，构造有n个叶子的二叉树，每个叶子带权wi，其中WPL最小的二叉树

31 例6.8 将百分制转换为五分制 赫夫曼树算法 1)根据给定的n个权值{w1,w wn}，构成n颗二叉树的集合F＝{T1,T Tn}，每个二叉树只有一个带权Wi的根结点。 2)在F中选取两颗根结点的权值最小的树作为左右子树，构造一个新二叉树，且置其根结点的权值为两个子树根结点权值之和。 3)在F中删除这两颗树，同时在F中加入新树。 4)重复2）、3）直至F只含一颗树为止

32 赫夫曼树存储结构 算法6.18 创建赫夫曼树 typedef struct{ int weight;
int lchild,rchild,selected; }HTNode; HTNode *Htree; int root; }HuffmanTree; 算法6.18 创建赫夫曼树 void CreateHuffman(HuffmanTree &HT, int *w,int n)

33 例6.9 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计赫夫曼编码
前缀编码： 任一字符的编码都不是另一字符编码的前缀 赫夫曼编码： 以n种字符出现的概率（频率）为权，设计一个赫夫曼树，由此得到的二进制前缀编码 例6.9 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计赫夫曼编码 算法 6.19 先序遍历 void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC, int n)