使用一维数组创建出完全二叉树

标签：后序遍历   src   vpd   vat   ado   测试结果   pre   奇数   pos   

下面直接上代码（我是直接用的for循环初始化开始做的，也可以使用递归解决）
这是树节点类

package com.edu.dataStructure.treeDemo;

import java.util.*;

/**
 * 

 * 自己创建的树节点
 * 
 *
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode() {
    }

    /**
     * 

     * 前序遍历:根节点+左节点+右节点
     * 
     */
    public void preShow() {
        if (this != null) {
            System.out.print(this.val + "\t");
            if (this.left != null) {
                this.left.preShow();
            }
            if (this.right != null) {
                this.right.preShow();
            }
        }

    }

    /**
     * 

     * 中序遍历:左节点+根节点+右节点
     * 
     */
    public void midShow() {
        if (this != null) {
            if (this.left != null) {
                this.left.preShow();
            }
            System.out.print(this.val + "\t");
            if (this.right != null) {
                this.right.preShow();
            }
        }
    }

    /**
     * 

     * 后序遍历:左节点+右节点+根节点
     * 
     */
    public void postShow() {
        if (this != null) {
            if (this.left != null) {
                this.left.preShow();
            }
            if (this.right != null) {
                this.right.preShow();
            }
            System.out.print(this.val + "\t");
        }
    }

    /**
     * 

     * 将数组转换为完全二叉树

     * 完全二叉树的特性:

     * 1.第 n 个元素的左子节点为	2 * n + 1   

     * 2.第 n 个元素的右子节点为	2 * n + 2   

     * 3.第 n 个元素的父节点为	(n-1) / 2   

     * 
     *
     * @return
     */
    public static TreeNode arraytoCompletebinarytree(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new TreeNode();
        }
        //创建一堆树
        List treeNodeList = new ArrayList(arr.length);
        for (int i = 0; i 

这是测试类

package com.edu.dataStructure.treeDemo;

/**
 * 

 * 该类{@link TreeNodeTest} 是{@link TreeNode} 的测试类
 * 
 *
 */
public class TreeNodeTest {
    public static void main(String[] args) {
//        TreeNode instanceToTest = getInstanceToTest();
//        instanceToTest.preShow();
        TreeNode.arraytoCompletebinarytree(new int[]{1,2,3,4,5,6,7,8,9}).preShow();
    }

    /**
     * 
得到一个测试用例
     * @return
     */
    private static TreeNode getInstanceToTest() {
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode6=new TreeNode(6);
        TreeNode treeNode7=new TreeNode(7);
        TreeNode treeNode8=new TreeNode(8);
        TreeNode treeNode9=new TreeNode(9);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;
        treeNode4.left=treeNode8;
        treeNode4.right=treeNode9;
        return treeNode1;
    }
}

测试结果如图：

使用一维数组创建出完全二叉树

标签：后序遍历   src   vpd   vat   ado   测试结果   pre   奇数   pos   

原文地址：https://www.cnblogs.com/five-five/p/14347941.html