二叉树（java实现）

二叉树基本概念：

二叉树也称为二分树，二元树，对分数等，当集合为空时，该二叉树被称为空二叉树。

结点的度：结点所拥有子树的个数称为该结点的度。

叶结点：度为0的结点称为叶结点，或称为终端结点。

分支结点：度不为0的结点，或者称为非终端结点，一颗的结点除了叶结点外，其他的都是分支结点。

左孩子，右孩子，双亲：书中一个结点的子树称为这个结点的双亲，具有同一个双亲孩子结点胡成为兄弟。

性质：

1. 一颗非空二叉树的第i层 上最多有2^(i-1)个结点（i>=1）

2. 一颗深度为k的二叉树中，最多具有2^k-1个结点，最少有k个结点

3. 对一颗非空二叉树，度为0的结点（叶子结点）总是比度为2的结点多一个

4. 对于完全二叉树，如果按照（开始为1）从上至下，从左至右的顺序对二叉树进行编号，如果i>1,双亲结点为i/2,反推可得孩子结点序号

实现二叉排序树（先，中，后序遍历）

如何遍历

package com.qyc.binaryTree;

public class Node {
    public int date;
    public Node left;
    public Node right;
    public Node(int data){
        this.date = data;
        this.left = null;
        this.right = null;
    }
}

package com.qyc.binaryTree;

public class BinaryTree {
    private Node root;

    public BinaryTree() {
        root = null;
    }

    // 构建二叉树
    public void buildTree(int[] data) {
        for (int i = 0; i < data.length; i++) {
            insert(data[i]);
        }
    }

    // 插入
    public void insert(int data) {
        Node node = new Node(data);
        if (root == null) {
            root = node;
        } else {
            Node current = root;
            Node parend = null;
            while (true) {
                parend = current;
                if (data < current.date) {
                    current = current.left;
                    if (current == null) {
                        parend.left = node;
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parend.right = node;
                        return;
                    }
                }
            }
        }
    }

    // 中序遍历  左 根 右
    public void inOrder(Node localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.left);
            System.out.print(localRoot.date + " ");
            inOrder(localRoot.right);
        }
    }

    public void inOrder() {
        this.inOrder(this.root);
    }

    // 先序遍历   使劲左，然后右
    public void preOrder(Node localRoot) {
        if(localRoot!=null){
            System.out.print(localRoot.date + " ");
            preOrder(localRoot.left);
            preOrder(localRoot.right);
        }
    }

    public void preOrder() {
        this.preOrder(this.root);
    }

    // 后序遍历  左 右 根
    public void postOrder(Node localRoot) {
        if(localRoot!=null){
            postOrder(localRoot.left);
            postOrder(localRoot.right);
            System.out.print(localRoot.date + " ");
        }
    }

    public void postOrder() {
        this.postOrder(this.root);
    }
}

package com.qyc.binaryTree;

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        int data[] = {2,8,7,4,9,3,1,6,7,5};
        binaryTree.buildTree(data);
        binaryTree.inOrder();
        System.out.println();
        binaryTree.preOrder();
        System.out.println();
        binaryTree.postOrder();
    }
}

1 2 3 4 5 6 7 7 8 9 
2 1 8 7 4 3 6 5 7 9 
1 3 5 6 4 7 7 9 8 2 

层序遍历 

   //层序遍历  
    public void layerTranverse() {
        if(this.root==null){
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(this.root);
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            System.out.print(n.date);
            System.out.print(" ");
            if(n.left!=null){
                queue.add(n.left);
            }
            if(n.right!=null){
                queue.add(n.right);
            }
        }

    }

2 1 8 7 9 4 7 3 6 5