电子工程学院电子工程学院第第66章树章树电子工程学院电子工程学院上一页下一页回主目录上讲主要内容•串定义存储算法应用•数组定义存储算法应用•线性与非线性数据结构电子工程学院电子工程学院上一页下一页回主目录第第66章树章树6.16.1树树6.26.2二叉树二叉树6.36.3二叉树的遍历二叉树的遍历6.46.4树和森林树和森林6.66.6二叉树的应用二叉树的应用习题习题电子工程学院电子工程学院上一页下一页回主目录6.1树树的定义树的定义（递归定义）：树（（递归定义）：树（TreeTree）是）是nn（（nn≥≥00）个结点的有限集合）个结点的有限集合TT，满足两个条件：，满足两个条件：（1）有且仅有一个特定的称为根（Root）的结点，它没有前趋；（2）其余的结点可分成m个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为根的子树。当n=0时的空集合定义为空树。CAEDBFIGJH电子工程学院电子工程学院上一页下一页回主目录树的表示方法☼直观表示法直观表示法☼文氏图表示法文氏图表示法☼目录表示法目录表示法☼嵌套括号表示法嵌套括号表示法电子工程学院电子工程学院上一页下一页回主目录树的直观表示法圆圈表示结点，结点的名字可写在圆圈内或圆圈旁。连线表示结点之间的关系，学校一系二系十系一室八室一室七室电子工程学院电子工程学院上一页下一页回主目录树的文氏图表示法圆圈圆圈表示表示结点结点圆圈的相互包含圆圈的相互包含表示结点之间的表示结点之间的关系关系。。1室1室1室2室8室一系学校2室9室2室5室十系二系............电子工程学院电子工程学院上一页下一页回主目录树的目录表示法凹入的线条表示结点线条的长短表示结点间的关系，长线条包含短线条。学校一系1室2室8室...二系1室2室9室十系1室2室5室......电子工程学院电子工程学院上一页下一页回主目录树的嵌套括号表示法括号表示结点括号表示结点括号的相互包含表示结点间的关系。括号的相互包含表示结点间的关系。(学校(一系(1室)(2室)…(8室))(二系(1室)(2室)…(9室))…(十系(1室)(2室)…(5室)))电子工程学院电子工程学院上一页下一页回主目录树的基本术语结点结点：指树中的一个元素，包含数据项：指树中的一个元素，包含数据项及若干指向其子树的分支。及若干指向其子树的分支。结点的度结点的度：指结点拥有的子树个数。：指结点拥有的子树个数。树的度树的度：指树中最大结点度数。：指树中最大结点度数。叶子叶子：指度为零的结点，又称为终端结：指度为零的结点，又称为终端结点。点。孩子孩子：一个结点的子树的根称为该结点：一个结点的子树的根称为该结点的孩子。的孩子。双亲双亲：一个结点的直接上层结点称为该：一个结点的直接上层结点称为该结点的双亲。结点的双亲。兄弟兄弟：同一双亲的孩子互称为兄弟。：同一双亲的孩子互称为兄弟。堂兄弟堂兄弟：双亲在同一层上的结点互称为：双亲在同一层上的结点互称为堂兄弟。堂兄弟。CAEDBFIGJH电子工程学院电子工程学院上一页下一页回主目录结点的层次结点的层次：从根结点开始，根结点为第一层，根的：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的孩子为第三层，依次类推。孩子为第二层，根的孩子的孩子为第三层，依次类推。树的深度树的深度：树中结点的最大层次数。：树中结点的最大层次数。电子工程学院电子工程学院上一页下一页回主目录路径路径：若存在一个结点序列：若存在一个结点序列kk11,k,k22,…,k,…,kjj,,可使可使kk11到达到达kkjj,,则称这个结序序列是则称这个结序序列是kk11到达到达kkjj的一条路径。的一条路径。子孙和祖先子孙和祖先：若存在：若存在kk11到到kkjj的一条路的一条路径径kk11,k,k22,…,k,…,kjj，则，则kk11,…,k,…,kj-1j-1为为kkjj的祖先，的祖先，而而kk22,…,k,…,kjj为为kk11的子孙。的子孙。森林森林：：m(m≥0)m(m≥0)棵互不相交的树的集棵互不相交的树的集合构成森林。合构成森林。有序树和无序树有序树和无序树：若将树中每个结点：若将树中每个结点的各个子树都看成...
