1.引言
前面寫了下库糠。二叉樹的遞歸遍歷發(fā)，但是自己寫非遞歸遍歷的時(shí)候涮毫，真是艱難瞬欧。寫不出來，自己還是太水了罢防，太水了艘虎。無奈把人家的代碼看了下。跑了下咒吐，自己在紙上走了一下野建。還是在此記錄下，供以后翻閱恬叹。
2.正題
先說下：非遞歸遍歷二叉樹候生。需要一個(gè)棧來保存根節(jié)點(diǎn)。然后涉及到倆個(gè)while循環(huán)绽昼。第一個(gè)while(!statck.empty()||rootNode!=null)唯鸭。第二個(gè)while主要是將左子樹的節(jié)點(diǎn)添加進(jìn)棧中，所以循環(huán)的條件while(rootNode!=null)硅确。目溉。接下來就是正題明肮。
聲明節(jié)點(diǎn)：
public static class Node{
private int number;
private Node leftNode;
private Node rightNode;
public Node getLeftNode() {
return leftNode;
}
public Node(int number) {
this.number = number;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
建立二叉樹：
public static void main(String args[]){
BinTree binaryTree=new BinTree();
List<Node> treeNodes=new ArrayList<>();
treeNodes.add(new Node(6));
treeNodes.add(new Node(3));
treeNodes.add(new Node(7));
treeNodes.add(new Node(1));
treeNodes.add(new Node(4));
treeNodes.add(new Node(9));
treeNodes.forEach(treeNode -> {binaryTree.buildTree(treeNode,binaryTree.rootNode);});
// binaryTree.postorderTraversal(binaryTree.rootNode);
}
前序遍歷：
public void preorderTraversal(Node rootNode){
if (rootNode==null)
return;
Stack<Node>stack=new Stack<>();//棧，先進(jìn)先出
while(rootNode!=null ||!stack.empty()){
while (rootNode!=null){
System.out.println(rootNode.getNumber());
stack.add(rootNode);
rootNode=rootNode.getLeftNode();
}
if (!stack.empty()){
Node node=stack.pop();
rootNode=node.getRightNode();
}
}
}
中序遍歷：
和前序的區(qū)別是：System的位置不同缭付。
public void middleTraversal(Node rootNode){
if (rootNode==null)
return;
Stack<Node>stack=new Stack<>();
while(rootNode!=null||!stack.empty()){
while (rootNode!=null){
stack.add(rootNode);
rootNode=rootNode.getLeftNode();
}
if (!stack.empty()){
Node node=stack.pop();
System.out.print(node.getNumber());
rootNode=node.getRightNode();
}
}
}
后序遍歷：
后序遍歷又復(fù)雜了一點(diǎn)柿估。根節(jié)點(diǎn)最后遍歷。前面的倆中遍歷蛉腌。在處理右節(jié)點(diǎn)的時(shí)候官份，是直接調(diào)用pop()。彈出那個(gè)節(jié)點(diǎn)烙丛。但是 后序遍歷不能這樣搞。后序遍歷不清楚是：左-->根（右節(jié)點(diǎn)缺少）羔味。左-->右-->根河咽。右-->根(左節(jié)點(diǎn)缺失)。按照大神的博客說的是：需要一個(gè)棧來保存訪問的左節(jié)點(diǎn),右節(jié)點(diǎn)赋元。左節(jié)點(diǎn) 0進(jìn)棧忘蟹，右節(jié)點(diǎn)1進(jìn)棧。
代碼如下：
public void postorderTraversal(Node rootNode){
Stack<Node>stack=new Stack<>();
Stack<Integer>stack1=new Stack<>();
while (!stack.empty()||rootNode!=null){
while (rootNode!=null){
stack.push(rootNode);
stack1.push(new Integer(0));//棧一直加0搁凸。代表加入的是左節(jié)點(diǎn)
rootNode=rootNode.getLeftNode();
}
//這個(gè)wihle 不明白媚值。不過在紙上一步一步的走循環(huán)一次的確不行
while (!stack.empty() && stack1.peek()==1) {
stack1.pop();
System.out.print(stack.pop().getNumber());
}
if (!stack.empty()){
stack1.pop();
stack1.push(new Integer(1));//棧頂?shù)脑靥鎿Q成1，表示讀取的是當(dāng)前根節(jié)點(diǎn)的右節(jié)點(diǎn)
Node node=stack.peek();
rootNode=node.getRightNode();
}
}
}
二叉樹的遍歷的確小難护糖，不看任何資料褥芒，能寫出來的確是nb。目前就淺嘗而至算了嫡良，等一會真正遇到了 在好好品味下锰扶。二叉樹算法
