Unit4_树_二叉树.pptVIP

第4章: 树和二叉树 4.0 简介 4.1 树 4.2 二叉树的定义及性质 4.3 二叉树的遍历 主题 3 4.1 树 4.1.1 树的定义 4.1.2 树的术语 4.1.3 树的广义表形式表示 4 4.1.1 树的定义 树(tree) 树（tree）是包含n（n0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件： 　　（1）有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。 　　（2）除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。 　　（3）K中各结点，对关系N来说可以有m个后继（m=0）。 4.1.2 树 第6章 树与二叉树 6 4.1.3 树的广义表形式表示 可以用广义表的形式表示树结构。例如图示树的广义表表示形式为：A（B（E，F），C（G），D(H，I，J）） 7 4.2 二叉树的定义及性质 4.2.1 二叉树的定义 二叉树是每个结点最多有两个子树的有序树 4.2.2 二叉树的性质 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的（i-1）次方个结点；深 度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2， 则n0 = n2 + 1。 8 4.3 二叉树的遍历 二叉树的遍历 (1)先序遍历 　　访问根；按先序遍历左子树；按先序遍历右子树 　　(2)中序遍历 　　按中序遍历左子树；访问根；按中序遍历右子树 　　(3)后序遍历 　　按后序遍历左子树；按后序遍历右子树；访问根 　　（4）层次遍历 　　即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女 （越往后的层次越低）（两个子女的级别相同）