前序遍歷按照“根結(jié)點(diǎn)-左孩子-右孩子”的順序進(jìn)行訪問。
1. 遞歸實(shí)現(xiàn)
/**
* 前序遍歷
* @param node
*/
public static void preOrderTraverse(Node node) {
if (node == null) return;
System.out.print(node.data + "\t");
preOrderTraverse(node.leftNode);
preOrderTraverse(node.rightNode);
}
2. 非遞歸實(shí)現(xiàn)
根據(jù)前序遍歷訪問的順序，優(yōu)先訪問根結(jié)點(diǎn)，然后再分別訪問左孩子和右孩子笆凌。即對(duì)于任一結(jié)點(diǎn)，其可看做是根結(jié)點(diǎn)士葫，因此可以直接訪問乞而，訪問完之后，若其左孩子不為空慢显，按相同規(guī)則訪問它的左子樹爪模；當(dāng)訪問其左子樹時(shí)，再訪問它的右子樹荚藻。因此其處理過程如下：
- 訪問結(jié)點(diǎn)P屋灌，并將結(jié)點(diǎn)P入棧;
- 判斷結(jié)點(diǎn)P的左孩子是否為空，若為空鞋喇，則取棧頂結(jié)點(diǎn)并進(jìn)行出棧操作声滥，并將棧頂結(jié)點(diǎn)的右孩子置為當(dāng)前的結(jié)點(diǎn)P，循環(huán)至1);若不為空侦香，則將P的左孩子置為當(dāng)前的結(jié)點(diǎn)P;
- 直到P為NULL并且棧為空，則遍歷結(jié)束纽疟。
/**
* 前序遍歷 非遞歸
* @param node
*/
public static void nonRecInOrder(Node node) {
Stack<Node> stackNode = new Stack<Node>();
Node d = node;
while (d != null || stackNode.size() > 0) {
while (d != null) {
System.out.print(d.data + "\t");
stackNode.push(d);
d = d.leftNode;
}
while (stackNode.size() > 0) {
d = stackNode.pop();
d = d.rightNode;
}
}
}
