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

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

//首先定义<a href="https://beatree.cn/tag/%e4%ba%8c%e5%8f%89%e6%a0%91" title="查看更多关于二叉树的文章" target="_blank">二叉树</a>类
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);  
  
    }  

喜欢 (0) 赏

[欢迎投币]

分享 (0)