数 据 结 构 Ch.6 树 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj.

Slides:



Advertisements
Similar presentations
第七节 心 悸 郑祖平. 一、概述 心悸是一种自觉心脏跳动的不适感或心 慌感。当心率加快时感到心脏跳动不适, 心率缓慢时则感到搏动有力。心悸时,心 率可快、可慢,也可有心律失常,心率和 心律正常者亦可有心悸。 一般认为与心肌收缩力心搏量的变化及 患者的精神状态注意力是否集中等多种因 素有关。
Advertisements

1/67 美和科技大學 美和科技大學 社會工作系 社會工作系. 2/67 社工系基礎學程規劃 ( 四技 ) 一上一下二上二下三上 校訂必修校訂必修 英文 I 中文閱讀與寫作 I 計算機概論 I 體育 服務與學習教育 I 英文 II 中文閱讀與寫作 II 計算機概論 II 體育 服務與學習教育 II.
聖若翰天主教小學 聖若翰天主教小學歡迎各位家長蒞臨 自行分配中一學位家長會 自行分配中一學位家長會.
「健康飲食在校園」運動 2008小學校長高峰會 講題:健康飲食政策個案分享 講者:啟基學校-莫鳳儀校長 日期:二零零八年五月六日(星期二)
脊柱损伤固定搬运术 无锡市急救中心 林长春.
第7章 樹與二元樹 (Trees and Binary Trees)
Chapter 06 Tree and binary tree 第六章 树和二叉树
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
第6章 二叉树和树 前面的章节主要讨论的是线性结构,二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。
務要火熱服事主.
作业现场违章分析.
蒙福夫妻相处之道 经文:弗5:21-33.
计算机软件技术基础 数据结构与算法(4).
数据结构——树和二叉树 1/96.
引入树 线性表、堆栈和队列都是线性结构,它们的共同特点:一对一; 计算机对弈中的一个格局可能有多个后继格局,用线性结构难以描述。
第六章 树和二叉树.
第六章 树和二叉树.
第6章 树和二叉树 (Tree & Binary Tree)
第5章 树( Tree )和二叉树 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林
CH6 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林
第八章 查找.
数据结构 第六章 树与二叉树 深圳大学计算机系 蔡茂国.
第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
数据结构 第6章 树和二叉树 什么是树和二叉树?? 二叉树的遍历 数据结构.
专题研讨课二: 数组在解决复杂问题中的作用
第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用.
6.5滑坡 一、概述 1.什么是滑坡? 是斜坡的土体或岩体在重力作用下失去原有的稳定状态,沿着斜坡内某些滑动面(滑动带)作整体向下滑动的现象。
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
Chapter 5 Tree & Binary Tree
第11章 查找 主要知识点 查找的基本概念 静态查找表 动态查找表 哈希表.
Chapter8 Binary and Other Trees
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
复习.
结构体和共用体 2 梁春燕 华电信息管理教研室.
第五章 数组和广义表.
哈夫曼编码.
第12章 樹狀搜尋結構 (Search Trees)
第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历 6.4线索二叉树 6.5树和森林 6.6树的应用(霍夫曼树及其编码)
第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.
第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第六章 树和二叉树.
本章重点难点 重点:顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。
第3章 栈和队列(一).
数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
第7章 树和二叉树 7.1 树 7.2 二叉树 7.3 以结点类为基础的二叉树设计 7.4 二叉树类 7.5 二叉树的分步遍历
数据结构 第9章 查找 什么是查找?? 静态查找 动态查找 哈希表 数据结构.
6.6 Huffman树及其应用 王 玲.
6.3 遍历二叉树和线索二叉树(知识点二) 遍历二叉树 一、问题的提出
西师大版 语文 一年级 上册 十个数.
Tree & Binary Tree.
第6章 树和二叉树 本章主题:树、二叉树 教学目的:掌握树和二叉树的类型定义、运算及存储结构 教学重点:树的各种表示、各种存储方式和运算,
第6章 树与二叉树 6.1 树的概念和运算 6.2 二叉树 6.3 树和森林 6.4 树的典型应用 6.5 本章小结.
聖本篤堂 主日三分鐘 天主教教理重温 (94) (此簡報由聖本篤堂培育組製作).
7.1 广义表的概念 广义表是n(n≥0)个数据元素组成的序列,其中每个数据元素或是单个数据元素(简称原子),或仍然是一个广义表 。
第六章 树和二叉树 £6.1 树 £6.2 二叉树 £6. 3 二叉树的存储结构 £6.4 二叉树的遍历与线索化 £6.1.1 树的定义
第六章 树和二叉树 学习要点 理解树的定义和基本术语,重点了解二叉树的定义、性质、存储结构; 掌握二叉树遍历的递归算法及它的典型运算;
第7章 樹與二元樹(Trees and Binary Trees)
資料結構使用Java 第9章 樹(Tree).
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算
C++语言程序设计教程 第2章 数据类型与表达式 第2章 数据类型与表达式 制作人:杨进才 沈显君.
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
树和二叉树(一).
基督是更美的祭物 希伯來書 9:1-10:18.
第10章 二元搜尋樹 (Binary Search Tree)
本节内容 1.二叉排序树的定义 2.二叉排序树的查找操作 3.二叉排序树的插入操作 4.二叉排序树的删除操作 5.二叉排序树的总结
Presentation transcript:

数 据 结 构 Ch.6 树 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj

Ch.6 树 树形结构: 特征: 应用:家谱、行政架构等,计算机系统中的文件目录等 二叉树,树,森林等 结点间有分支,具有层次关系 每个结点最多只有一个直接前驱,但可有多个直间后继. 开始结点 —— 根 终端结点 —— 叶 其余结点 —— 内部结点 应用:家谱、行政架构等,计算机系统中的文件目录等

§6.1树的概念 Def: 树是n (n>=0) 个结点的有限集T,T为空时称为空树,否则它满足: 有且仅有一个特定的称为根的结点; 其余结点可分为m (m>=0) 个互不相交的子集T1 ,T2,…Tm,其中每个子集本身又是一棵树,并称之为根的子树.

§6.1树的概念 递归定义:刻画了树的固有特性:非空树由若干棵子树构成,子树由较小子树构成. 表示:

§6.1树的概念 术语: 结点的度:结点拥有的子树数目(树的度) 叶子:终端结点,度为0的结点 分支结点:非终端结点,度>0 内部结点:根之外的分支结点 根:开始结点 孩子、双亲:某结点的子树的根称为该 结点的孩子,该结点为孩子的双亲 直接前驱(双亲) 直接后继(孩子) 兄弟:同一双亲的孩子互为兄弟

§6.1树的概念 术语: 路径:道路(自上而下) 祖先和子孙:若k到ks有一路径,则k是ks的祖先,ks是k的子孙.   若存在一结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1<=i<=j-1),则称该序列是从k1到kj的一条路径或道路,路径长度为边数j-1. 祖先和子孙:若k到ks有一路径,则k是ks的祖先,ks是k的子孙. 结点A的祖先是从根到A的路径上所经过的所有结点. 结点A的子孙是以A为根的子树中的所有结点. 真祖先和真子孙不包含自身 层数从根起算(为1或0),其余结点的层数是其双亲的层数+1

§6.1树的概念 术语: 高(深)度:树中结点的最大层数 堂兄弟:双亲在同一层的结点互为堂兄弟 有序树、无序树:   若每结点的各子树看成是从左到右有次序(不能互换)的,则称为有序树,否则为无序树。 不同的有序树,一般讨论有序树 森林:m (m>=0) 棵互不相交的树的集合 树和森林非常接近:删去树根 => 森林           森林加上一根 => 树

§6.1树的概念 }其余结点为内部结点. 逻辑特征: 父子关系(非线性关系):任一结点至多有一直接前驱(双亲)结点,但可有多个直接后继(子女)结点. 开始结点:根 终端结点:叶 祖先与子孙关系:是对父子关系的延拓,它定义了树中结点的纵向关系. 横向关系:有序树定义了同一组兄弟间的从左到右的长幼关系,可将其延拓到结点间的横向次序:k1和k2是兄弟,k1在左,则k1的任一子孙在k2的任一子孙的左边. }其余结点为内部结点.

§6.2二叉树 是一种特殊的树型结构,每个结点至多只有二棵子树,一般树可转换为二叉树,计算机用途甚广. §6.2.1二叉树的定义 Def: 二叉树是n(n>=0)个结点的有限集,它或者是空集,或由一个根结点及两棵互不相交的,分别称作根的左子树和右子树的二叉树组成

§6.2.1 二叉树的定义 形态 与度为2的有序树区别: 当某一结点只有一孩子时,有序树中它理所当然为长子,但二叉树中,一个结点只有一个孩子亦需分出其左右.

§6.2.2 二叉树的性质 性质1:二叉树的第i层上至多有2i-1个结点(i≥1,根为第1层) pf:归纳法 归纳假设:设所有的j(1 ≤ j<i)命题成立.即: 第j层结点数≤2j-1 归纳步骤:j=i时,第i-1层结点数≤ 2i-2(由归纳假设)   因为,每个结点至多有两个孩子.   所以,第i层上结点数≤ 2*2i-2=2i-1.

§6.2.2 二叉树的性质 性质2.深度为h的二叉树至多有2h-1个结点(h≥1). Pf: 深度一定时,仅当每层上结点达到最大时,该树结点最多. 利用性质1知,深度为h的二叉树至多有: 20+21+…+2h-1 = 2h-1

§6.2.2 二叉树的性质 性质3.在任一二叉树T中,设叶子数为n0,度为2的结点数为n2.则n0=n2+1. Pf: 设n1为度为1的结点总数,则结点总数n等于0度, 1度和2度结点数之和   n = n0+n1+n2 // 二叉树   (6.1) 另一方面,除根外,其余结点均是其双亲的孩子,树中: 孩子结点总数 = n1+2n2  n-1 = n1+2n2 n = n1+2n2+1 (6.2) 由6.1和6.2:n0=n2+1

§6.2.2 二叉树的性质 满二叉树:深度为h的具有2h-1个结点的二叉树称为满二叉树. 完全二叉树:若一二叉树至多只有最下两层上结点的度数可小于2,且最下一层上的结点都集中在该层最左边的若干位置,则称为完全二叉树.    某结点无左孩子,则它必为叶子    满二叉树是完全二叉树,但反之未必成立.

§6.2.2 二叉树的性质 性质4.具有n个结点的完全二叉树高为 或 pf: ∵树高为h,则前h-1层是高为h-1的满二叉树,结点总数 = 2h-1-1. ∴ 2h-1-1 < n ≤ 2h-1 (2h-1 < n+1 ≤ 2h) // 第h层上至少有一个结点 2h-1 ≤ n < 2h //整数 h-1 ≤ lgn < h (h-1 < lg(n+1) ≤ h) ∵ h-1和h是相邻的整数 ∴ h-1 = (h = )

§6.2.3 二叉树的存储结构 顺序存储结构 如何将结点线性化,使得在线性序列中的相互位置能反映出结点间的逻辑关系? 若对完全二叉树自上而下,每层自左到右给所有n个结点编号,就能到一个足以反映整个二叉树结构的线性序列. ∵ 完全二叉树除最下层外,各层都充满了结点,每层结点数恰为上层的2倍. ∴ 从一结点编号可推出其双亲,左右孩子,兄弟结点和编号.

§6.2.3 二叉树的存储结构 性质5. 设完全二叉树中编号为i的结点简称ki(1≤ i≤ n), 则有: (1) 若i=1,则结点ki为根,无双亲;若i>1,则ki的双亲是 (2) 若2i≤n,则ki的左孩子为k2i;否则ki无左孩子,即它必 为叶子。//因此,完全二叉树中编号i> 的结点必为叶子; (3) 若2i+1≤n,则ki的右孩子为k2i+1 ,否则ki无右孩子; (4) 若i为奇数且大于1,则ki的左兄弟为ki-1,否则ki无左兄 弟; (5) 若i为偶数且小于n,则ki的右兄弟为ki+1,否则ki无右兄 弟。 证明从略。

§6.2.3 二叉树的存储结构 ∵ 上述关系中,编号足以反 映结点间的逻辑关系 ∴ 可将n个结点存储在向量 bt[0..n]中,其中: bt[1..n] —— 存储编号为1至n的结点

§6.2.3 二叉树的存储结构 缺点 对一般的二叉树,须按完全二叉树的编号来存储,浪费空间,最坏情况是右单支树,k个结点需2k-1个结点空间。 结论 这种结构只适用于存储完全二叉树,且插入和删 除不便。

§6.2.3 二叉树的存储结构 链式存储结构 结点结构 类型定义 typedef struct node { DataType data; struct node *lchild, *rchild; } BinTNode; // 结点类型 typedef BinTNode *BinTree; //二叉树类型

在二叉树中,所有类型为BinTNode的结点,加上一个指向根的BinTree型头指针root,就构成了二叉树的链式存储结构,称之为二叉链表 §6.2.3 二叉树的存储结构 在二叉树中,所有类型为BinTNode的结点,加上一个指向根的BinTree型头指针root,就构成了二叉树的链式存储结构,称之为二叉链表 显然,二叉链表由根指针root唯一确定。 例子 特性 空树  root = NULL 叶子  左右指针为空 空指针数:n个结点,共有2n个指针域,但只有n-1个结点是别人的孩子,故空指针数为n+1

§6.3 遍历二叉树 概念 定义:沿某搜索路线,依次对树中每个结点均做一次且仅做一次访问。 §6.3 遍历二叉树 概念 定义:沿某搜索路线,依次对树中每个结点均做一次且仅做一次访问。 重要性:是其它运算的基础,很多树上操作均依赖于遍历操作,只是访问结点所做的操作不同。 如何遍历? 遍历线性结构很容易:从开始结点出发,依次访问当前结点的后继,直至终端结点为止。遍历路线只有一条(如单链表,从头指针开始)。 但二叉树中每个结点可能有两个后继,故遍历路线不唯一,须找到适用于每个结点的相同的遍历规则。

§6.3 遍历二叉树 ∵ 在二叉树的递归定义中,非空树组成为: D、L、R ∴ 在任一结点上,可按某种次序执行三个操作: §6.3 遍历二叉树 ∵ 在二叉树的递归定义中,非空树组成为: D、L、R ∴ 在任一结点上,可按某种次序执行三个操作: 访问根结点(D),遍历该结点的左子树(L),遍历该结点的右子树(R) 显然有六种执行次序: 遍历规则(从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同 前序(先序,先根)遍历:DLR 中序(中根)遍历:LDR 后序(后根)遍历:LRD

§6.3 遍历二叉树 以中根为例,遍历二叉树定义为: 遍历算法 if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 §6.3 遍历二叉树 遍历算法 以中根为例,遍历二叉树定义为: if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 (2) 访问根 // 将(1)(2)和(2)(3)对调后为先根和后根遍历 (3) 遍历右子树 //即遍历二叉树 } // 否则为空操作 (递归结束条件) void Inorder(BinTree T) { // T为二叉树的头指针 if (T) { // T非空,T为空时为空操作 Inorder(T->lchild); // 递归遍历左子树 printf(“%c”, T->data);// 访问根结点,具体问题,此 // 操作不同 Inorder(T->rchild); // 递归遍历右子树 } 时间:O(n)

§6.3 遍历二叉树 遍历序列 包络线是递归遍历路线 向下:表示递归调用,更 深一层 向上:表示递归结束,返 回一层 每个结点经过3次, §6.3 遍历二叉树 遍历序列 包络线是递归遍历路线 向下:表示递归调用,更 深一层 向上:表示递归结束,返 回一层 每个结点经过3次, 第1次经过时访问所得结 点序列为前序,第2次经 过时访问所得结点序列为 中序,第3次经过时访问 所得结点序列为后序。 1个开始结点,1个终端结点,其余结点均有一个直接前驱和一个直接后继,为区别3种次序在前面冠以 叶子的相对次序相同

§6.3 遍历二叉树 通用的遍历算法 因为访问结点的操作依赖于具体问题,故可将它作为一个函数指针参数放于遍历算法的参数表中,调用时,使其指向具体的访问结点的应用函数 void Inorder( BinTree T, void (*Visit)(DataType x) ) { if (T) { Inorder(T->lchild, Visit); (*Visit)(T->data); Inorder(T->rchild, Visit); } 其中Visit是一函数指针,它指向形如void f(DataType x)的函数,故可将访问结点的操作写在函数f中,通过调用语句: Inorder(root, f); 将f的地址传给Visit。

§6.3 遍历二叉树 通用的遍历算法 例如,可将打印操作为 void print(DataType x) { print(“%c”, x); §6.3 遍历二叉树 通用的遍历算法 例如,可将打印操作为 void print(DataType x) { print(“%c”, x); } 调用Inorder(root, print),即可完成前述算法。 函数名:函数代码的起址。

§6.3 遍历二叉树 建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 §6.3 遍历二叉树 建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 输入先序序列,加入虚结点(输入时用空格符“ ”)以示空指针的位置,例如前述的二叉树,输入为: ABDФФФCEФФFФФ

§6.3 遍历二叉树 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 §6.3 遍历二叉树 void CreateBinTree(BinTree *T) { // 注意T为指针的指针 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 if (ch == ‘ ’) // 读入空格 *T = NULL; // 将相应的指针置空 else { // 读入的是结点数据 *T = (BinTNode*) malloc(sizeof(BinTNode)); (*T)->data = ch; // 生成新结点,相当于访问根节点 CreateBinTree(&(*T)->lchild); // 遍历左子树 CreateBinTree(&(*T)->rchild); // 遍历右子树 } 建树时调用 CreateBinTree(&root), 将root(BinTree类型)的地址复制给T,故修改*T就相当于修改了实参root本身。 时间:O(n)

§6.4 线索二叉树 基本概念 在一基本数据结构上常常需要扩充,增加辅助信息,其目的是: ①开发新操作;②加速已有操作。 §6.4 线索二叉树 基本概念 在一基本数据结构上常常需要扩充,增加辅助信息,其目的是: ①开发新操作;②加速已有操作。 线索 —— 利用空指针域(n+1个)存放指向结点在某种遍历次序下的前驱和后继指针 线索链表 —— 加上线索的二叉链表 线索二叉树 —— 相应的二叉树称为线索二叉树 目的:加速遍历操作 加速查找任一结点在某种遍历次序下的前驱和后继操作 如何区别结点的指针域 孩子指针:指向孩子? 线索指针:指向其某种遍历次序下的前驱和后继的线索?

§6.4 线索二叉树 基本概念 结点结构 线索标志 中序线索树和中序线索链表 中序序列:CBDAFHGIE

§6.4 线索二叉树 基本概念 中序线索树中必有两个指针域为空 前序线索树中,有几个指针域为空? §6.4 线索二叉树 基本概念 中序线索树中必有两个指针域为空 前序线索树中,有几个指针域为空? 前序序列的开始结点为根,故当它的左子树非空时,其指针域指向左指子树,此时前序序列开始结点左指针非空。 但是,前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针。

§6.4 线索二叉树 基本概念 后序线索树中,开始结点的左指针必为空,仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称 §6.4 线索二叉树 基本概念 后序线索树中,开始结点的左指针必为空,仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称 带头结点的线索链表 树上6.11图(b). 令空指针也指向此哨兵

§6.4 线索二叉树 基本概念 线索化 线索树中,如何判定结点是否为叶子? ltag = rtag = 1 (适用于三种线索树) §6.4 线索二叉树 基本概念 线索树中,如何判定结点是否为叶子? ltag = rtag = 1 (适用于三种线索树) 有时线索树只有左线索或右线索之一 线索化 将二叉树变为线索树的过程 按某种次序遍历,在遍历过程中用线索取代空指针。 typedef enum {Link, Thread} PointerTag; // 0为Link,1为Thread typedef struct node { DataType data; PointerTag ltag, rtag; struct node *lchild, *rchild; } BinThrNode, *BinThrTree; 设p和pre分别指向遍历过程中当前访问结点和其前驱,即*pre和*p是 前驱和后继的关系,其中pre为全局量,在遍历过程中建立线索。 以中序为例,pre初始为NULL,因为中序前驱对开始结点是NULL。

§6.4 线索二叉树 void InorderThreading(BinThrTree p) { // pre为全局量,初值为NULL §6.4 线索二叉树 void InorderThreading(BinThrTree p) { // pre为全局量,初值为NULL if (p) { InorderThreading(p->lchild); // 左子树线索化 p->ltag = (p->lchild) ? Link : Thread; // 左指针非空,置为 // Link,否则为线索。 p->rtag = (p->rchild) ? Link : Thread; if (pre) { // 若*pre存在 if (pre->rtag == Thread) // 当前结点*p的前驱右标志为线索 pre->rchild = p; // 令*pre的右线索指向中序后继*p if (p->ltag == Thread) // 当前结点的左线索已建立 p->lchild = pre; //令当前节点的左线索指向中序前驱 } pre = p; //使*pre为*p的前驱,循环不变量 InorderThreading(p->rchild); // 右子树线索化 时间:和遍历相同O(n). 后序(前序)线索化类似于此。 访问根结点

§6.4 线索二叉树 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 找*p的中序后继 §6.4 线索二叉树 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 找*p的中序后继 i) 若*p的右子树空,则p->rchild为右线索,直接指向*p的中序后继 ii)若*p的右子树非空(rtag为0),则*p的中序后继必是其右子树中第一个中序遍历到的结点,其特征是: 从*p的右孩子开始,沿其左链往下找,直至找到一个没有左孩子的结点为止,不妨称其为右子树中“最左下”的结点。 p 这里k≥ 1, Rk不一定是叶子,其右子树可为空,可非空。 算法 请自己给出找给定结点*p的中序后继算法。时间O(h),快于无线索的二叉树。

§6.4 线索二叉树 找*p的中序前驱 ∵ 中序是对称序,其方法与(1)完全对称 i) 若*p的ltag = 1,则中序前驱为lchild §6.4 线索二叉树 加速作用 在普通二叉树中,找*p中序后继: 对于ii)同样有效 对于 i)就必须从根开始遍历。 ∵有线索是直接从线索找到O(1)。但线索一般“向上”指向其祖先,而二叉树中无向上的链接,只能从根开始遍历得到,最坏情况O(n)。 找*p的中序前驱 ∵ 中序是对称序,其方法与(1)完全对称 i) 若*p的ltag = 1,则中序前驱为lchild ii)若*p的ltag = 0,则中序前驱是*p的左子树中 “最右下”的结点。

§6.4 线索二叉树 (2) 找*p的后序前驱和后序后继(在后序线索树中) 找*p的后序前驱(易) §6.4 线索二叉树 (2) 找*p的后序前驱和后序后继(在后序线索树中) 找*p的后序前驱(易) i) 若*p的ltag = 1(左子树为空),则后序前驱为p->lchild ii)若*p的ltag = 0(左子树非空),则后序前驱为p的左孩子或右孩子 ∵根是在遍历左右子树L和R之后被访问 ∴*p的前驱必是L和R中最后一个遍历到的结点 if (p的右孩子非空) then return p->rchild; // 后序前驱为p的右孩子 else return p->lchild; //后序前驱为p的左孩子 找*p的后序后继(难)(见右图) i) 若*p为根,无后继,返回NULL ii) 若*p是其双亲右子,则*p的后序后继是双亲 iii)若*p是其双亲左子,但*p无右兄弟,则*p的 后序后继亦为双亲

§6.4 线索二叉树 (3) 找*p的前序前驱和前序后继 类似于后序的情况分析 讨论:找前序前驱难(涉及双亲) 找前序后继易 §6.4 线索二叉树 找*p的后序后继(续) iv)若*p是其双亲左子,但*p有右兄弟,则*p的 后序后继是其右兄弟子树中1st后序遍历到的结点,它是该子树中“最左下的叶结点” 结论:找后序前驱易 找后序后继难,因为: 只有*p的右子树为空(rtag = 1)时,p->rchild是线索,可直接找到; 否则,一般须涉及*p的双亲,故仅给出*p时,须从根遍历。 (3) 找*p的前序前驱和前序后继 类似于后序的情况分析 讨论:找前序前驱难(涉及双亲) 找前序后继易

§6.4 线索二叉树 (4) 遍历线索二叉树 遍历某次序的线索二叉树,只要从该次序下的开始结点出发,反复找其后继直至终端结点为止。 中序 §6.4 线索二叉树 (4) 遍历线索二叉树 遍历某次序的线索二叉树,只要从该次序下的开始结点出发,反复找其后继直至终端结点为止。 中序 找开始结点(最左下结点),找当前结点中序后继,直至终端结点(p->rchild = NULL) 头结点的右指针指向开始结点较方便 前序 找开始结点(根),找当前结点的前序后继,直至终端结点 (p->rchild = NULL) 头结点的右指针指向终端结点较方便 后序 找终端结点(根),找当前结点的后序前驱,直至开始结点 (p->lchild = NULL),得到的是后序序列的逆序列 头结点的右指针指向开始结点较方便 时间:仍为O(n),但因为非递归,略快于递归的方法 对遍历而言 前序线索树中,只需保留右线索树即可 中序线索树中,保留左、右线索之一均可 后序线索树中,只需保留左线索即可

§6.5 树和森林 树、森林与二叉树的转换 树中每个结点有多个孩子 => 二叉树只有两个孩子 树 => 二叉树 §6.5 树和森林 树、森林与二叉树的转换 树 => 二叉树 树中每个结点有多个孩子 => 二叉树只有两个孩子 长子及右邻兄弟 => 二叉树的左右孩子 节点X的长子是其左子,X的右兄弟是其右子 每个结点仅保留与长子的连线 所有兄弟结点间连线

§6.5 树和森林 树、森林与二叉树的转换 森林 => 二叉树 将各树转换为二叉树(根无右兄弟,所以无右子) 将各根作为兄弟互连

§6.5 树和森林 树、森林与二叉树的转换 二叉树 => 树或森林 设x是y的左孩子,则将x的右孩子,右孩子的右孩子,都与y相连 §6.5 树和森林 树、森林与二叉树的转换 二叉树 => 树或森林 设x是y的左孩子,则将x的右孩子,右孩子的右孩子,都与y相连 去掉所有双亲到右孩子的连线

§6.5 树和森林 树的存储结构 双亲链表表示法 ∵每结点双亲唯一,故存储结点时,增加一个parent域指向双亲,用向量表示较方便 §6.5 树和森林 树的存储结构 双亲链表表示法 ∵每结点双亲唯一,故存储结点时,增加一个parent域指向双亲,用向量表示较方便 特点:向上链接,根的parent为-1 求指定结点双亲(O(1))及祖先(O(h))方便 求指定结点孩子及后代须遍历数组O(n) 类型说明(略)

§6.5 树和森林 树的存储结构 孩子链表表示法 ∵ 树边n-1条 若k叉树用k叉链表表示,会导致浪费空间 §6.5 树和森林 树的存储结构 孩子链表表示法 若k叉树用k叉链表表示,会导致浪费空间 ∵ 树边n-1条 ∴ 空指针kn-(n-1)=n(k-1)+1 设度数域,结点不等长、运算不便 孩子链表:每结点设一孩子链表,将结点及相应孩子链表的头指针放在一向量中。

§6.5 树和森林 树的存储结构 孩子链表表示法(续) 孩子兄弟链表表示法 树 => 二叉树时,结点关系由:最左孩子、右邻兄弟表 示 §6.5 树和森林 树的存储结构 孩子链表表示法(续) 特点:易实现找结点的孩子及子孙(向下查找易) 难实现找结点的双亲及祖先(向上查找难) 双亲孩子链表表示法 在孩子链表中,增加parent域 此方法结合了双亲链表和孩子链表的优点,向上向下查找均方便 类型说明:略 孩子兄弟链表表示法 树 => 二叉树时,结点关系由:最左孩子、右邻兄弟表 示

§6.5 树和森林 树和森林的遍历 先序遍历树 先访问树的根;然后依次先序遍历根的每棵子树 后序遍历树 §6.5 树和森林 树和森林的遍历 先序遍历树 先访问树的根;然后依次先序遍历根的每棵子树 后序遍历树 先依次后序遍历根的每棵子树;然后访问树的根; 先序遍历森林 先访问森林中第一棵树的根;然后先序遍历第一棵树中根结点的各子树所构成的森林;最后先序遍历除第一棵外其它树构成的森林 后序遍历森林 后序遍历森林中第一棵树的根结点的各子树所构成的森林;然后访问第一棵树的根;最后后序遍历除第一棵外其它树构成的森林 先序遍历恰好等价于先序遍历对应的二叉树,后序遍历恰好等价于中序遍历对应的二叉树。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 概念 结点路径长度:根到该结点所经过的边数 树的路径长度:所有结点的路径长度之和 (结点数相同时,完全二叉树的路径长度最短) 结点的带权路径长度: 结点的权值Wi × 结点的路径长度li 树的带权路径长度(实际上是加权外部路径长度) 所有叶子的加权路径长度之和

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 最优二叉树(Huffman树) 在权为w1,w2,…,wn的叶子所构成的所有的二叉树,WPL最小的二叉树称为最优二叉树 例 n=4,{a:7, b:5, c:2, d:4} 若叶子权值相同,完全二叉树一定是最优二叉树,否则不一定

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 显然,权越大应离根越近,Huffman首先提出了构造方法: 1)初始森林:根据给定的n个权{w1,w2,…,wn}构成一个包含n棵二叉树的森林F={T1,T2,…,Tn}. 其中Ti只有一个根(亦为叶子)结点,其权为wi; 2)合并:在F中选两棵根的权最小的二叉树(若不止两棵,则任选)作为左、右孩子,将其合并为一棵新树,新根权值为这两个结点的权值之和; 3)对新森林F重复2),直至只剩下一棵树为止。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 算法特点 每合并一次产生1新结点,且新结点度为2,故最终的 Huffman树有2n-1个结点: 实际上任何严格二叉树中,叶子数为n时,总结点数为2n-1。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 存储结构 构造算法 #define n 100 // 叶子数 #define m 2*n-1 // 结点总数 typedef struct { float weight; // 权,不妨设≥0 int lchild, rchild, parent; // 指针 } HTNode; typedef HTNode HuffmanTree[m]; parent域作用:找双亲结点 为-1时表示根,区分根与非根 构造算法

§6.6 Huffman树及其应用 int i, p1, p2; void CreateHuffmanTree (HuffmanTree T) { // 构造最优树,根为T[m-1] int i, p1, p2; InitHuffmanTree(T); // 初始化, 将2n-1个结点的3个指针置空(-1),权置为0 InputWeight(T); // 输入n个叶子(根)的权存于T[0..n-1]中,初 //始化森林F0中的根权 for (i = n; i < m; i++){ // 对F中的树合并n-1次,新根依次放入T[i]中,最终 //根为T[m-1] SelectMin(T, i-1, &p1, &p2); // 在当前森林T[0..i-1]的所有结点中,选权 //最小和次小的两个根结点T[p1]和T[p2]作为合并对象,0≤p1,p2≤i-1 T[p1].parent = T[p2].parent = i; // 合并产生的新根为T[i] T[i].lchild = p1; T[i].rchild = p2; T[i].weight = T[p1].weight + T[p2].weight } 算法中用到的三个函数略,实例(教材)

§6.6.2 Huffman编码 概念 数据压缩 可将数据文件压缩20%~90%,压缩效率取决于文件特征 编解码 编码方案(对字符集编码) 例 C = {a, b, c, d, e, f}, 设数据文件有10万字符,|C|=6 节约25%空间 a b c d e f 编码总长 频度(万) 4.5 1.3 1.2 1.0 0.9 0.5 定长 000 001 010 011 100 101 30万 变长 111 1101 1100 22.4万

§6.6.2 Huffman编码 定长编码:码长 变长编码:问题是解码可能有二义性 例如:设E,T,W编码为00, 01, 0001 问题的原因 —— E的编码是W的编码的前缀 前缀编码:要求字符集中,任一字符的编码皆不是其他 字符编码的前缀。 显然,定长编码是前缀编码 最优的前缀码 (Huffman编码):压缩效果最佳的前缀码 动态编码 对给定文件,先统计字符集C = {c1,c2,…,cn} 中各字符出现的频率fi, 据此设计编码,设ci的码长为li,则编码文件总长度: —— 使文件编码总长最短的前缀码是最优前缀码 对同一字符集表示的不同文件,编码方案不同,即根据文 件特征动态编码。 特点: 费时,效果最佳

§6.6.2 Huffman编码 编码算法 算法思想 利用Huffman树求最优前缀码 静态编码 无需每次压缩前均统计Ci的频度,而是对定义在相同字符集上的大量文件进行统计,得出每个字符Ci 出现的概率pi,据此编码,则平均码长为: —— 平均码长最短的前缀码为最优前缀码 例:上例中a~f 出现的概率为:0.45, 0.13, …, 0.05, 平均码长为 2.24,优于定长编码 (平均码长为3)。 特点 编码算法 算法思想 利用Huffman树求最优前缀码 step1:用字符ci作为叶子,pi(或fi)做ci的权,构造Huffman树 step2:将树的左右分支分别标记0和1,将根到叶子的路径上的标号依次相连,作为该叶子(字符)的编码。 所有文件使用同一编码,省时 对不同的文件,效果不尽相同

§6.6.2 Huffman编码 例子 按算法建立的Huffman树唯一

§6.6.2 Huffman编码 算法实现 (对字符集编码,即叶子集编码) typedef struct { 上述编码是最优的前缀吗? 最优 ∵ 叶子的码长 = 叶子的路径长度li ∴ 既是平均码长,又是二叉树的WPL 即 Huffman树是WPL最小的二叉树 => 平均码长最小 前缀码 ∵ 树中任一叶子不可能是其它叶子的祖先 ∴ 每叶子编码不可能是其它叶子编码的前缀 算法实现 (对字符集编码,即叶子集编码) typedef struct { char ch; // 放字符 char bits[n+1]; // 放位串‘\0’结束,码长不会超过n } CodeNode; // 存放Huffman编码的结点 typedef CodeNode HuffmanCode[n];

§6.6.2 Huffman编码 // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 void HuffmanCoding (HuffmanTree T, HuffmanCode H) { // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 char cd[n+1]; // 临时存放编码 int start; // 指示编码在cd中的起始位置 cd[n] = ‘\0’; // 从后往前放编码 for (i = 0; i < n; i++){ //依次求叶子T[i]的编码 0 ≤ i ≤ n-1 H[i].ch = getchar();//读入叶子T[i]对应的字符,若建树时有字符则无需读入 start = n; c = i; //从叶子T[i]上溯至根,逆向求编码 while((p = T[c].parent) >= 0) { // 到根为止 if (T[p].lchild == c) cd[--start] = ‘0’; // 若T[c]是T[p]的左子树生成代码0 else cd[--start] = ‘1’; // 否则生成代码1 c = p; // 继续上溯 } strcpy(H[i].bits, &cd[start]); // 复制编码位串 } // endfor } // 时间: O(n.h)

§6.6.2 Huffman编码 4. 应用 (数据文件的压缩与解压) 压缩数据文件 (对文件编码) for (依次从f1中读入字符c) { 在Huffman编码表H中,找H[i].ch = c 将c转换为H[i].bits写入压缩文件f2中; // 按bits0,1串写入“位”,设f2是二进制文件 } 加压译码 (对压缩文件解码) for (依次读入f2中的位串) { // 直至文件结束 从Huffman树根T[m-1]出发 若当前读入0,走向左孩子,否则走向右孩子; 若到达叶子T[i],便译出字符H[i].ch写入还原文件中,然后 重新从根出发译码 Note: 实际压缩与解压时,编码的0/1位串,不是字符串,即写入压缩文件中的是“位”

§6.7 回溯法与搜索树 回溯法思想 有一类问题,需要找出它的解集合,或要求找出满足某些约束条件下的最优解,最简单的方法是回溯法。 所谓回溯就是走回头路,即在一定的约束条件下试探地搜索前进,若前进中受阻,则回头另择道路继续搜索(搜索路线是一棵树) N皇后问题(Gauss 1777-1855 德国数学家) 高斯8后问题 (1850提出),即在8×8国际象棋棋盘上,安放8个皇后,要求彼此互不攻击,有多少个解,这些解的格局如何? 他本人未解决此问题 原因: 种格局,92个解(包括对称解)

§6.7 回溯法与搜索树 攻击(约束条件) 同一行、列,同一对角线的两皇后互相攻击 i+j: 135度对角线:同一对角线上元素行列号之和相等(2n-1条) 0~2n-2 j-i: 45度对角线:同一对角线上元素行列号之差相等(2n-1条) –(n-1),…,0,…,n-1

§6.7 回溯法与搜索树 回溯法 从第1行开始依次放置皇后,每行从第1列开始试探位置是否安全,安全则放置,若某行所有位置均不安全,则回溯到上一行,重新放置。 将上述求解过程中棋盘状态的每一步变化用树来表示,则 可用4叉树表示(如书上Fig6.29),该树反映了状态空间中搜 索过程,不满足约束条件的结点不再生长(即被剪枝)。 先序遍历该树

§6.7 回溯法与搜索树 N皇后算法 设try[0..n-1]存放解,下标为行,值为列,即:设try[i]=j,则(i, j)表示棋盘上第i行,第j列存一皇后,逐行放置,每行只有一皇后故可不考虑行冲突,只要考虑列和2条对角线冲突。 void Queens(i, col, diag45, diag135){ //i, col, diag45, diag135为值参 // 全局量try进入此处时,部分解try[0..i]已求出,col,diag45,diag135 // 是集合,初始调用为Queens(-1, Ф,Ф, Ф) if (i == n-1) print try[0..n-1]; // 输出一个解 else // 试求部分解try[0..i+1],即在(i+1)行上放皇后 for (j = 0; j < n; j++) // 试探在第(i+1)行上放皇后 if (j col && j-(i+1) diag45 && (i+1)+j diag135) { // (i+1, j)位置安全 try[i+1] = j; Queens(i+1, col∪{j}, diag45∪{j-i-1}, diag135∪{i+j+1}); } // endif } // 回溯过程要跟踪执行过程才能发现

§6.7 回溯法与搜索树 N皇后算法 改进 上述算法的执行过程就是Fig6.29的状态树(先序遍历) 实际算法可设置布尔数组(初始值均为false)来测试安全性 放置皇后(i+1, j) 令:col[j] = true, 表示第j列已有皇后 diag45[(n-1)+j-(i+1)]=true,表示该对角线上已有皇后 // 移位n-1 diag135[(i+1)+j]=true,表示该对角线上已有皇后 测试安全性 if (!col[j] && !diag45[n-i+j-2] && !diag135[i+1+j]) Note: 用数组要注意它们不是值参,因此可将其说明为结构,内含数组

§6.8 树的计数 问题:一棵具有n个结点的二叉树有多少种不同形态? 二叉树相似: T和T’相似: 指形态相同,不考虑结点中数据是否相同,否则为树等价 二叉树的计数问题:求n个结点互不相似的二叉树数目bn. 二者皆空,否则 二者不空时,它们的左右子树相似

§6.8 树的计数 树的计数问题 n个结点的树的形态数目 ,∵树转换为二叉树后,根无右子树 遍历序列能否唯一确定一棵二叉树? 一般情况: 利用生成函数可求出此递推公式的解为(教材): 树的计数问题 n个结点的树的形态数目 ,∵树转换为二叉树后,根无右子树 遍历序列能否唯一确定一棵二叉树? 二叉树确定后,其三种遍历序列唯一确定 反之,能唯一确定一棵二叉树吗?

§6.8 树的计数 由一棵二叉树的前序序列(或后序序列)+中序序列可唯一确定该二叉树 例:已知某二叉树的前序序列:ABCDEFG,中序序列:CBEDAFG,求对应的二叉树。 由前序序列+后序序列不能唯一确定一棵二叉树 例:前:ABC 后:CBA 由一个遍历序列更不能唯一确定一棵二叉树。

作业 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树对应的中序线索树,然后给出该树的后序遍历序列。 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成, 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码。