Home > Java > javaTutorial > How to build a binary tree using java

How to build a binary tree using java

PHPz
Release: 2017-04-03 10:15:04
Original
2266 people have browsed it

Directory:

1. Put a Assign the value of array to a binary tree

2. Specific code

Note:

1. The subscript of the parent node array ranges from 0 to n/2 -1, but it should be less than n/2-1 when traversing, because the last The parent node may not have a right child. When n/2-1 is an odd number, it has a right child, and when it is an even number, it only has a left child.

##2. Node. The subscript of the left child is 2n+1, and the subscript of the right child is 2n+2

##1. Tree construction method




2. Specific code

package tree;  
  
import java.util.LinkedList;  
import java.util.List;  
  
/** 
 * 功能:把一个数组的值存入二叉树中,然后进行3种方式的遍历 
 *  
 * 参考资料0:数据结构(C语言版)严蔚敏 
 *  
 * 参考资料1:http://zhidao.baidu.com/question/81938912.html 
 *  
 * 参考资料2:http://cslibrary.stanford.edu/110/BinaryTrees.html#java 
 *  
 * @author ocaicai@yeah.net @date: 2011-5-17 
 *  
 */  
public class BinTreeTraverse2 {  
  
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
    private static List<Node> nodeList = null;  
  
    /** 
     * 内部类:节点 
     *  
     * @author ocaicai@yeah.net @date: 2011-5-17 
     *  
     */  
    private static class Node {  
        Node leftChild;  
        Node rightChild;  
        int data;  
  
        Node(int newData) {  
            leftChild = null;  
            rightChild = null;  
            data = newData;  
        }  
    }  
  
    public void createBinTree() {  
        nodeList = new LinkedList<Node>();  
        // 将一个数组的值依次转换为Node节点  
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {  
            nodeList.add(new Node(array[nodeIndex]));  
        }  
        // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树  
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {  
            // 左孩子  
            nodeList.get(parentIndex).leftChild = nodeList  
                    .get(parentIndex * 2 + 1);  
            // 右孩子  
            nodeList.get(parentIndex).rightChild = nodeList  
                    .get(parentIndex * 2 + 2);  
        }  
        // 最后一个父节点:因为最后一个父节点可能没有右孩子,所以单独拿出来处理  
        int lastParentIndex = array.length / 2 - 1;  
        // 左孩子  
        nodeList.get(lastParentIndex).leftChild = nodeList  
                .get(lastParentIndex * 2 + 1);  
        // 右孩子,如果数组的长度为奇数才建立右孩子  
        if (array.length % 2 == 1) {  
            nodeList.get(lastParentIndex).rightChild = nodeList  
                    .get(lastParentIndex * 2 + 2);  
        }  
    }  
  
    /** 
     * 先序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void preOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        System.out.print(node.data + " ");  
        preOrderTraverse(node.leftChild);  
        preOrderTraverse(node.rightChild);  
    }  
  
    /** 
     * 中序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void inOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        inOrderTraverse(node.leftChild);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.rightChild);  
    }  
  
    /** 
     * 后序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void postOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        postOrderTraverse(node.leftChild);  
        postOrderTraverse(node.rightChild);  
        System.out.print(node.data + " ");  
    }  
  
    public static void main(String[] args) {  
        BinTreeTraverse2 binTree = new BinTreeTraverse2();  
        binTree.createBinTree();  
        // nodeList中第0个索引处的值即为根节点  
        Node root = nodeList.get(0);  
  
        System.out.println("先序遍历:");  
        preOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("中序遍历:");  
        inOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("后序遍历:");  
        postOrderTraverse(root);  
    }  
  
}
Copy after login

Output result:

先序遍历:  
1 2 4 8 9 5 3 6 7   
中序遍历:  
8 4 9 2 5 1 6 3 7   
后序遍历:  
8 9 4 5 2 6 7 3 1
Copy after login

The above is the detailed content of How to build a binary tree using java. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template