java二叉树遍历

数据结构主要是数据以及数据与数据之间的关系。二叉树这种数据结构的数据：就是节点里面存放的值，数据与数据之间的关系就是：一个节点最多有2个子节点。

其它相关概念不懂的自己百度，直接看代码，程序实现了求二叉树的高度，结点数，前序遍历，中序，后序遍历以及非递归方法前序遍历。

二叉树结构图

代码

package smallkong;

import java.util.Stack;

public class BinaryTree {
    private TreeNode  root = null;
    
    public BinaryTree(){
        root = new TreeNode(1, "A");
    }
    
    public class TreeNode{
        private int index;
        private String data;
        private TreeNode leftChild;
        private TreeNode rightChild;
        
    
        public int getIndex() {
            return index;
        }


        public void setIndex(int index) {
            this.index = index;
        }


        public String getData() {
            return data;
        }


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


        public TreeNode(int index,String data){
            this.index = index;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }
    
    /**
     * 构建二叉树
     *         A
     *     B       C
     * D      E        F
     */
    public void createBinaryTree(){
        TreeNode nodeB = new TreeNode(2, "B");
        TreeNode nodeC = new TreeNode(3, "C");
        TreeNode nodeD = new TreeNode(4, "D");
        TreeNode nodeE = new TreeNode(5, "E");
        TreeNode nodeF = new TreeNode(6, "F");
        root.leftChild = nodeB;
        root.rightChild = nodeC;
        nodeB.leftChild = nodeD;
        nodeB.rightChild = nodeE;
        nodeC.rightChild = nodeF;
    }
    
    /**
     * 求二叉树的高度
     * @author smallkong
     *
     */
    public int getHeight(){
        return getHeight(root);
    }
    
    private int getHeight(TreeNode node) {
        if(node == null){
            return 0;
        }else{
            int i = getHeight(node.leftChild);
            int j = getHeight(node.rightChild);
            return (i<j)?j+1:i+1;
        }
    }

    /**
     * 获取二叉树的结点数
     * @author smallkong
     *
     */
    public int getSize(){
        return getSize(root);
    }
    
    
    private int getSize(TreeNode node) {
        if(node == null){
            return 0;
        }else{
            return 1+getSize(node.leftChild)+getSize(node.rightChild);
        }
    }

    /**
     * 前序遍历——递归
     * @author smallkong
     *
     */
    public void preOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            System.out.print(node.getData());
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    
    /**
     * 前序遍历——非递归
     */
    
    public void nonRecOrder(TreeNode node){
        if(node == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(node);
        while(!stack.isEmpty()){
            //出栈和进栈
            TreeNode n = stack.pop();//弹出根结点
            //压入子结点
            System.out.print(n.getData());
            if(n.rightChild!=null){
                stack.push(n.rightChild);
                
            }
            if(n.leftChild!=null){
                stack.push(n.leftChild);
            }
        }
    }
    /**
     * 中序遍历——递归
     * @author smallkong
     *
     */
    public void midOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            midOrder(node.leftChild);
            System.out.print(node.getData());
            midOrder(node.rightChild);
        }
    }
    
    /**
     * 后序遍历——递归
     * @author smallkong
     *
     */
    public void postOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.getData());
        }
    }
    
    
    public static void main(String[] args){
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.createBinaryTree();
        
        int height = binaryTree.getHeight();
        System.out.println("树的高度treeHeihgt:"+height);
        
        int size = binaryTree.getSize();
        System.out.println("结点数treeSize:"+size);
        
        System.out.print("前序preOrder data:");
        binaryTree.preOrder(binaryTree.root);
        
        System.out.print("\n中序midOrder data:");
        binaryTree.midOrder(binaryTree.root);
        
        System.out.print("\n后序postOrder data:");
        binaryTree.postOrder(binaryTree.root);
        
        System.out.print("\n前序非递归preOrder data:");
        binaryTree.nonRecOrder(binaryTree.root);
    }
}

运行结果:

树的高度treeHeihgt:3
结点数treeSize:6
前序preOrder data:ABDECF
中序midOrder data:DBEACF
后序postOrder data:DEBFCA
前序非递归preOrder data:ABDECF

更多编程资料

微信公众号 smallkong