数据结构与算法之树

1. 什么是树？

树是数据结构和算法分析与设计中一种非常重要的结构，由N个节点组成的具有层次结构的模型，主要有以下几个特点：

• 1. 有一个根节点，一般称为root节点
• 2. 每一个节点都被称为node
• 3. 除了root节点外，其余的节点都会被分成n个互不相交的集合。

具体的结构如下所示：

树.png

树形结构的基本术语：

• 节点：树形结构里面的元素
• 子树：当节点大于1时，其余节点分为的互不相交的集合称为字数
• 度：一个节点拥有子树的数量，称为节点的度，出度和入度（区分叶子节点和根节点）
• 叶子：出度为0 的节点
• 孩子：节点的子树的根称为孩子节点
• 双亲：和孩子节点对应
• 兄弟：同一个双亲节点
• 深度：节点的最大层次称为树的深度（计算时间复杂度用）
• 森林：由N个互不相交的树构成森林

2. 什么是二叉树？

二叉树是树形结构中比较特殊的一种，它的主要特点是每个节点最多有两个子树的树结构，也就是经常听到的左子树和右子树。他有非常多的应用，其典型的就是二叉查找。

• 二叉树：的第N层上最多有2^(N-1)个节点。二叉树最多有2^N-1个节点个数。
• 满二叉树：假设树的深度为M，其有2^M-1个节点的二叉树
  具有N个节点的完全二叉树其深度为log2^n + 1。注意：这个特性决定了索引树的时间复杂度。

三种遍历方式：

• 前序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根

递归实现二叉树前序、中序、后序遍历源代码：java

class BNode{
    private char data;
    private BNode leftNode;
    private BNode rightNode;

    public BNode(char date, BNode leftNode, BNode rightNode){
        this.data = date;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public BNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(BNode leftNode) {
        this.leftNode = leftNode;
    }

    public BNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(BNode rightNode) {
        this.rightNode = rightNode;
    }
}

public class BinaryTree {
    public static void main(String[] args){

        BNode D = new BNode('D', null, null);
        BNode H = new BNode('H', null, null);
        BNode K = new BNode('K', null, null);
        BNode C = new BNode('C', D, null);
        BNode B = new BNode('B', null, C);
        BNode G = new BNode('G', H, K);
        BNode F = new BNode('F', G, null);
        BNode E = new BNode('E', null, F);
        BNode A = new BNode('A', B, E);

        BinaryTree binaryTree = new BinaryTree();
        System.out.println("前序遍历");
        binaryTree.pre(A);  //ABCDEFGHK
        System.out.println();
        System.out.println("====================");

        System.out.println("中序遍历");
        binaryTree.in(A);  //BDCAEHGKF
        System.out.println();
        System.out.println("====================");

        System.out.println("后序遍历");
        binaryTree.post(A); //DCBHKGFEA 
        System.out.println();
        System.out.println("====================");

    }

    public void print(BNode bNode){
        System.out.print(bNode.getData());
    }

    public void pre(BNode root){  //前序遍历
        print(root);

        if(root.getLeftNode() != null){
            pre(root.getLeftNode());
        }

        if(root.getRightNode() != null){
            pre(root.getRightNode());
        }
    }

    public void in(BNode root){  //中序遍历

        if(root.getLeftNode() != null){
            in(root.getLeftNode());
        }

        print(root);

        if(root.getRightNode() != null){
            in(root.getRightNode());
        }
    }

    public void post(BNode root){  //后序遍历

        if(root.getLeftNode() != null){
            post(root.getLeftNode());
        }

        if(root.getRightNode() != null){
            post(root.getRightNode());
        }

        print(root);
    }

}