第六章树 2019/1/14.

第六章树 2019/1/14

6.1 树(tree)的(递归)定义树：非线性数据结构，以分支关系定义的层次结构树是 n(≥0) 个结点的有限集 T，在非空树中：
有且仅有一个特定的结点，称为树的根(root) n>1时，其余结点可分为 m(>0) 个互不相交的有限集 T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) A 只有根结点的树 2019/1/14

根 A B C D E F G H I J K L M 有子树的树子树子树子树
2019/1/14

基本术语结点(node)：树的元素结点的度(degree)：结点拥有的子树数树的度：一棵树中最大的结点度数
含数据项及若干指向其子树的分支结点的度(degree)：结点拥有的子树数叶子(leaf)：度为 0 的结点树的度：一棵树中最大的结点度数 2019/1/14

基本术语(cont.) 孩子(child)：结点的子树的根双亲(parents)：孩子结点的上层结点
兄弟(sibling)：同一双亲的孩子结点层次(level)：根为第 1 层，根的孩子为第 2 层…… 树的深度/高度(depth)：树中结点的最大层次数 2019/1/14

基本术语(cont.) 子孙：一个结点所有子树中的结点。祖先：从根结点到达某结点路径上的所有结点。
有序树/无序树：如果树中结点的各子树从左到右是有次序的，则称该树为有序树；否则称为无序树森林(forest)：m(≥0) 棵互不相交的树的集合 2019/1/14

结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点I的双亲：D 结点L的双亲：E
结点A的孩子：B，C，D 结点B的孩子：E，F A B C D E F G H I J K L M 结点B，C，D为兄弟结点K，L为兄弟树的度：3 树的深度：4 结点F，G为堂兄弟结点A是结点F，G的祖先结点A的层次：1 结点M的层次：4 2019/1/14

6.2 二叉树定义：二叉树是 n≥0 个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左、右子树的互不相交的二叉树构成
特点：每个结点至多有二棵子树(即不存在度大于 2 的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 2019/1/14

6.2 二叉树  基本形态：度为2的有序树空二叉树 A 只有根结点的二叉树 A B 右子树为空 A B 左子树为空 A B C
左、右子树均非空 2019/1/14

练习：给出 3 个结点A、B和C构成的所有形态的二叉树（不考虑结点值的差异）
2019/1/14

i=1时，只有一个根结点，2i-1=20=1，结论正确 假设对所有 j(1≤j＜i) 命题成立
二叉树性质性质1：二叉树的第 i(≥1) 层上至多有 2i-1 个结点证明：(归纳法) i=1时，只有一个根结点，2i-1=20=1，结论正确 假设对所有 j(1≤j＜i) 命题成立即第 j 层上至多有 2j-1 个结点，则第 i-1 层至多有 2i-2 个结点又二叉树每个结点的度至多为 2  第 i 层上最大结点数是第 i-1 层的 2 倍，即 2×2i-2=2i-1 故命题得证 2019/1/14

二叉树性质性质2：深度为 k(≥1) 的二叉树至多有 2k-1 个结点证明：由性质1，可得深度为k 的二叉树最大结点数是
2019/1/14

二叉树性质性质3：任何一棵二叉树 T，如果其叶子数为 n0，度为 2 的结点数为 n2，则 n0=n2+1
证明：设 n1 为二叉树 T 中度为 1 的结点数因为：二叉树中所有结点的度均小于或等于2 所以二叉树的结点总数 n=n0+n1+n2 又：除根结点外，其余结点都只有一个分支进入设 B 为分支总数，则 n=B+1 又：分支只能由度为 1 和 2 的结点射出，即 B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 故：n0=n2+1 2019/1/14

二叉树特殊形式满二叉树：深度为 k 且有 2k-1 个结点的二叉树
特点：每层上的结点数都是最大值完全二叉树：深度为 k、有 n 个结点的完全二叉树当且仅当，其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为 l，则其左分支下子孙的最大层次必为 l 或 l+1 2019/1/14

证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则：
性质4：有 n 个结点的完全二叉树深度＝证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： ① 2k-1－1＜n≤2k－1 即： 2k-1＜n+1≤2k k－1＜log2(n+1)≤k log2 (n+1)≤k＜log2(n+1)+1 因 k 为整数，所以 k= 2019/1/14

证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则：
性质4：有 n 个结点的完全二叉树深度＝证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： ② 2k-1≤n＜2k 则：k－1≤log2n＜k 即：log2n＜k≤log2n+1 因 k 为整数，故 k= 2019/1/14

哪个是完全二叉树？ 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 2019/1/14

性质5：对有 n 个结点的完全二叉树按层编号，则对任一结点 i(1≤i≤n)，有：
(1) 若 i=1，则结点 i 是二叉树的根，无双亲；若 i＞1，则其双亲编号＝i/2 (2) 若 2i＞n，则结点 i 无左孩子；如果 2i≤n，则其左孩子编号＝2i (3) 若 2i+1＞n，则结点 i 无右孩子；如果2i+1≤n，则其右孩子编号＝2i+1 2019/1/14

理想平衡二叉树 / 理想平衡树 / 理想二叉树在一棵二叉树中，若除最后一层外，其余层都是满的，而最后一层上的结点可以任意分布
显然！理想平衡树包括满二叉树和完全二叉树 2019/1/14

练习：任意一个有 n 个结点的二叉树，已知它有 m 个叶子，请证明非叶结点中有 m-1 个结点的度为 2、其余度为 1
证明：设度为 1 的结点有 n1 个，度为 2 的有 n2 个则总结点 n＝n1＋n2＋m 又：n＝B＋1，B为分支数且：B＝n1＋2n2 则：n＝n1＋2n2＋1 又：n1＋n2＋m＝n1＋2n2＋1 ∴ n2＝m－1 2019/1/14

练习：已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？
解：设度为 0、1、2 的结点数为 n0、n1、n2，结点总数为 n n0=50，因有 n0 = n2 + 1，则 n2=49 又结点总数 n = n0+n1+n2，将上面结果代入得： n = 50 + n1 + 49，即 n=n1+99 由上式可知，当 n1=0 时n 最少，则 n 至少有 99 个结点 2019/1/14

二叉树的存储结构顺序存储结构按满二叉树结点的层次编号，依次存放二叉树的数据元素特点：结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树 1 2 3 4 5 6 7 2019/1/14

假设二叉树的存储结构如下，画出对应的二叉树
练习：假设二叉树的存储结构如下，画出对应的二叉树 I D P C F M E H N 2019/1/14

二叉树顺序存储结构的类型定义：注：下标为 0 的元素存储根结点 #define MAX_TREE_SIZE 100
typedef TElemType SqBiTree [MAX_TREE_SIZE]; SqBiTree bt; 注：下标为 0 的元素存储根结点 2019/1/14

二叉树的链式存储结构（二叉链表）结点 typedef struct BiTNode { BTElemType data ;
数据域：数据本身左指针：左孩子结点右指针：右孩子结点二叉链表由如上结点链接而成二叉树 BiTNode bt; //二叉树根结点 BiTree T; //指向二叉树根结点的指针 lchild data rchild typedef struct BiTNode { BTElemType data ; struct BiTNode *lchild, *rchild; } BiTNode , *BiTree ; 2019/1/14

二叉树的链式存储结构（二叉链表）示例 ^ ^ ^ ^ ^ ^ ^ ^ T (指向根结点的指针) A B C D E F G A B C D
2019/1/14

二叉树的链式存储结构（二叉链表）示例 A B C D E F G ^ T 2019/1/14

静态二叉链表：数组存储结点及父子关系 #define MAX_TREE_SIZE 100 //存储结点最大个数 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8 9 … 99 2019/1/14

静态二叉链表：数组存储结点及父子关系 #define MAX_TREE_SIZE 100 //存储结点最大个数 //结点
struct SBiTreeNode { TElemType data; //数据 int left , right ; //左、右孩子对应数组元素下标 } ; 1 2 3 4 5 6 7 8 9 … 99 data left right 2019/1/14

静态二叉链表：数组存储结点及父子关系 SBiTree #define MAX_TREE_SIZE 100 //存储结点最大个数
struct SBiTreeNode {//结点 TElemType data; //数据 int left , right ; //左、右孩子对应数组元素下标 } ; typedef SBiTreeNode SBiTree [ MAX_TREE_SIZE ]; //静态二叉链表 99 … 9 8 7 6 5 4 3 2 1 data left right SBiTree 2019/1/14

练习：画出以上数组所示二叉树。静态二叉链表：数组存储结点及父子关系
typedef SBiTreeNode SBiTree [ MAX_TREE_SIZE ]; //静态二叉链表 *注意：元素 0 不放数据，其左(下标)指针指向根结点元素指针为 0 表示：空根结点 1 2 3 4 5 6 7 8 9 … 99 A B D C E H F G I data left right SBiTree 练习：画出以上数组所示二叉树。 2019/1/14

二叉树基本操作 I (P127) 辅助：初始化 / 销毁 / 清空 / 空树判定数据值：取值 / 赋值
InitBiTree / DestoryBiTree / ClearBiTree / BiTreeEmpty 数据值：取值 / 赋值 Value / Assign 导航：取根/父/左子/右子/左兄弟/右兄弟结点 Root/Parent/LeftChild/RightChild/LeftSibling/RightSibling 结点：插/删子结点 InsertChild / DeleteChild 2019/1/14

计数：树高度 / 结点数 / 叶子数创建 / 输出遍历：前序 / 中序 / 后序 / 层序
Depth / Count / LeafCount 创建 / 输出 CreateBiTree / PrintBiTree 遍历：前序 / 中序 / 后序 / 层序 PreOrderTraverse / InOrderTraverse / PostOrderTraverse / LevelOrderTraverse 2019/1/14

Depth( T )：树高度/深度，最大结点层次
Depth(T) = 0，T = NULL 2019/1/14

Depth (T) = Max ( Depth (T->lchild ) , Depth (T->rchild ) ) + 1
T (非空树，T 指向根结点) lchild rchild Depth(T->rchild) Depth(T->lchild) Depth (T) = Max ( Depth (T->lchild ) , Depth (T->rchild ) ) + 1 2019/1/14

int BiTreeDepth( BiTree *T ) { if ( T == NULL) //空树，高度=0 return 0;
Depth(T)＝，T＝NULL Max ( Depth(T->lchild) , Depth(T->rchild) ) + 1，T≠NULL int BiTreeDepth( BiTree *T ) { if ( T == NULL) //空树，高度=0 return 0; else { //非空树 lDepth = BTHeight( T->lchild ); //左子树高度 rDepth = BTHeight( T->rchild ); //右子树高度 if (lDepth > rDepth ) return lDepth + 1; //左子树更高 else return rDepth + 1; //右子树更高 2019/1/14

Count(T->lchild) + Count(T->rchild) + 1，T≠NULL
lchild rchild Count(T->rchild) Count(T->lchild) Count(T)= ，T＝NULL Count(T->lchild) + Count(T->rchild) + 1，T≠NULL 2019/1/14

Count(T->lchild) + Count(T->rchild) + 1, T≠NULL
int Count( BiTree T) { if ( T == NULL) //空树 return 0; else { //非空树 lCount = Count( T->lchild ); //左子树结点数 rCount = Count( T->rchild ); //右子树结点数 return ( lCount + rCount +1); } 2019/1/14

(3) 二叉树叶子数：LeafCount(T)
lchild rchild LeafCount(T->lchild) LeafCount(T->rchild) LeafCount(T) , T = NULL LeafCount(T->lchild)+LeafCount(T->rchild), 其它 , T 为叶子 2019/1/14

LeafCount(T->lchild)+LeafCount(T->rchild), 其它 1 , T 为叶子
, T = NULL LeafCount(T->lchild)+LeafCount(T->rchild), 其它 , T 为叶子 int LeafCount( BiTree T ) { if ( T == NULL ) //空树 return 0; else if( T->lchild == NULL && T->rchild == NULL) //叶子 return 1; else { //非叶子结点 lCount = LeafCount( T->lchild); rCount = LeafCount( T->rchild); return (lCount + rCount); } 2019/1/14

^ ^ ^ (4) 用括号表示法描述二叉树：根 ( 左子树, 右子树 ) Ex1. 空树空串 Ex2. 叶子（左右子树均为空） A
A(B) Ex4. 左右子树均非空 A( B , C) A ^ B ^ C ^ 2019/1/14

^ (4) 用括号表示法描述二叉树：根 ( 左子树, 右子树 ) Ex1. 空树空串 Ex2. 叶子（左右子树均为空） A
A(B) Ex4. 左右子树均非空 A( B , C) Ex5. 只有右子树 A( , C) A ^ C 2019/1/14

A( B( C, D( E( ,G), F) )) ^ 先序遍历结果序列的另类表示法！练习：用括号表示法描述左图的二叉树 A B C D
T A( B( C, D( E( ,G), F) )) 先序遍历结果序列的另类表示法！ 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) ① 若树不空则执行 ②，否则停止 ② 输出树的根结点值(字符)
③ 若根结点有孩子则执行 ④，否则停止 ④ 输出左括号："(" ⑤ 递归处理左子树，完成后返回 ⑥ ⑥ 若存在右孩子则输出逗号："," ⑦ 递归处理右子树，完成后返回 ⑧ ⑧ 输出右括号：")" ⑨ 结束 A B C D E F G ^ T 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T)
void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 } 2019/1/14

void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { } 2019/1/14

void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 } 2019/1/14

void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 if (T->rchild != NULL) cout<<","; //输出逗号 } 2019/1/14

void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 if (T->rchild != NULL) cout<<","; //输出逗号 PrintBiTree( T->rchild ); //递归处理右子树 cout<<“)”; } 2019/1/14

？ ^ (5) 用括号表示法创建二叉树：CreatBiTree(T) 已知括号表示字符串，创建二叉链表
已知：A( B( C, D( E( ,G), F))) 要求：创建对应的二叉链表？ A B C D E F G ^ T 2019/1/14

从左到右逐个读入字符串，根据字符类型确定动作
(5) 已知括号表示字符串，创建二叉链表从左到右逐个读入字符串，根据字符类型确定动作 A( B( C, D( E( ,G), F) ) ) 2019/1/14

^ (5) 已知括号表示字符串，创建二叉链表从左到右逐个读入字符串，根据字符类型确定动作
A ( B( C, D( E( ,G), F) ) ) 字符 1=A，数据值 T 创建根结点，填入数据值，左右指针为空设置根指针 T，指向根结点 A ^ 2019/1/14

^ (5) 已知括号表示字符串，创建二叉链表从左到右逐个读入字符串，根据字符类型确定动作
A ( B( C, D( E( ,G), F) ) ) 字符 2= ( ，有左孩子，需要递归处理，需要栈！根结点入栈，开始处理左孩子 1 2 3 4 5 A ^ T A top 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) )
有右孩子，为区分左右，引入标志 k＝1(左)、2(右) A ^ T B C 遇到 ‘(‘，k = 1 (左子树) 遇到 ‘,’，k = 2 (右子树) 1 2 3 4 5 A top B 2019/1/14

T 遇到 ‘)‘，左右子树都处理完，根结点出栈 1 2 3 4 5 A top B D E 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) 字符 14=, (逗号)
又遇到 ‘,‘，后面字符表示右子树，根结点在栈顶 A B C D E G ^ T 1 2 3 4 5 A top B D 2019/1/14

T F 连续的 ‘)‘，连续的出栈，最终栈空且字符串结束，二叉链表创建完成！ 1 2 3 4 5 A top B D 2019/1/14

BiTree CreateBiTree(char *str) { // str: 括号表示串
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char *str) { // str: 括号表示串 } //end = A ( B( C, D( E( ,G), F) ) ) 2019/1/14

BiTree CreateBiTree(char * str) { BiTree T;
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str) { BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = 0; //栈顶指针 } //end T 1 2 3 4 5 top st 2019/1/14

BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 } //end P k = 1 (左子树) k = 2 (右子树) 2019/1/14

(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 int j = 0; //当前字符下标 (初始 = 0 ) char ch; //当前字符 } //end j = 8 str = A ( B ( C , D ( E ( , G ) , F ) ) ) ch = str [j] 2019/1/14

(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 int j = 0; //当前字符下标 (初始 = 0 ) char ch; //当前字符 bt = NULL; //根指针初始为空 ch = str [j]; //读入第 1 个字符 2019/1/14

BiTree CreateBiTree(char * str){
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 j ++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

BiTree CreateBiTree(char * str){
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

BiTree CreateBiTree(char * str){ ……
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++; st [top] = p; k=1 ; break; } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++ ; st [top] = p ; k=1 ; break; case ‘)’: //右括号，左右子树都处理完，出栈 top -- ; break; } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 2019/1/14

(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++ ; st [top] = p ; k=1 ; break; case ‘)’: //右括号，左右子树都处理完，出栈 top -- ; break; case ‘,’: //逗号，准备处理右子树 k=2 ; break; } //end switch 2019/1/14

(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 default: //其它字符(即数据) p = (BiTNode *)malloc (sizeof (BiTNode)); //创建结点 p->data = ch; //保存数据 p->lchild = NULL; //初始化左右指针 p->rchild = NULL; } //end switch 2019/1/14

BiTree CreateBiTree(char * str){ …… default: //其它字符(即数据)
(5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… default: //其它字符(即数据) //新结点与栈顶结点链接 if ( bt == NULL ) //空树，新结点是根 bt = p; else if ( k == 1 ) //新结点是栈顶结点的左孩子 st [ top ] -> lchild = p ; else if ( k == 2 ) //新结点是栈顶结点的右孩子 st [ top ] -> rchild = p; } //end switch 2019/1/14

6.3 遍历二叉树树的遍历遍历——按某条路径访问二叉树的每个结点，使每个结点被访问一次且仅被访问一次常用方法
先根（序）遍历：访问根结点；依次先根遍历根的每棵子树后根（序）遍历：依次后根遍历每棵子树；访问根结点层次遍历：访问第一层结点；依次遍历第二层，…第n层结点 2019/1/14

二叉树遍历先序：访问根结点；先序遍历左子树、右子树中序：中序遍历左子树；访问根结点；中序遍历右子树后序：后序遍历左、右子树；访问根结点
层次：从上到下、从左到右访问各层结点 D L R LDR、LRD、DLR RDL、RLD、DRL 2019/1/14

先序遍历: 先序遍历序列：A B D C D L R D L R A D L R A D B C B > D L R C >
2019/1/14

中序遍历: 中序遍历序列：B D A C L D R A L D R A D B C L D R > L D R B > C
2019/1/14

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B D > B > > C
2019/1/14

- + a * b - c d / e f a + b * c - d - e / f a b c d - * + e f / -
先序遍历： a + b * c - d - e / f 中序遍历： a b c d - * + e f / - 后序遍历： 2019/1/14

二叉树遍历（递归）算法 //二叉链表定义 typedef int TElemType ; typedef struct BiTNode {
TElemType data; struct BiTNode *lchild, *rchild; } BiNode , *BiTree ; lchild data rchild 2019/1/14

先序遍历（递归）算法 int PreOrderTraverse ( BiTree T ) {
if ( T != NULL) { //遍历指针不空，指向某子树根结点 printf ( “%d\t” , T->data ); //根 PreOrderTraverse ( T->lchild ); //左 PreOrderTraverse ( T->rchild ); //右 } 2019/1/14

A > B C > > D > > T A printf(A); pre(T L); pre(T R); T
int PreOrderTraverse ( BiTree T ) { if ( T != NULL) { printf ( “%d\t” , T->data ); PreOrderTraverse ( T->lchild ); PreOrderTraverse ( T->rchild ); } T A printf(A); pre(T L); A pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); T > 左是空返回 B C pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回主程序 pre( T ) 返回 pre(T R); 返回返回先序序列：A B D C pre(T R); 返回 2019/1/14

int InOrderTraverse ( BiTree T ) { if ( T != NULL) {
/// 中序遍历 int InOrderTraverse ( BiTree T ) { if ( T != NULL) { InOrderTraverse ( T->lchild ); //左 printf ( “%d\t” , T->data ); //根 InOrderTraverse ( T->rchild ); //右 } 2019/1/14

int PostOrderTraverse ( BiTree T ) { if ( T != NULL) {
/// 后序遍历 int PostOrderTraverse ( BiTree T ) { if ( T != NULL) { PostOrderTraverse ( T->lchild ); //左 PostOrderTraverse ( T->rchild ); //右 printf ( “%d\t” , T->data ); //根 } 2019/1/14

由先序和中序遍历结果可以唯一确定一棵二叉树。由后序和中序遍历结果可以唯一确定一棵二叉树。由先序和后序遍历结果不能唯一确定一棵二叉树。
说明：对于先序、中序、后序遍历序列中：由先序和中序遍历结果可以唯一确定一棵二叉树。由后序和中序遍历结果可以唯一确定一棵二叉树。由先序和后序遍历结果不能唯一确定一棵二叉树。若二叉树的先序、中序序列相同，则该二叉树的形态为：空树、只有根结点、右单支若二叉树的后序、中序序列相同，则该二叉树的形态为：空树、只有根结点、左单支若二叉树的先序、后序序列相同，则该二叉树的形态为：空树、只有根结点 2019/1/14

例：二叉树的先序、中序遍历结果如下，画出该二叉树先序：ABCDEFG 中序：CBDEAFG
2019/1/14

1、二叉树的后序、中序周游结果如下，画出该二叉树。后序：43268751 （每位数字代表一个结点）中序：24316578
练习： 1、二叉树的后序、中序周游结果如下，画出该二叉树。后序：（每位数字代表一个结点）中序： 2、一个二叉树的先序、中序和后序分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。先序：__B__F__ICEH__G 中序：D__KFIA__EJC__ 后序：__K__FBHJ__G__A 答: ABDFKICEHJG DBKFIAHEJCG DKIFBHJEGCA 2019/1/14

按先序遍历序列，建立二叉链表 A B C 0 0 D E 0 G 0 0 F 0 0 0 (0 表示空) A B C D E F G
2019/1/14

scanf(“%c”, &ch); //读入 1 个字符 if ( ch ==‘0’) //空 bt = NULL; else {
按先序遍历序列，递归建立二叉链表算法 BiTree createbt ( ) { BiTree *bt; char ch; scanf(“%c”, &ch); //读入 1 个字符 if ( ch ==‘0’) //空 bt = NULL; else { bt = (BiTree) malloc ( sizeof ( BiNode )); bt->data = ch; bt->lchild = createbt (); //递归读入左子树 bt->rchild = createbt (); //递归读入右子树 } 2019/1/14

6.3.2 线索二叉树定义：二叉树遍历序列中两个相邻结点互称为前驱与后继指向前驱或后继结点的指针称为线索加上线索的二叉树叫线索二叉树
按遍历序列使二叉树变为线索二叉树的过程叫线索化 2019/1/14

6.3.2 线索二叉树实现 n 个结点的二叉链表中，必有 n+1 个空链域扩展二叉链表结点：标志域 LTag、RTag
LTag：表示 lchild 指针的含义，0—左孩子；1—前驱 RTag：表示 rchild 指针的含义，0—右孩子；1—后继 lchild LTag data RTag rchild 2019/1/14

Ex.1 先序线索二叉树 A B C D E A B D C E T 先序序列：ABCDE 先序线索二叉树 1 1 1 1 1 1 ^
1 1 1 1 1 1 ^ 2019/1/14

Ex.2 中序线索二叉树 A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 ^ 1 1 ^ 1 1 1 1
^ 1 1 ^ 1 1 1 1 2019/1/14

Ex.3 后序线索二叉树 A B C D E A B D C E T 后序序列：CBEDA 后序线索二叉树 1 1 ^ 1 1 1 1
1 1 ^ 1 1 1 1 2019/1/14

6.3.2 线索二叉树二叉树线索化的目的遍历时，不再需要栈 2019/1/14

6.4 树和森林树 vs. 二叉树森林相同点：层次结构、唯一根结点
差异点：树结点允许 2 个以上的子结点；二叉树结点最多 2 个子结点森林不相交的树集合 2019/1/14

6.4.1 树的存储结构双亲表示法孩子表示法多重链表孩子链表孩子兄弟表示法 2019/1/14

6.4 树和森林 6.4.1 树的存储结构双亲表示法：子结点保存父结点位置信息 //结点结构
数据域：存放结点本身信息双亲域：指示双亲结点在数组中位置 //结点结构 typedef struct PTNode { TElemType data; int parent; } PTNode; data parent 数据域双亲域 2019/1/14

6.4 树和森林 6.4.1 树的存储结构双亲表示法 …… 1 2 data parent // 双亲表示的树结构
1 2 MAX_TREE_SIZE data parent …… 结点数组 // 双亲表示的树结构 typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r, n; } PTree; 根结点位置结点个数 2019/1/14

双亲表示法示例如何找孩子结点如何找兄弟结点 6 1 2 3 4 5 7 8 9 data parent a b c d e f h g
1 2 3 4 5 7 8 9 data parent a b c d e f h g i a c d e f g h i b 1 1 2 2 3 5 如何找孩子结点如何找兄弟结点 5 根结点放在位置 1 5 1 9 结点数＝9 2019/1/14

6.4.1 树的存储结构孩子表示法(多重链表) 每个结点有多个指针域，分别指向其子树的根结点同构：结点指针个数相等＝树的度 D
data child1 child2 ………. childD 树的度＝ D 结点不同构：结点指针个数不等＝结点的度 d data degree child1 child2 ………. childd 结点的度＝ d 2019/1/14

^ ^ ^ ^ ^ 孩子表示法示例如何找双亲结点 6 1 2 3 4 5 7 8 9 a c d e f g h i b data
1 2 3 4 5 7 8 9 a c d e f g h i b data firstchild a b c d e f h g i 2 3 ^ 4 5 ^ 6 ^ ^ 9 7 8 ^ ^ ^ 如何找双亲结点 ^ ^ 1 9 2019/1/14

6.4.1 树的存储结构带双亲的孩子链表 int parent; parent：指示父结点位置 firstchild：孩子链表头指针
//表头数组元素结点 typedef struct { TElemType data; int parent; ChildPtr firstchild; //孩子链表头指针 } CTBox ; 父结点在数组中的位置 2019/1/14

^ 带双亲的孩子链表法示例 a b c d e f h g i 6 1 2 3 4 5 7 8 9 a c d e f g h i b
data ^ parent firstchild 2019/1/14

6.4.1 树的存储结构孩子兄弟表示法(二叉链表) 左指针  自己的第 1 个孩子结点右指针  自己的下一个兄弟
typedef struct CSNode { TElemType data; struct CSNode *firstchild, //第一个孩子 *nextsibling; //下一个兄弟 } CSNode, *CSTree; 2019/1/14

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 孩子兄弟表示法示例问题：破坏了树的层次关系 a b c d e f h g i a b c d e
2019/1/14

孩子兄弟表示法的另类解释！二叉链表即可表示树也可表示二叉树 ^ a b c d e f h g i a b c d e f h g i
2019/1/14

树与二叉树之间可以一一对应！可以相互转换 ^ 二叉链表即可表示树，也可表示二叉树 a b c d e f h g i a b c d e
2019/1/14

将树转换成二叉树 6.4.2 森林与二叉树的转换加线抹线旋转兄弟之间加连线除左孩子外，去除与其余孩子之间的连线
以根结点为轴心，整树顺时针旋转 45° 2019/1/14

树转换成二叉树示例加线、抹线、旋转转换得到的二叉树其右子树一定为空 A B C D E F G H I A B C D E F G H
2019/1/14

二叉树转换成树加线若结点 p 是其父结点的左孩子，则将 p 的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p 的父结点连线抹线抹掉原二叉树中父结点与右孩子之间的连线调整将结点按层次排列，形成树结构 2019/1/14

二叉树转换成树示例加线、抹线、调整 A B C D E F G H I A B C D E F G H I A B C D E F G H
2019/1/14

森林转换成二叉树 6.4.2 森林与二叉树的转换（树）转换（根）连线旋转各棵树分别转换成二叉树每棵树根结点用线相连
第一棵树根结点为二叉树根以根结点为轴顺时针旋转，构成二叉树型结构 2019/1/14

森林转换成二叉树示例 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J
树转换 A B C D E F G H I J A B C D E F G H I J 旋转根连线 2019/1/14

二叉树转换成树或森林 6.4.2 森林与二叉树的转换加线抹线还原
若结点是左孩子，则将该结点的右孩子、右孩子的右孩子，…都与该结点的父结点连线抹线抹去原二叉树中所有父结点与右孩子之间的连线还原整理上两步的结果，使之结构层次分明 2019/1/14

二叉树转换成树或森林加线、抹线、还原 A B C D E F G H I J A B C D E F G H I J A B C D E
调整 A B C D E F G H I J 2019/1/14

6.6 赫夫曼树及其应用 Huffman树结点带权路径长度：根到该结点的路径长度与该结点权值的乘积
树带权路径长度：所有叶结点的带权路径长度之和 Huffman树设有 n 个权值 {w1,w2,……wn} 构造有 n 个叶结点的二叉树，其叶子结点的权值＝wi WPL 最小的二叉树叫 Huffman 树 2019/1/14

例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树
a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 WPL=7*3+5*3+2*1+4*2=46 树的带权路径长度最短 WPL=7*1+5*2+2*3+4*3=35 2019/1/14

Huffman 树的构造给定 n 个权值 {w1,w2,……wn} [1] 初始化：构造 n 棵只有根结点的二叉树，权值为 wj
[2] 迭代选择(贪心)：森林中选取 2 棵根结点权值最小的树作左右子树，构造一棵新二叉树新二叉树根结点权值＝左右子树根结点权值和 [3] 重复步骤[2]，直到只剩一棵树时，算法结束 2019/1/14

练习：w = { 5, 29, 7, 8, 14, 23, 3, 11 } 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 29 23 14 7 15 29 14 8 7 15 11 3 5 19 23 42 2019/1/14

练习：w = { 5, 29, 7, 8, 14, 23, 3, 11 } 271 Huffman 树可以不唯一！ 29 14 8 7 15
19 23 42 11 3 5 8 19 23 42 29 14 7 15 58 11 3 5 8 19 23 42 29 14 7 15 58 100 WPL=？ 271 Huffman 树可以不唯一！ 2019/1/14

Huffman 树的应用：Huffman 编码
数据通信，压缩电文用的二进制编码 Ex. 设要传送的字符串＝ABACCDA (定长)编码：A—00 B—01 C—10 D—11 位若采用不等长编码，让出现次数较多的字符尽可能用短编码则转换的二进制字符串便可能减少 2019/1/14

若编码为： A—0 B—00 ABACCDA C—1 D---01 000011010 9位但： 0000 AAAA ABA BB
但： AAAA ABA BB 重码位关键：不等长编码方案中，必须使任一字符的编码都不是另一个字符的编码的前缀，即前缀编码 2019/1/14

前缀编码 A C B D 1 编码方案：A—0 B—110 C—10 D—111 要传送的字符串＝ABACCDA
A C B D 1 规定：左分支用“0”表示右分支用“1”表示前缀编码二叉树 2019/1/14

前缀编码译码：从根出发，逐个接收字符，遇“0”向左、遇“1”向右，到达叶子、译出一个字符 A C B D 1 A B A C C D A 2019/1/14

练习电文由字母 S, W, P, U, C, T, E, D 组成，字母出现频率(%)为 5, 25, 3, 6, 10, 11, 36, 4 画出 Huffman 树，给出 Huffman 编码求出平均码长给出电文 swpucsse 的对应编码串给出编码串的对应电文 2019/1/14

画出 Huffman 树，给出 Huffman 编码
字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 画出 Huffman 树，给出 Huffman 编码 100 61 39 36 25 22 17 7 10 11 4 3 6 5 P D C T S U W E 1 S W P U C T E D 0110 10 0000 0111 001 010 11 0001 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 求出平均码长 (4×5＋2×25＋4×3＋4×6＋3×10＋3×11＋2×36＋4 ×4)/100 2.57 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 给出电文 swpucsse 的对应编码串 S W P U C T E D 0110 10 0000 0111 001 010 11 0001 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 给出编码串的对应电文 DSTE 100 61 39 36 25 22 17 7 10 11 4 3 6 5 P D C T S U W E 1 2019/1/14

例 w={5, 29, 7, 8, 14, 23, 3, 11} typedef struct { unsigned int weight;
下标 weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 typedef struct { unsigned int weight; unsigned int parent , lchild , rchild ; } HTNode , *HuffmanTree ; 2019/1/14

int Huffman( HuffmanTree HT, int *w , int n ) {
for( i = 1 ; i < 2*n ;i++) { // 初始化 HT[i].parent = HT[i].lchild = HT[i].rchild = 0; if (i <= n) HT[i].weight = w[i-1]; // 前 n 个结点赋权值 else HT[i].weight = 0; // 后 n-1 个结点预留 } //初始化结束 // 待续… 2019/1/14

int Huffman( HuffmanTree HT, int *w , int n ) { // …续
for ( i = n+1 ; i <=2*n-1 ; i++) { // 构造 HUFFMAN树 Select ( HT , i - 1 , &s1, &s2 ) ; // 最小及次小权元下标 HT[s1].parent = i; // 设置新根结点 HT[s2].parent = i; HT[i].weight = HT[s1].weight + HT[s2].weight ; // 权值和 HT[i].lchild = s1; // 根结点与子结点链接 HT[i].rchild = s2; } //结束构造 } 2019/1/14

Huffman树频率={ 5, 29, 7, 8, 14, 23, 3, 11 } n = 8 存储静态 Huffman 树的数组尺寸：
下标 weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 10 12 13 15 频率={ 5, 29, 7, 8, 14, 23, 3, 11 } n = 8 存储静态 Huffman 树的数组尺寸： 2*n – 1 = 15 初始化 2019/1/14

i = n+1 = 9 在前 i -1 = 8 个元素中找无父结点且有最小及次小权值元素的下标 s1 = 7 s2 = 1
构造新结点，存储于下标为 i = 9 的元素中权值=最小及次小权和 = = 8 构造以元素9为根的子二叉树 index weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 10 12 13 15 9 8 7 1 2019/1/14

i + 1 = 10 在前 i -1 = 9 个元素中找无父结点且有最小及次小权值元素的下标 s1 = 3 s2 = 4
新结点存储于元素10 权值 = = 15 构造元素10的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 12 13 2019/1/14

i + 1= 11 在前 i -1 = 10 个元素中找无父结点且有最小及次小权值元素的下标 s1 = 9 s2 = 8
新结点存储于元素11 权值 = = 19 构造元素11的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 19 12 13 2019/1/14

新结点存储于元素12 权值 = = 29 构造元素12的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 11 15 19 13 2019/1/14

i + 1= 13 在前 i -1 = 12 个元素中找无父结点且有最小及次小权值元素的下标 s1 = 11 s2 = 6
新结点存储于元素13 权值 = = 42 构造元素13的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 13 11 15 19 42 2019/1/14

新结点存储于元素14 权值 = = 58 构造元素14的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 2019/1/14

新结点存储于元素15 权值 = = 100 构造元素15的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 100 2019/1/14

第六章树 2019/1/14.

Similar presentations

Presentation on theme: "第六章树 2019/1/14."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

第六章 树 2019/1/14.

Similar presentations

Presentation on theme: "第六章 树 2019/1/14."— Presentation transcript:

Similar presentations

About project

反馈

第六章树 2019/1/14.

Presentation on theme: "第六章树 2019/1/14."— Presentation transcript: