数据结构二叉树教学.pptxVIP

第六章树和二叉树

6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码

6.1树的类型定义

数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：

基本操作：查找类插入类删除类

Root(T)//求树的根结点1Value(T,cur_e)//求当前结点的元素值2Parent(T,cur_e)//求当前结点的双亲结点3LeftChild(T,cur_e)//求当前结点的最左孩子4RightSibling(T,cur_e)//求当前结点的右兄弟5TreeEmpty(T)//判定树是否为空树6TreeDepth(T)//求树的深度7TraverseTree(T,Visit())//遍历8查找类：

InitTree(T)//初始化置空树01CreateTree(T,definition)//按定义构造树02Assign(T,cur_e,value)//给当前结点赋值03InsertChild(T,p,i,c)//将以c为根的树插入为结点p的第i棵子树04插入类：

ClearTree(T)//将树清空1DestroyTree(T)//销毁树的结构2DeleteChild(T,p,i)//删除结点p的第i棵子树3删除类：

ABCDEFGHIJMKLA()T1T3T2树根例如:B(E,F(K,L)),C(G),D(H,I,J(M))

(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。

基本术语

结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM

(从根到结点的)路径：孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次

森林：任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF

对比树型结构和线性结构的结构特点

线性结构~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~树型结构一个后继)(无后继)(无后继)最后一个数据元素多个叶子结点(无前驱)(一个前驱、根结点其它数据元素(无前驱)(一个前驱、多个后继)第一个数据元素其它数据元素

6.2二叉树的类型定义

二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF

N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的五种基本形态：

01二叉树的主要基本操作：03插入类02查找类04删除类

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

213InitBiTree(T);Assign(T,e,value);CreateBiTree(T,definition);4InsertC