美文网首页JavaJava 杂谈Java学习笔记
二叉树的构建与前序、中序、后序的排列

二叉树的构建与前序、中序、后序的排列

作者: firststep | 来源:发表于2019-04-09 10:18 被阅读0次

二叉树的定义

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。(copy百度百科)

前序

先根节点再左节点最后右节点

中序

先左节点再根节点最后右节点

后序

先左节点后右最后根节点
可能这些定义大家都比较熟悉,但是了解起来还是比较麻烦。那么直接上代码:

package BinaryTree;

import java.util.LinkedList;
import java.util.List;

/**
 * author micky.wang
 * 创建二叉树并且使用先序,中序,后序显示出来。
 */
public class ConstructingBinaryTree {
    private int[] array = {1,2,3,4,5,6,7,8,9,10};
    private static List<Node> nodeList = null;

    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>();
        for (int i =0;i<array.length;i++) {
            nodeList.add(new Node(array[i]));
        }
        for (int j = 0; j<array.length / 2 - 1; j++) {
            // 左孩子
            nodeList.get(j).leftChild = nodeList.get(j * 2 + 1);
            // 右孩子
            nodeList.get(j).rightChild = nodeList.get(j * 2 + 2);
        }

        int lastboy = array.length / 2 - 1;
        nodeList.get(lastboy).leftChild = nodeList.get(lastboy * 2 + 1);
        if (array.length % 2 ==1) {
            nodeList.get(lastboy).rightChild = nodeList.get(lastboy * 2 + 2);
        }
    }

    // 先序 先跟再左后右
    public void preording(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.data);
        preording(node.leftChild);
        preording(node.rightChild);
    }

    // 中序 先左再跟最后右
    public void middleOrder(Node node) {
        if (node == null) {
            return;
        }
        middleOrder(node.leftChild);
        System.out.print(node.data);
        middleOrder(node.rightChild);
    }

    // 后序 先左再右后中
    public void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.leftChild);
        postOrder(node.rightChild);
        System.out.print(node.data);
    }

    public static  void  main(String args[]) {
        ConstructingBinaryTree constructingBinaryTree = new ConstructingBinaryTree();
        constructingBinaryTree.createBinTree();
        Node root = nodeList.get(0);
        System.out.println("先序;");
        constructingBinaryTree.preording(root);
        System.out.println("中序;");
        constructingBinaryTree.middleOrder(root);
        System.out.println("后序;");
        constructingBinaryTree.postOrder(root);
    }
}

希望大家可以一起进步。

相关文章

网友评论

    本文标题:二叉树的构建与前序、中序、后序的排列

    本文链接:https://www.haomeiwen.com/subject/bjwviqtx.html