nullnull 6.1 树的定义和基本术语第六章 树和二叉树 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.5 赫夫曼树及其应用 6.4 树和森林树的定义(逻辑关系)树的定义(逻辑关系) 树(Tree)是n(n>=0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:
(1)有且仅有一个特定的称为根(Root)的结点;
(2) 其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm,其中每个子集又是一棵树,并称其为子树(Subtree)。
树的基本概念树的基本概念结点(node)
根结点(root)、叶子/叶结点(leaf)
孩子结点(child)、双亲结点(parent)、 兄弟(brother)
度(degree)
结点的度
树的度:max(结点的度)
树的深度/高度(depth):max(结点的层次)
森林(forest)树的基本术语树的基本术语子女:若结点的子树非空,结点子树的根即为该结点的子女。
父结点:若结点有子女,该结点是子女的父结点。null兄弟:同一结点的子女互称为兄弟。
度:结点的子女个数即为该结点的度;
树中各个结点的度的最大值称为树的度。
分支结点:度不为0的结点即为分支结点,亦称为非终端结点。
叶结点:度为0的结点即为叶结点,亦称为终端结点。null结点的层次:规定根结点在第一层,其子女结点的层次等于它的层次加一。以下类推。
深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。6.2.1 二叉树的定义和基本术语6.2.1 二叉树的定义和基本术语二叉树的定义
是一颗空树
或是由根及两颗不相交的左子树、右子树构成,并且左、右子树本身也是二叉树。
(a)
空二叉树AABABACB (b)
根和空的左右子树 (c)
根和左子树(d)
根和右子树 (e)
根和左右子树
度不大于2的有向树称为二叉树null说明
1)二叉树中每个结点最多有两颗子树;二叉树每个结点度小于等于2;
2)左、右子树不能颠倒——有序树;
3)二叉树的定义是递归结构,在二叉树的定义中又用到了二叉树的概念;二叉树的逻辑结构二叉树的逻辑结构二叉树是一种非线性的数据结构null两种特殊的二叉树
1)满二叉树:如果深度为k的二叉树,有2k-1个结点则称为满二叉树;K=3的满二叉树K=2的满二叉树5.2.1 二叉树的概念null 2)完全二叉树:如果一颗二叉树只有最下一层结点数可能未达到最大,并且最下层结点都集中在该层的最左端,则称为完全二叉树;(a)(c)(b)、(b)完全二叉树
(c) 不是完全二叉树5.2.1 二叉树的概念6.2.2 二叉树的性质性质1 在二叉树的第i 层上最多有2i-1个结点
性质2 深度为k的二叉树最多有 2k-1 个结点
性质3 设二叉树叶子结点数为n0,度为2的结点n2,则n0 = n2 +16.2.2 二叉树的性质null下面是两个关于完全二叉树的性质
性质4 具有n个结点的完全二叉树的深度为:log2 n +1.
对完全二叉树的结点编号:从上到下,每一层从左到右123456性质5:在完全二叉树中编号为i的结点
1)若有左孩子,则左孩编号为2i
2)若有右孩子,则右孩子结点编号为2i+1
3)若有双亲,则双亲结点编号为 i/26.2.3 二叉树的存储结构6.2.3 二叉树的存储结构 1 二叉树的顺序结构
适于满二叉树或完全二叉树的存储。 0 1 2 3 4 5 6 n-1A B C D E F逻辑结构存储结构null1672453810 E9null 6.3 遍历二叉树和线索二叉树 一、遍历:按某种搜索路径访问二叉树的每个结
点,而且每个结点仅被访问一次。树结构(非线性结构)→线性结构。null 6.3 遍历二叉树和线索二叉树 一、遍历:按某种搜索路径访问二叉树的每个结
点,而且每个结点仅被访问一次。令:L:遍历左子树 D:访问根结点 R:遍历右子树
有六种遍历
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
:
DLR,LDR,LRD,
DRL,RDL,RLDnull1.先序遍历先序序列:ABDEJCFIGFlashnull2.中序遍历中序序列:DBJEAFICGFlashnull3.后序遍历后序序列:DJEBIFGCAFlashnull 二、遍历的算法描述先序遍历Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ if (T) //非空树
{if(Visit(T->data))
if(PreOrderTraverse(T->lchild, Visit)) if(PreOrderTraverse(T->rchild, Visit))
return OK;
}else return ERROR;
}//PreOrderTraversenullnull 二、遍历的算法描述中序遍历void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ if (T)
{ InOrderTraverse(T->lchild, Visit);
Visit(T->data); InOrderTraverse(T->rchild, Visit);
}//if }//InOrderTraversenull 二、遍历的算法描述后序遍历void PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ if (T)
{ PostOrderTraverse(T->lchild, Visit); PostOrderTraverse(T->rchild, Visit);
Visit(T->data);
}//if }//PostOrderTraversenull 二、遍历的算法描述层次遍历遍历序列:AABCBDCEFGDEFGnull三. 二叉树遍历的应用1. 建立二叉树的存储结构——二叉链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
遍历操作访问二叉树的每个结点,而且每个结点仅被访问一次。是否可以利用遍历,建立二叉链表的所有结点并完成相应结点的链接?问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的提出null三. 二叉树遍历的应用1. 建立二叉树的存储结构——二叉链表输入:二叉树的先序序列
结果:二叉树的二叉链表基本思想:扩展二叉树 先序序列:ABDFCE 先序序列:ABD#F###CE###二叉树的链式存储结构二叉树的链式存储结构typedef struct bnode
{ char data;
struct node *lchild,*rchild;
}btree;二叉链表的类型定义(C语言描述)逻辑结构存储结构null 3 三叉链表
三叉链表中每个结点包含四个域:数据域、双亲指针域、左指针域、右指针域Struct node
{ int data;
struct node *lch,*rch,*parent;
};nullStatus CreateBiTree(BiTree &T)
{ scanf (&ch);
if (ch= = ‘# ’) T=NULL;
else
{ if (! (T=(BiTNode * )malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch; // 建立(根)结点
CreateBiTree(T->lchild); //构造左子树链表
CreateBiTree(T->rchild); //构造右子树链表
}//if
return OK;
}//CreateBiTree1. 建立二叉树的存储结构——二叉链表null三. 二叉树遍历的应用2. 编写求二叉树叶子结点的算法输入:二叉树的二叉链表
结果:二叉树的叶子结点个数
基本思想:遍历操作访问二叉树的每个结点,而
且每个结点仅被访问一次。所以可在
二叉树遍历的过程中,统计叶子结点
的个数。nullvoid leaf(BiTree T)
{ //n为全局变量,用于累加二叉树的叶子结点的个数
//第一 次被调用时,n=0
if(T)
{ if(T->lchild==NULL&&T->rchild==NULL)
n=n+1;
leaf(T->lchild);
leaf(T->rchild);
}//if
}//leaf三. 二叉树遍历的应用2. 编写求二叉树叶子结点的算法nullvoid leaf(BiTree T)
{ if(T)
{ if (T->lchild==NULL&&T->rchild==NULL) n=n+1;
leaf(T->lchild);
leaf(T->rchild);
}//if
}//leafviod PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ if (T) {
Visit(T->data); PreOrderTraverse(T->lchild, Visit); PreOrderTraverse(T->rchild, Visit);
}//if
}//PreOrderTraversenull四、由遍历序列恢复二叉树先序序列:
A, B, D, E, J, C, F, I, G中序序列:
D, B, J, E, A, F, I, C, Gnull二叉树的计数二叉树的计数二叉树遍历的结果是将一个非线性结构中的数据通过访问排列到一个线性序列中。
前序序列:a b d c e 特点是第一个访问的a一定是树根,只要左子树非空,后面紧跟的b 一定是根的左子女,…
中序序列:b d a e c 特点是树
根 a 把整个中序分成两部分,
a 左侧子序列是根的左子树上
的结点数据,右侧子序列是根
的右子树上的结点数据。abcdenull由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。
例, 前序序列 { A B H F D E C K G } 和中序序列 { H B D F A E K C G }, 构造二叉树过程如下:
前序序列 { A B H F D E C K G }前序序列 { A B H F D E C K G }null如果前序序列固定不变,给出不同的中序序列,可得到不同的二叉树。
固定前序排列,选择所有可能的中序排列,可能构造多少种不同的二叉树?null例如, 有 3 个数据 { 1, 2, 3 },可得 5 种不同的二叉树。它们的前序排列均为 123,中序序列可能是 321,231,213,132,123。
前序序列为 123,中序序列为 312 的二叉树不存在。null有0个, 1个, 2个, 3个结点的不同二叉树如下null练习: 一棵二叉树的
中序序列是DCEFBHGAKJLIM,
后序序列是DFECHGBKLJMIA,
构造出这棵二叉树,并写出它的先序序列。null先序序列:
ABCDEFGHIJKLM练习: 一棵二叉树的
中序序列是DCEFBHGAKJLIM,
后序序列是DFECHGBKLJMIA,
构造出这棵二叉树,并写出它的先序序列。null假设一棵二叉树的后序遍历序列为
D G J H E B I F C A,中序遍历序列为
D B G E H J A C I F,则其前序遍历序列
为 。
A)A B C D E F G H I J
B)A B D E G H J C F I
C)A B D E G H J F I C
D)A B D E G J H C F Inull 若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD,则该二叉树的后序遍历序列为 (38) 。 A. PBCDE B. DECBP
C. EBDCP D. EBPDCnull二叉树的查找有深度优先和广度优先二类,深度优先包括_C_。当一棵二叉树的前序序列和中序序列分别是
H G E D B F C A 和 E G B D H F A C时,其后序序列必是_D_,层次序列为_E_.
C: (1)前序遍历 后序遍历 中序遍历
(2)前序遍历 后序遍历 层次遍历
(3)前序遍历 中序遍历 层次遍历
(4)中序遍历 后序遍历 层次遍历
D: (1) B D E A G F H C
(2) E B D G A C F H
(3) H G F E D C B A
(4) H F G D E A B CE: (1) B D E A C G F H
(2) E B D G A C F H
(3) H G F E D C B A
(4) H F G C D E A Bnull 6.3 遍历二叉树和线索二叉树问题的提出:中序遍历序列:D G B A E C Fnull 6.3 遍历二叉树和线索二叉树问题的提出:中序遍历序列:D G B A E C Fnull 6.3 遍历二叉树和线索二叉树问题的提出:如何不重复存储,节省存储空间?null 6.3 遍历二叉树和线索二叉树问题的提出:null 6.3 遍历二叉树和线索二叉树如何将二叉链表与中序链表结合?线索:将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索;
线索化:使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化;
线索二叉树:加上线索的二叉树称为线索二叉树。将二叉链表中的空指针域指向其前驱结点和后继结点 五. 线索二叉树null 6.3 遍历二叉树和线索二叉树有n个结点的二叉链表存在n+1个空链域。 空链域=2n0+n1(叶子结点有两个空链域,度为1的结点有一个空链域)
二叉树性质3有:n0=n2+1
空链域=n0+n1+n2+1
=n+1证明 五. 线索二叉树null 6.3 遍历二叉树和线索二叉树有n个结点的二叉链表存在n+1个空链域。证明 五. 线索二叉树ABCDEFGHT^^^^^^^^^null中序序列:D, B, H, E, A, F, C, G 6.3 遍历二叉树和线索二叉树 五. 线索二叉树null 六. 线索二叉树的构造 6.3 遍历二叉树和线索二叉树如何区分孩子结点和前驱后继结点?null 六. 线索二叉树的构造 6.3 遍历二叉树和线索二叉树null 七. 线索二叉树的存储typedef enum PointerTag {link,thread};
typedef struct BiThrNode
{ TElemType data;
Struct BiThrNode *lchild, *rchild;
PointerTag Ltag, Rtag;
} BiThrNode,*BiThrTree; 6.3 遍历二叉树和线索二叉树null 八. 线索二叉树的遍历 6.3 遍历二叉树和线索二叉树 二叉树的遍历方式有4种,故有4种意义下的前驱和后继,相应的有4种线索二叉树:
⑴ 先序线索二叉树
⑵ 中序线索二叉树
⑶ 后序线索二叉树
⑷ 层序线索二叉树null 八. 线索二叉树的遍历 6.3 遍历二叉树和线索二叉树分析:首先需要建立线索链表,其实质就是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历该二叉树时才能得到。null 八. 线索二叉树的遍历 为简化线索链表的遍历算法,仿照线性链表,为线索链表加上一头结点。 约定: 头结点的lchild域指向二叉树的根结点; 头结点的rchild域指向中序序列最后一个结点; 中序序列第一结点lchild域指向头结点; 中序序列最后一个结点的rchild域指向头结点;中序序列:D, B, H, E, A, F, C, G 6.3 遍历二叉树和线索二叉树null中序序列:D, B, H, E, A, F, C, G00000000000000001头结点的lchild域指向二叉树的根结点; 头结点的rchild域指向中序序列最后一个结点; 中序序列第一结点lchild域指向头结点; 中序序列最后一个结点的rchild域指向头结点;∧∧∧∧∧∧∧∧∧0111111111nullStatus InOrderTraverse_Thr(BiThrTree T,
Status (* visit) (TE1emType e))
{ p=T->lchild; //p指向根结点
While(p!=T) { // 空树或遍历结束时,p= =T
While(p->LTag= =Link) p= p->lchild;
if(!Visit(p->data)) return ERROR;
while (p->RTag= =Thread && p->rchild!=T)
{p=p->rchild; visit(p->data); }
p=p->rchild;
}
return OK;
}//InOrderTraverse_Thr算法T指向根结点P134null中序序列:D, B, H, E, A, F, C, Gnull九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G00000000000000001∧∧∧∧∧∧∧∧∧0111111111P134null九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G00000000000000001∧∧∧∧∧∧∧∧∧0null九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G00000000000000001∧∧∧∧∧∧∧∧∧011第一个结点处理完毕null九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G00000000000000001∧∧∧∧∧∧∧∧∧0111第二个结点处理完毕null九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G000000001∧111111110∧最后一个结点处理完毕null九. 二叉树的线索化 6.3 遍历二叉树和线索二叉树中序序列:D, B, H, E, A, F, C, G000000001∧111111111线索化完成