二叉樹深度優先周遊

在二叉樹的深度優先周遊中分為前序周遊、中序周遊和後序周遊，其中根據前序周遊和中序周遊或後序周遊和中序周遊可以推算出完整的二叉樹。

三種周遊方式為：

前序周遊：根節點->左子樹->右子樹

中序周遊：左子樹->根節點->右子樹

後序周遊：左子樹->右子樹->根節點

由上述三種周遊方式可知中序周遊最為重要，因為中序周遊可以确定哪些節點在根節點的左側，哪些節點在根節點的右側。

首先根據前序或後序周遊找到根節點，然後根據中序周遊将其他節點配置設定到根節點兩側，以此方式使用遞歸的方式可以推算出完整的二叉樹。

例題：

已知某二叉樹的先序周遊序列為ABCDEF、中序周遊序列為BADCFE，則可以确定（）；

此處不管要考什麼問題，肯定都要推出正确的二叉樹才行，根據上述解析，在先序序列中可知A為根節點，根據中序序列可知B在A的左子樹上，DCFE在A的右子樹上。将DCFE拿出與ABCDEF對比可知C為DCFE中的根節點，即C為A的右子節點，同時可知D在C的左子樹上，FE在C的右子樹上。重複上述推理，最後得出改二叉樹為：

該題選項為

A.是單支樹（即非葉子節點都隻有一個孩子）

B.高度為4（即節點分布在4層上）

C.根節點的左子樹為空

D.根節點的右子樹為空

綜上所述選B