关于 二叉树

二叉树和正常的树不同，它向下生长，并且拥有各种令人头疼的遍历顺序...

参照附录BT了解关于二叉树的词汇及各种遍历顺序。

• 该模块包含一个屏幕和一个深度为三的满二叉树, 其中包含七个可以摁下的结点。 每个结点的颜色可能不同, 并且上面都印有一个黑色或银色字符。 字母'O'不会在此模块上出现，但是数字0可能会出现。
• 该模块有三个阶段。 在每一个阶段，参照一个引用结点来决定需要摁下哪个结点。 在第一个阶段，使用树的根节点作为引用结点。 在其后的阶段，使用你在上个阶段中摁下的正确结点作为引用结点。
• 为了确认摁下哪个结点，先将引用结点上的字符转换成一个数字。 如果字符就是一个数字，就用那个数字，否则使用字符在字母表中的位置+2。
• 如果你得到的数字大于7，那么重复地减7直到数字在1~7之间。 如果数字是0，把它变为7。 设你最终得到的数字为N。
• 使用下一页的表格，根据引用结点的颜色和当前阶段来决定所有结点的遍历顺序。
• 摁下遍历顺序中的第N个结点，除非引用结点的字符是银色的，在那种情况下摁遍历顺序中从后往前数的第N个结点。
• 屏幕上仅显示你之前摁过的正确结点。你不需要它就可以解除整个模块。
• 摁下错误的结点会导致一次错误，但模块会保持在当前阶段。 模块也会亮起错误指示灯，在此期间所有操作会被忽略。

结点遍历顺序表

阶段：		第一阶段	第二阶段	第三阶段
引用结点颜色：	红色	先序	右到左 中序	右到左 层次顺序
	绿色	中序	右到左 后序	中序
	蓝色	后序	右到左 先序	右到左 中序
	橙色	层次顺序	层次顺序	先序
	青色	右到左 先序	先序	层次顺序
	洋红色	右到左 中序	中序	右到左 后序
	黄色	右到左 后序	右到左 层次顺序	后序
	灰色	右到左 层次顺序	后序	右到左 先序

附录 BT：二叉树词汇及遍历顺序

词汇：

• 一个满二叉树是一个拥有许多结点的结构，其中除了在底层的结点以外，所有结点都与它下面的两个子结点连接。
• 一个树的根节点是位于树顶层的那个结点。
• 一个结点的左子树是包含那个结点的左子结点以及那个子结点的所有子结点的满二叉树。 一个结点的右子树是包含那个结点的右子结点以及那个子结点的所有子结点的满二叉树。
• 树的一个遍历顺序将按一种顺序来访问每个结点一次。

遍历顺序：

• 先序：从树的根节点开始，先访问根节点，然后使用先序访问其左子树中的所有结点，最后使用先序访问其右子树中的所有结点。
• 中序：从树的根节点开始，先使用中序访问其左子树中的所有结点，然后访问根结点，最后使用中序访问其右子树中的所有结点。
• 后序：从树的根节点开始，先使用后序访问其左子树中的所有结点，然后使用后序访问其右子树中的所有结点，最后访问根节点。
• 层次顺序：与阅读顺序相同。 从最上面一层开始，在每一层从左往右访问所有结点。从上往下访问所有层。
• 对于上面给出的遍历顺序的右到左版本，使用上面的描述，但是请将描述中的所有“右”与“左”互换。