[高等教育]6_latest

《[高等教育]6_latest》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其与树的应用第六章树和二叉树16.1树的定义和基本术语6.1树的定义和基本术语树的定义：树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则：有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ABCEFGHIJKLMD5ABCEFGHIJKLMDROOTSU

2、BTREE1SUBTREE2SUBTREE366.1树的定义和基本术语凹入表表示:A------------B----------E--------K------L------F--------C----------G--------D----------H--------M------I--------J--------嵌套集合表示:广义表表示:A(B(E(K,L),F),C(G),D(H(M),I,J))76.1树的定义和基本术语例：英国王室家谱86.1树的定义和基本术语结点(node)：数据元素及其分支结点的度(degree)：结点拥有的子树的个数树的度：树中结点的度的最大值分

3、支(branch)结点：度不为0的结点(非终端结点)叶子(leaf)结点：度为0的结点（终端结点）子(child)结点：结点子树的根双亲(parent)结点：子结点的直接前驱结点兄弟(sibling)结点：同一双亲的子结点互称兄弟结点结点的层次(level)：根为第一层；子结点层次比双亲结点的层次加1树的深度(depth)：树中结点的最大层次有序树：子树从左到右有序（不能互换）无序树：子树无序森林(forest)：m（m≥0）棵互不相交的树的集合96.1树的定义和基本术语ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：

4、B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先106.1树的定义和基本术语ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅有一个元素，R为空集，否则R={H},H具有以下二元关系：(1)在D中存在唯一的称为根的元素root，它在关系H中没有前驱；(2)若D-{root}!=，则存在D-{root}的一个划分D1,D2,…,Dm(m>0)，对任意j!=k，有DjDk=,且对于任意的i,

5、唯一存在数据元素xiDi，有H；(3)对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1,…Hm,对任意的j!=k有HjHk=,对任意的i,Hi是Di上的二元关系，(Di,{Hi})是一颗符合本定义的树，成为根root的子树。基本操作：……}6.1树的定义和基本术语11Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的

6、右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历基本操作:查找类126.1树的定义和基本术语InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为T树中结点p的第i棵子树插入类：13删除类：ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)/

7、/删除结点p的第i棵子树6.1树的定义和基本术语146.1树的定义和基本术语逻辑关系位置线性结构树型结构开始结点一个表首数据元素(无前驱)一个根结点(无前驱)最后结点一个表尾数据元素(无后继)多个叶子结点(无后继)中间结点每个结点只有一个前驱和一个后继每个结点有一个前驱和多个后继6.2二叉树BCDEFL二叉树示例：6.2.1二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成。二叉