Java实现二叉树三种遍历算法（递归以及非递归）

首先需要定义一个二叉树的类

//首先定义二叉树类
package mm.test.tree;

public class BinaryTree {

char data;                  //根节点  
BinaryTree leftChild;       //左孩子  
BinaryTree rightChild;      //右孩子  

public BinaryTree() {  

}  

public void visit() {  
    System.out.println(this.data);  
}  

public BinaryTree(char data) {  
    this.data = data;  
    this.leftChild = null;  
    this.rightChild = null;  
}  

public BinaryTree getLeftChild() {  
    return leftChild;  
}  

public void setLeftChild(BinaryTree leftChild) {  
    this.leftChild = leftChild;  
}  

public BinaryTree getRightChild() {  
    return rightChild;  
}  

public void setRightChild(BinaryTree rightChild) {  
    this.rightChild = rightChild;  
}  

public char getData() {  
    return data;  
}  

public void setData(char data) {  
    this.data = data;  
}  

}

先序遍历思想：根左右。首先遍历根节点，然后遍历左子树和右子树。

package mm.test.tree;

import java.util.Stack;

public class VisitBinaryTree {

//先序遍历非递归算法  
private void preOrder(BinaryTree root) {  

    if(root!=null) {  

        Stack stack = new Stack();  

        for (BinaryTree node = root; !stack.empty() || node != null;) {  

            //当遍历至节点位空的时候出栈  
            if(node == null) {  
                node = stack.pop();  
            }  

            node.visit();  

            //遍历右孩子存入栈内  
            if(node.getRightChild()!=null) {  
                stack.push(node.getRightChild());  
            }  

            //遍历左子树节点  
            node = node.getLeftChild();  

        }  

    }  

}  

//先序遍历递归算法  
public void preOrderRecursion(BinaryTree root) {  
    if(root!=null) {  
        root.visit();  
        preOrderRecursion(root.getLeftChild());  
        preOrderRecursion(root.getRightChild());  
    }  
}  

}

测试代码：

public static void main(String args[]) {

     BinaryTree node = new BinaryTree('A');    
     BinaryTree root = node;   
     BinaryTree nodeL1;  
     BinaryTree nodeL;  
     BinaryTree nodeR;  
     node.setLeftChild(new BinaryTree('B'));    
     node.setRightChild(new BinaryTree('C'));    

     nodeL1 = node.getLeftChild();    
    nodeL1.setLeftChild(new BinaryTree('D'));    
    nodeL1.setRightChild(new BinaryTree('E'));   

   nodeL = nodeL1.getLeftChild();    
   nodeL.setLeftChild(new BinaryTree('F'));  

   node = node.getRightChild();    
   node.setLeftChild(new BinaryTree('G'));    
  node.setRightChild(new BinaryTree('H'));    

 nodeR = node.getLeftChild();    
 nodeR.setLeftChild(new BinaryTree('I'));    
nodeR.setRightChild(new BinaryTree('J'));   

 VisitBinaryTree vt= new VisitBinaryTree();    

    //先序遍历递归和非递归测试  
    vt.preOrder(root);  
    vt.preOrderRecursion(root);  

}  

中序遍历算法：

//中序遍历的非递归算法
public void inOrder(BinaryTree root) {

    if(root!=null) {  

        Stack stack = new Stack();  

        for (BinaryTree node = root; !stack.empty() || node != null; ) {  

            //寻找最左的左子树节点,并将遍历的左节点进栈  
            while(node!=null) {  
                stack.push(node);  
                node = node.getLeftChild();  
            }  

            if(!stack.empty()) {  
                node = stack.pop();      //出栈  
                node.visit();            //读取节点值  
                node = node.getRightChild();  
            }  
        }  
    }  
}  

//中序遍历的递归算法  
public void inOrderRecursion (BinaryTree root) {  

        if(root!=null) {  
            inOrderRecursion(root.getLeftChild());  
            root.visit();  
            inOrderRecursion(root.getRightChild());  
        }  

}  

测试代码：

public static void main(String args[]) {

BinaryTree node = new BinaryTree('A');    
    BinaryTree root = node;    
    BinaryTree nodeL1;  
    BinaryTree nodeL;  
    BinaryTree nodeR;  
    node.setLeftChild(new BinaryTree('B'));    
    node.setRightChild(new BinaryTree('C'));    

    nodeL1 = node.getLeftChild();    
    nodeL1.setLeftChild(new BinaryTree('D'));    
    nodeL1.setRightChild(new BinaryTree('E'));   

    nodeL = nodeL1.getLeftChild();    
    nodeL.setLeftChild(new BinaryTree('F'));  

    node = node.getRightChild();    
    node.setLeftChild(new BinaryTree('G'));    
    node.setRightChild(new BinaryTree('H'));    

    nodeR = node.getLeftChild();    
    nodeR.setLeftChild(new BinaryTree('I'));    
    nodeR.setRightChild(new BinaryTree('J'));   

    VisitBinaryTree vt= new VisitBinaryTree();    

    //中序遍历递归和非递归测试  
    vt.inOrder(root);  
    vt.inOrderRecursion(root);  

}  

后序遍历：

//后序遍历非递归算法
private void postOrder(BinaryTree root) {
if(root!=null) {
Stack stack = new Stack();

        for (BinaryTree node = root; !stack.empty() || node != null;) {  
            while(root!=null) {  
                stack.push(root);  
                root = root.getLeftChild();  
            }  

            while(!stack.empty() && root == stack.peek().getRightChild()) {  
                root = stack.pop();    
                root.visit();    
            }  

            if (stack.empty()) {    
                return;    
            } else {    
                root = stack.peek().getRightChild();    
            }    
        }  
    }  
}  

//后序遍历递归算法  
private void postOrderRecursion(BinaryTree root) {  
    if(root!=null) {  
        postOrderRecursion(root.getLeftChild());  
        postOrderRecursion(root.getRightChild());  
        root.visit();  
    }  
}  

测试方法：

public static void main(String args[]) {

BinaryTree node = new BinaryTree('A');    
    BinaryTree root = node;    
    BinaryTree nodeL1;  
    BinaryTree nodeL;  
    BinaryTree nodeR;  
    node.setLeftChild(new BinaryTree('B'));    
    node.setRightChild(new BinaryTree('C'));    

    nodeL1 = node.getLeftChild();    
    nodeL1.setLeftChild(new BinaryTree('D'));    
    nodeL1.setRightChild(new BinaryTree('E'));   

    nodeL = nodeL1.getLeftChild();    
    nodeL.setLeftChild(new BinaryTree('F'));  

    node = node.getRightChild();    
    node.setLeftChild(new BinaryTree('G'));    
    node.setRightChild(new BinaryTree('H'));    

    nodeR = node.getLeftChild();    
    nodeR.setLeftChild(new BinaryTree('I'));    
    nodeR.setRightChild(new BinaryTree('J'));   

    VisitBinaryTree vt= new VisitBinaryTree();    

    //后序遍历递归和非递归测试  
    vt.postOrder(root);  
    vt.postOrderRecursion(root);  

}

• ← Previous Post
• Next Post →