5树 51树的概念 511树和森林 512森林与二叉树的等价转换 513树的抽象数据类型 5.1.4树的周游 52树的链式存储 52.1子结点表表示法 522左子结点右兄弟结点表示法 523动态结点表示法 524动态“左子结点/右兄弟结点”二叉链表表示法 525父指针表示法及等价类的并查算法 53树的顺序存储 53.1带右链的先根次序表示法 532带双标记位的先根次序表示法 533带左链的层次次序表示法 534带度数的后根次序表示法 54K叉树 图书目录,杜威表示法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 11
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 5 树 5.1 树的概念 5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游 5.2 树的链式存储 5.2.1 子结点表表示法 5.2.2 左子结点/右兄弟结点表示法 5.2.3 动态结点表示法 5.2.4 动态“左子结点/右兄弟结点”二叉链表表示法 5.2.5 父指针表示法及等价类的并查算法 5.3 树的顺序存储 5.3.1 带右链的先根次序表示法 5.3.2 带双标记位的先根次序表示法 5.3.3 带左链的层次次序表示法 5.3.4 带度数的后根次序表示法 5.4 K叉树 图书目录，杜威表示法 凹入表表示法(例子)
嵌套括号表示法 (A(B(D)(E((J)(F)(C(G)(H) (d)嵌套括号表示法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 嵌套括号表示法 (A(B(D)(E(I)(J))(F))(C(G)(H))) （d）嵌套括号表示法
氏图到嵌套括号表示的转化 从最外层依次将表示集合 的方框转化成括号对 B C olooollool (A(BDOE(O)F(C(G() 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 13
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 文氏图到嵌套括号表示的转化 A B C D E I J G H F (A(B(D)(E(I)(J)) (C (F)) (G)(H))) 从最外层依次将表示集合 的方框转化成括号对
树的定义 ■树是包括n个结点的有限集合T(n1),使得: 有一个特别标出的称作根的结点 除根以外的其它结点被分成m个m≥0)不相交的集合T1, Tm,而且这些集合的每一个又都是树。树T1, T2,…,Tm称作这个根的子树 ■这个定义是递归的,我们用子树来定义树:只包 含一个结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 ge 14
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 树的定义 树是包括n个结点的有限集合T（n≥1），使得： 有一个特别标出的称作根的结点 除根以外的其它结点被分成m个(m≥0)不相交的集合T1， T2，…，Tm，而且这些集合的每一个又都是树。 树T1， T2，…，Tm称作这个根的子树 这个定义是递归的，我们用子树来定义树：只包 含一个结点的树必然仅由根组成，包含n>1个结 点的树借助于少于n个结点的树来定义
树结构中的概念(1) 若<k,k′>∈N,则称k是k′的父结点(或称“父 母”),而k′则是k的子结点(或“儿子”、“子女”) 若有序对<k,k′>及<k,k">∈N,则称k′和k 互为兄弟 若有一条由k到达k的路径,则称k是k的祖先,k是k 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 条边 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 15
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 树结构中的概念(1) 若<k，k′>∈N，则称k是k′的父结点（或称“父 母”），而k′则是k的 子结点(或“儿子”、“子女”) 若有序对<k，k′>及<k，k″>∈N，则称k′和k″ 互为兄弟 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k 的子孙 树形结构中，两个结点的有序对，称作连接这两结点的 一条边