Java实现二叉树基础操作：遍历与构建

package com.ccut;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @describe 二叉树常见操作
 */
public class BinaryTree {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        int[] datas = new int[]{1,2,3,4,5,6,7,8,9};
        List<BinaryNode> nodeList = new ArrayList<BinaryNode>(datas.length);
        binaryTree.createBinaryTree(datas, nodeList);
        System.out.println("前序遍历为：");
        binaryTree.preTraverse(nodeList.get(0));
        System.out.println("\n中序遍历为：");
        binaryTree.inTraverse(nodeList.get(0));
        System.out.println("\n后序遍历为：");
        binaryTree.postTraverse(nodeList.get(0));
        System.out.println("\n层序遍历为：");
        binaryTree.levelTraverse(nodeList.get(0), nodeList.size());

        System.out.println("\n非递归前序遍历：");
        binaryTree.preTraverseByLoop(nodeList.get(0));
        System.out.println("\n非递归中序遍历：");
        binaryTree.inTraverseByLoop(nodeList.get(0));
        System.out.println("\n非递归后序遍历：");

        binaryTree.postTraverseByLoop(nodeList.get(0));
    }

    /**
     * 构造二叉树
     * @param datas 二叉树中各节点的值
     * @param nodeList 二叉树中的各节点
     * 可以讲的点:
     *    1:先构造节点信息(把数据加到节点当中),节点信息保存到数组中
     *    2:为父节点添加相应的子节点
     *      2.1:节点个数和父节点的关系 2倍关系 
     *      2.2:最后一个父节点需要特殊处理,奇数的话,有右孩子,偶数的话没有右孩子
     * 
     */
    public void createBinaryTree(int[] datas, List<BinaryNode> nodeList){
        //为各节点添加数据域
        BinaryNode binaryNode = null;
        for(int i = 0; i < datas.length; i++){
            binaryNode = new BinaryNode(datas[i]);
            nodeList.add(binaryNode);
        }

        /**
         * 说明：
         *  1、为各个父节点添加相应的子节点，按照层序的方式添加子节点
         *  2、将二叉树按照完全二叉树编号，根节点的编号为1，若某节点i有左孩子，则其左孩子的编号为2i
         *     若某节点有右孩子，则其右孩子的编号为(2i + 1)
         *  3、二叉树中若有n个节点，那么父节点的个数为(n/2)
         *  4、二叉树中若节点的个数为奇数，那么最后一个父节点有右子节点
         *     若节点的个数为偶数，那么最后一个父节点只有左子节点，没有右子节点