软件技术基础1.ppt

《软件技术基础1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章树一.树结构树结构的基本概念和术语二.二叉树结构基本概念二叉树的存储二叉树的遍历二叉树的应用一.树结构结点、根、分支结点、叶子结点、兄弟结点的度、树的度、树的深度/高度/层次EBJKAFCDGHIMNL第1层第2层第3层第4层a*(b＋c/d)＋e*h－g*f(s，t，x＋y)树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树是由n（n≥1）个结点组成的有限集合。（1）有一个特定的称为根（root）的结点。它可有直接后继，没有直接前驱；（2）除根结点以外的其它结点可以划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1,每个集

2、合Ti又是一棵树，称为根的子树(subTree)，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。一.树结构二叉树是n（n≥0）个结点组成的有限集，它或者是空集（n=0），或是由一个根结点及两棵不相交的左子树和右子树组成。特点：(1)二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点。(2)二叉树是有序树，其子树的顺序不能颠倒。一、二叉树的定义二.二叉树结构二.二叉树结构(a)空二叉树(b)只有一个结点(c)只有左子树(d)只有右子树(e)有左右子树二叉树有五种不同的形态：ABCDEFGHIJKLM12345

3、6二.二叉树结构ABC二叉树与一般树的概念区别：树至少应有一个结点，而二叉树可以是空的；二叉树的所有子树要区分为左子树和右子树，其结点的度不超过2。二.二叉树结构思考题任意三个结点可构造多少种树?多少种二叉树?二.二叉树结构性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。二、二叉树的性质i=1时，只有一个根结点，假设对所有j(1j=

4、1)。证明：由性质1，可得深度为k的二叉树最大结点数是（证明用求等比级数前k项和的公式）二.二叉树结构性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。二.二叉树结构ABCDEF证明：设n1为二叉树T中度为1的结点数；因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2又二叉树中，除根结点外，其余结点都只有一个分支进入，设B为分支总数，则n=B+1又分支由度为1和度为2的结点发出，故B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1二.二叉树结构三、几种

5、特殊形式的二叉树1231145891213671014151234567二.二叉树结构（1）满二叉树：特点：每一层上的结点数都达到最大结点个数。（2）完全二叉树定义：深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~123114589126710123456二.二叉树结构（2）完全二叉树叶子结点只可能在层次最大的两层上出现;对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。123114589126710思考题:第五层有5个叶子结点的完全二叉树，最多有多少个结点

6、?二.二叉树结构（3）二叉排序树或者为一棵空树、或者：左子树所有结点的关键字均小于根；右子树所有结点的关键字均大于根。子树本身也是一棵二叉排序树。8412635291016二.二叉树结构1、顺序存储：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。ABCDEFG1234567ABCDEFG二.二叉树结构四、二叉树的存储结构对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对应，不存在的结点用用“0”填充。四、二叉树的存储结构ABCDEFGABCDE0000FG1234567891011特点：结点间关系蕴含在其存储位置中浪费

7、空间，适于存储满二叉树和完全二叉树二.二叉树结构BCDAEFGABDCEFrootG四、二叉树的存储结构2、二叉链表二.二叉树结构typedefstructnode{datatypedata;structnode*lchild,*rchild;}TREENODE;??四、二叉树的存储结构二.二叉树结构ABCDEGHFK1、二叉树中分支数B和结点数n的关系，2、二叉链树中空指针数用结点数n表示为。3、对于满二叉树或完全二叉树：①若i<=n/2，则i的左孩子编号为,否则i没有左孩子；②若i<=(n-1)/2，则i的右孩子编号，否则i没有右孩

8、子；③若i!=1，则结点i的双亲编号是。问题讨论二.二叉树结构2i+12ii/2n=B+1n+