611树和森林 树的逻辑结构可以这样描述:树是包含n个结点的有 穷集合K(n>0),且在K上定义了一个满足以下条件 的二元关系R={r}: 口有且仅有一个结点k∈K,它对于关系r来说没 有前驱。结点k称作树的根。 口除结点k外,K中的每个结点对于关系r来说都有 且仅有一个前驱。 口除结点k外的任何结点k∈K,都存在一个结点 序列k,k1,…,k,使得k就是树根,且k=k ,其中有序对<k-1,k>∈R(1≤i≤s)。这样 的结点序列称为从根k到结点k的一条路径。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 ◼ 树的逻辑结构可以这样描述：树是包含n个结点的有 穷集合K(n > 0)，且在K上定义了一个满足以下条件 的二元关系R = {r}： ❑ 有且仅有一个结点k0∈ K，它对于关系r来说没 有前驱。结点k0称作树的根。 ❑ 除结点k0外，K中的每个结点对于关系r来说都有 且仅有一个前驱。 ❑ 除结点k0外的任何结点k ∈ K，都存在一个结点 序列k0，k1，…，ks，使得k0就是树根，且ks = k ，其中有序对<ki-1，ki> ∈ R（1 ≤ i ≤ s）。这样 的结点序列称为从根k0到结点k的一条路径
树形结构的各种表示法 树的逻辑结构是 结点集合K={A,B,C,D,E,F,G,H,I,乃 K上的关系N={<A,B>,<A,C>,<B,D>, <B,E>,<B,F>,<C,G>, <C,B>,<E,I>,<E,J “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树形结构的各种表示法 树的逻辑结构是： 结点集合K={A，B，C，D，E，F，G，H，I，J} K上的关系N={<A，B>，<A，C>，<B，D>， <B，E>，<B，F>，<C，G>， <C，H>，<E，I>，<E，J>}
树结构中的概念 在一棵树中,若存在结点k指向结点k的连线,则 称k是k的父结点,而k则是k的子结点,有向连 线<k,k>称作边 同一个父结点的子结点之间互称兄弟。树中没有 父结点的结点称为根。没有子结点的结点称为树 叶 ■结点的子树数目称为结点的度,树的度是树中各 结点度的最大值,二叉树的度是2。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 在一棵树中，若存在结点k指向结点k’的连线，则 称k是k’的父结点，而k’则是k的子结点，有向连 线<k, k’>称作边。 ◼ 同一个父结点的子结点之间互称兄弟。树中没有 父结点的结点称为根。没有子结点的结点称为树 叶。 ◼ 结点的子树数目称为结点的度，树的度是树中各 结点度的最大值，二叉树的度是2
树结构中的概念 若树中存在结点序列k,k1,…,k,使得<k0, k1>,<k1,k2>,…,<k、1,k>都是树中的边 则称从结点k到结点k存在一条路径 若有一条由k到达ks的路径,则称k是ks的祖先, ks是k的子孙。 结点的层数同样由树根开始定义的,根结点为第 0层,非根结点的层数是其父结点的层数加1。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 若树中存在结点序列k0，k1，…，ks，使得<k0， k1>，< k1，k2>，…，< ks-1，ks>都是树中的边， 则称从结点k0到结点ks存在一条路径。 ◼ 若有一条由 k到达ks的路径，则称k是ks的祖先， ks是k的子孙。 ◼ 结点的层数同样由树根开始定义的，根结点为第 0层，非根结点的层数是其父结点的层数加1
树结构中的概念 有序树:计算机的存储是有序的,为方便计算机处理 ,往往把子结点按从左到右的次序顺序编号,即把树 作为有序树( ordered tree看待。 度为2的有序树并不是二叉树,因为在第一子结点被删 除后,第二子结点自然顶替成为第一子结点。因此, 度为2并且严格区分左右两个子结点的有序树才是二叉 树 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 有序树：计算机的存储是有序的，为方便计算机处理 ，往往把子结点按从左到右的次序顺序编号，即把树 作为有序树(ordered tree)看待。 ◼ 度为2的有序树并不是二叉树，因为在第一子结点被删 除后，第二子结点自然顶替成为第一子结点。因此， 度为2并且严格区分左右两个子结点的有序树才是二叉 树