第6章 树与二叉树校长一系二系三系六系教务处科研处总务处601 602教务科603A B C D 张三李四王五例1工厂(根目录) f1f2f3fnd1d2dm 例2f11f12f1kd11d12 例31 树的基本概念2 树的存储结构3 二叉树4 二叉树的存储结构5 二叉树的遍历6 线索二叉树 6.1 树的基本概念 树是由n 0 个结点组成的有穷集合(不妨用D表示)以及结点之间关系组成的集合构成的结构。 当n=0 时，称该树为空树； 在任何一棵非空的树中，有一个特殊的结点t D，称之为该树的根结点；其余结点Dt被分割成m0个不相交的子集D1, D2, ,Dm,其中每一个子集Di又为一棵树，分别称之为t 的子树。递归定义一. 树的定义J I H G F EAC XBA的第1棵子树 A的第3棵子树A的第2棵子树二. 树(逻辑上)的特点1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。2. 除了根结点外,每个结点有且仅有一个直接前驱结点。3. 包括根结点在内，每个结点可以有多个后继结点。J I H G F EAC XB4. 树形表示法 借助自然界中一棵倒置的树的形状来表示数据元素之间层次
