树和二叉树part1课件

第六章树和二叉树

主讲：戚玉涛第六章树和二叉树主讲：戚玉涛1第6章树和二叉树

树型结构是一类重要的非线性数据结构。现实生活中有着广泛存在。如：家谱，组织机构关系等。在计算机领域中树在编译程序和数据库系统中也得到了广泛的应用。直观来看树是以分支关系来定义的层次结构，其中以树和二叉树最为常用。第6章树和二叉树树型结构是一类重要的非线性数据结构。2第6章树和二叉树6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码第6章树和二叉树6.1树的类型定义3树的类型定义数据对象D：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。树的类型定义数据对象D：4举例：举例：5树的类型定义基本操作：查找类插入类删除类树的类型定义基本操作：6

Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历Root(T)//求树的根结点查找类：Val7InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树InitTree(&T)//初始化置空树插入类：C8

ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ClearTree(&T)//将树清空删除类：De9树的逻辑表示法(1)树型表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。树的逻辑表示法(1)树型表示法。这是树的最基本的表示,使10树的逻辑表示法(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。树的逻辑表示法(2)文氏图表示法。使用集合以及集合的包含关系11树的逻辑表示法(3)凹入表示法。使用线段的伸缩描述树结构。树的逻辑表示法(3)凹入表示法。使用线段的伸缩描述树结构。12树的逻辑表示法(4)括号表示法(广义表表示法)。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。树的逻辑表示法(4)括号表示法(广义表表示法)。将树的根结点13树的分类有向树：(１)有确定的根；(２)树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。树的分类有向树：14对比树型结构和线性结构的结构特点线性结构第一个数据元素(无前驱)最后一个数据元素(无后继)其它数据元素(一个前驱、一个后继)树型结构根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点线性结构树型结构15树的基本术语结点：包含一个数据元素及若干指向其子树的分支。结点的度(degree)：结点拥有的子树个数。树的度：树内各结点的度的最大值。叶子(leaf)：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。除根结点外，分支结点也称为内部结点。树的基本术语结点：包含一个数据元素及若干指向其子树的分支。16树的基本术语(从根到结点的)路径：由从根到该结点所经分支和结点构成。孩子、双亲、兄弟、堂兄弟：结点的子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。同一双亲的孩子之间互称兄弟。其双亲在同一层的结点互为堂兄弟。B、C、D是A的孩子。A是B、C、D的双亲。结点H、I、J互为兄弟结点。树的基本术语(从根到结点的)路径：由从根到该结点所经分支和17树的基本术语路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径。用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。树的基本术语路径与路径长度：对于任意两个结点ki和kj,若树18树的基本术语结点的祖先：从根结点到该结点的路径上的所有结点。结点的子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。1234结点的层次：假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树的高度(深度)：树中结点的最大层次。树的基本术语结点的祖先：从根结点到该结点的路径上的所有结点。19树的基本术语森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给m棵独立的树增加一个根结点，并把这m棵树作为该结点的子树，森林就变成一棵树。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林rootABCDEFGHIJMKLF树的基本术语森林：m（m≥0）棵互不相交的树的集合。将一棵20第六章树和二叉树

主讲：戚玉涛第六章树和二叉树主讲：戚玉涛21第6章树和二叉树

树型结构是一类重要的非线性数据结构。现实生活中有着广泛存在。如：家谱，组织机构关系等。在计算机领域中树在编译程序和数据库系统中也得到了广泛的应用。直观来看树是以分支关系来定义的层次结构，其中以树和二叉树最为常用。第6章树和二叉树树型结构是一类重要的非线性数据结构。22第6章树和二叉树6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码第6章树和二叉树6.1树的类型定义23树的类型定义数据对象D：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。树的类型定义数据对象D：24举例：举例：25树的类型定义基本操作：查找类插入类删除类树的类型定义基本操作：26

Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历Root(T)//求树的根结点查找类：Val27InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树InitTree(&T)//初始化置空树插入类：C28

ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ClearTree(&T)//将树清空删除类：De29树的逻辑表示法(1)树型表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。树的逻辑表示法(1)树型表示法。这是树的最基本的表示,使30树的逻辑表示法(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。树的逻辑表示法(2)文氏图表示法。使用集合以及集合的包含关系31树的逻辑表示法(3)凹入表示法。使用线段的伸缩描述树结构。树的逻辑表示法(3)凹入表示法。使用线段的伸缩描述树结构。32树的逻辑表示法(4)括号表示法(广义表表示法)。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。树的逻辑表示法(4)括号表示法(广义表表示法)。将树的根结点33树的分类有向树：(１)有确定的根；(２)树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。树的分类有向树：34对比树型结构和线性结构的结构特点线性结构第一个数据元素(无前驱)最后一个数据元素(无后继)其它数据元素(一个前驱、一个后继)树型结构根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点线性结构树型结构35树的基本术语结点：包含一个数据元素及若干指向其子树的分支。结点的度(degree)：结点拥有的子树个数。树的度：树内各结点的度的最大值。叶子(leaf)：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。除根结点外，分支结点也称为内部结点。树的基本术语结点：包含一个数据元素及若干指向其子树的分支。36树的基本术语(从根到结点的)路径：由从根到该结点所经分支和结点构成。孩子、双亲、兄弟、堂兄弟：结点的子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。同一双亲的孩子之间互称兄弟。其双亲在同一层的结点互为堂兄弟。B、C、D是A的孩子。A是B、C、D的双亲。结点H、I、J互为兄弟结点。树的基本术语(从根到结点的)路径：由从根到该结点所经分支和37树的基本术语路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径。用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。树的基本术语路径与路径长度：对于任意两个结点ki和kj,若树38树的基本术语结点的祖先：从根结点到该结点的路径上的所有结点。结点的子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。1234结点的层次：假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树的高