• 欢迎访问梯云博客,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站点击访问
  • 站点的评论回复邮件可能会被邮箱放入垃圾邮件中,请注意哦~
  • 梯云博客近期增设了“电影资源”板块,在视频区域下边哦~
  • 梯云音乐上线,提供一站式的音乐下载平台,点击前往梯云音乐
  • 如果百度网盘下载速度过慢,可使用该工具~Proxyee-down 百度网盘不限速
  • 本站所有发布的信息以及产品,仅供学习研究使用;除有软件所有者授权外不得非法用于商业或其他用途。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏梯云吧!

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

一杯JAVA浓 做棵大树 2年前 (2017-12-10) 356次浏览 0个评论

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

//首先定义<a href="https://www.teenshare.club/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);  
  
    }  

 


TeenShare 梯云分享 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Java 实现二叉树三种遍历算法(递归以及非递归)
喜欢 (0)
[欢迎投币]
分享 (0)
关于作者:
一个整天无所事事的,有时候忽然热血的孩子
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址