程序设计与软件开发基础

1、掌握树的基本概念、二叉树的定义及其存储结构，掌握二叉树的前序、中序和后序遍历教学目标及基本要求教学目标及基本要求第第2929讲讲 程序设计与软件开发基础程序设计与软件开发基础( (三三) )教学重点教学重点二叉树的定义，二叉树的前序、中序和后序遍历第第2929讲讲 程序设计与软件开发基础程序设计与软件开发基础( (三三) )教学难点教学难点二叉树的遍历 树与二叉树教学内容教学内容第第2929讲讲 程序设计与软件开发基础程序设计与软件开发基础( (三三) )1学时 教学时间教学时间第第2929讲讲 程序设计与软件开发基础程序设计与软件开发基础( (三三) )树（Tree）是一种简单的非线性结构，

2、在这种数据结构中，所有数据元素之间的关系具有明显的层次特殊性。图7-12为一棵一般的树。 图7-12 一般的树ABCDEFGHv树用直线连起来的两端节点中，上端节点是前件，下端节点是后件 。 v前件和后件在树结构中，每个节点只有一个前件，称为父节点，没有前件的节点只有一个，称为树的根节点，简称为树的根。v父节点和根结点例图7-12中的A节点为根节点 。在树结构中，一个节点可以有多个后件，它们都称为该节点的子节点。v子节点例图7-12中的B、C节点为节点A的子节点。在树结构中，一个节点所拥有的后件个数（即子节点个数）称为该节点的度。在树中所有节点中的最大的度称为树的度。v节点的度和树的度例图7-

3、12中的A节点的子节点个数为2，则A节点的度为2，C节点的子节点个数为3，则C节点的度为3，在图7-12中C节点的度最大，则树的度为3。在树结构中，一般按如下原则分层：根节点在第一层，同一层上所有节点的子节点都在下一层。树的最大层次称为树的深度。v树的层数和树的深度例图7-12中A节点在第一层，B、C在第二层，D、E、F、G、H在第三层，树的深度为3。在树结构中，以某个节点的一个子节点为根构成的树称为该节点的一棵子树。v节点的子树在树结构中，没有后件的节点称为叶子节点，叶子节点没有子树。 v叶子节点具有如下特点的树称为二叉树： 非空二叉树只有一个根节点； 系统每个节点最多有两棵子树，分别称为该

4、节点的左子树与右子树。（1）二叉树的定义图7-13 二叉树的五种基本形态在二叉树中，每个节点的度最大为2。二叉树具有5种基本形态。如图7-13所示。（a）（b）（c）（d）（e）左子树左子树右子树右子树左子树左子树右子树右子树性质1：在二叉树的第k层上，最多有2k1（k=1）个节点。性质2：深度为m的二叉树最多有2m1个节点。性质3：在任意一棵二叉树中，度为0的节点（即叶子节点）总比度为2的节点多一个。性质4：具有n个节点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。性质5：具有n个节点的完全二叉树的深度为log2n+1。二叉树通常采用链式存储结构，用于存储二

5、叉树中各元素的存储节点由两部分组成：数据域与指针域。用于存储二叉树的存储节点的指针域有两个：一个指向该节点的左子节点的存储地址，叫左指针域；另一个指向该节点的右子节点的存储地址，叫右指针域，节点形式如图7-14所示。二叉树的链式存储结构也称为二叉链表。二叉树的遍历是指不重复地访问二叉树中的所有节点。在遍历二叉树的过程中，一般是先遍历左子树，然后再遍历右子树，在先左后右的原则下，根据访问根节点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首选访问根节点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时也是这个过程，因此，前序遍历二叉树的过程是一个递归的过程。 图7-15的树的前序遍历（DLR）为：A B D G C E F。中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首选访问遍历左子树，然后访问根节点，最后遍历右子树。在遍历左、右子树时也是这个过程，因此，中序遍历二叉树的过程是一个递归的过程。 图7-15的树的中序遍历（LDR）为：D G B A E C F。后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首选遍历左子树，然后遍历右子树，最后访问根节点。在遍历左、右子树时也是这个过程，因此，后序遍历二叉树的过程是一个递归的过程。 图7