树、森林与二叉树的转换
树和二叉树转换
左孩子右兄弟原则。
每个结点左指针指向它的第一个孩子结点，右指针指向它在树中相邻的兄弟结点。
森林与二叉树的转换
规则：将每一棵树转换为二叉树，将每棵二叉树的根依次只作为一上课二叉树的右子树。
树的遍历：按照某种方式访问树中的每个结点，且仅访问一次
先根遍历：若树非空，则先访问根结点，在按从左到右的顺序遍历根结点的没棵子数。
先根遍历顺序
*树的先根遍历序列与这棵树对应二叉树的先序遍历序列相同。
后根遍历：若树非空，则先按从左到右的顺序遍历根结点的没棵子树，再访问根结点。
后根遍历顺序
*树的后根遍历序列与这棵树对应二叉树的中序遍历序列相同。
层次遍历：若树非空，按照由上至下，由左至右的访问树中的所有结点。
森林的遍历
先序遍历
若森林非空，则，
·访问森林的第一棵树的根结点
·先序遍历第一课树的子树森林
·先序遍历除去第一课数之后的剩余的树构成的子树森林
先序遍历顺序
*森林的先序遍历序列与森林对应二叉树的先序遍历序列相同。
中序遍历
若森林非空，则，
·中序遍历第一棵树的根结点的子树森林
·访问第一棵树的根结点
·中序遍历除去第一棵树之后剩余的树构成的子树森林
中序遍历顺序
*森林的中序遍历序列与森林对应二叉树的中序遍历序列相同
遍历序列的对应关系
遍历序列的对应关系
