树、森林和二叉树的转换（哈喜老师）

1.树的存储结构

1.1：树的三种存储结构

树的三种存储结构分别是双亲表示法、孩子表示法、孩子兄弟表示法

1.1.1 ：双亲表示法

// 这里参考了王道书上的代码，哈喜老师课程中的代码不对#defineMAX_SIZE100// 结点结构的定义typedefstructPTNode{ElemType data;// 数据域，用于存储结点中的值intparent;// parent域，用于指向该结点的双亲（parent等于-1时，表示该结点没有父结点，也就是说该结点是根结点）}PTNode;// 树的类型的定义typedefstruct{PTNode nodes[MAX_SIZE];// 存储所有结点的数组intn;// 树中实际的结点个数}PTree;

1.1.2 ：孩子表示法

1.1.3 ：孩子兄弟表示法

typedefstructCSNode{ElemType data;//数据域structCSNode*firstchild;//指向该结点最左边的孩子structCSNode*nextsibling;// 指向该结点右边相邻的兄弟}CSNode,*CSTree;

2.树、二叉树、森林的转换（很重要）

2.1：树转换为二叉树

2.2：二叉树转换为树

2.3：森林转换为二叉树

2.4：二叉树转换为森林

2.5：习题

习题一（有难度）

习题二：（偏简单）

习题三：（有难度）

习题四：（难，思路很不好想，暂时还不理解）

真题(难，还没完全理解)

3.树和森林的遍历

3.1：树的遍历（非重点）

3.2：森林的遍历（非重点）

3.3：树、二叉树、森林的遍历关系（重点）

3.3.1：真题