第四章4.1树的基本概念4.2二叉树4.3二叉树的存储结构4.4二叉树的遍历4.5树和森林4.6哈夫曼树第四章树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。4.1树的定义和基本术语树——是n(n>=0)个结点的有限集T，满足：(1)有且仅有一个特定的称为根的结点；(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集Ti又是一棵树，并称其为子树。一、树的定义递归是树的固有特性第四章二、树的逻辑表示▲一般表示法(直观表示法)：FCEGBDAb、嵌套括号法：(根(子树,子树…子树))(A(B(E,F),C,D(G))根ABFCDGEc、凹入法表示：▲另三种表示法a、文氏图法：BACDEFG——第一层第二层第三层第四章三、树的基本术语●度——结点的度：该结点的子树数（即分支数）。树的度：树中结点的度最大值。●结点—由一个数据元素及若干指向其它结点的分支所组成。●叶子（终端结点）——度为零的结点。●孩子（子结点）——结点的子树的根称为该结点的孩子。●双亲（父结点）——一个结点称为该结点所有子树根的双亲。●非终端结点——度不为零的结点。●祖先——结点祖先指根到此结点的一条路径上的所有结点。●子孙——从某结点到叶结点的分支上的所有结点称为该结点的子孙。●兄弟——同一双亲的孩子之间互称兄弟。第四章●结点的层次——从根算起，根为第一层，其孩子在第二层,….，L层上任何结点的孩子都在L+1层上。●堂兄弟——其双亲在同一层的结点。●树的深度——树中结点的最大层次。●森林——是m（≥0）棵树的集合。●有序树——若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。●无序树——若树中各结点的子树是无次序的，可以互换，则成为无序树。第四章求根Root(T):求树T的根结点；求双亲Parent(T,X):求结点X在树T上的双亲；若X是树T的根或X不在T上，则结果为一特殊标志；求孩子Child(T,X,i):求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志；建树Create(X,T1,…,Tk),k>1:建立一棵以X为根，以T1,…,Tk为第1,…,k棵子树的树；剪枝Delete(T,X,i):删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作；遍历TraverseTree(T):遍历树，即访问树中每个结点，且每个结点仅被访问一次。四、树的基本操作第四章二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。4.2二叉树1、定义：二叉树是n(n>=0)个结点的有限集合，它或为空(n=0)，或是由一个根结点及两棵互不相交的左、右子树组成，且每棵子树都是二叉树。4.2.1二叉树的基本概念这是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。ABDCFGHE第四章2、特点：①二叉树可以是空的，称空二叉树；②每个结点最多只能有两个孩子；③子树有左、右之分且次序不能颠倒。３、二叉树与树的比较：结点子树结点顺序树n≥0不定(有限)无二叉树n≥0≤2有(左、右)第四章二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态，图(C)和（d）是不同的两棵二叉树。(a)空二叉树A(b)根和空的左右子树A(c)根和左子树A(d)根和右子树A(e)根和左右子树二叉树的5种形式4.2.1二叉树的定义第四章初始化Initiate(BT):建立一棵空二叉树，BT=∅。求双亲Parent(BT,X):求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X补在BT上，运算结果为NULL。建二叉树Create(BT):建立一棵二叉...
