压缩算法从入门到放弃之二叉树（1）-白红宇

作者: 玄夜时间: 2018.6.30

前言

算法，永不过时！

干码农干了好几年了，感觉自己能拿出手的东西并不多啊，所以最近有了重新拾起算法这块的想法；

进入正题，这是一个压缩算法系列的文章，从最简单的二叉树开始写，敬请关注。

一、二叉树的简介

二叉树是数据结构中树家族最为基础的结构。

1、二叉树应用场景：

①、哈夫曼编码，简单有效的压缩算法

②、快速排序、查找

2、二叉树的特性：

①、二叉树的每个结点至多只有二棵子树；

②、二叉树的子树有左右之分，次序不能颠倒；

③、二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点。

3、二叉树的基本形态：

二叉树是递归定义的，其结点有左右子树之分：

①空二叉树——如图(a)；

②只有一个根结点的二叉树——如图(b)；

③只有左子树——如图(c)；

④只有右子树——如图(d)；

⑤完全二叉树——如图(e)。

4.二叉树的表达方法：

①、图像表达法，如图：

②、符号表达法:

以上图为例（A,(B(D,E),C(F)）

③、遍历表达法：

先序遍历为ABDECF

中序遍历为DBEAFC

后序遍历为DEBFCA

二、实战

好了，上面写的都是一些基本的知识点，现在直接上代码，简单粗暴：

1、先建一个类

package com.jt.tree;import java.util.ArrayList;import java.util.List;/** * Created by jay on 2018/6/30. */public class Tree {    private Tree root;//根节点    private Tree left;//左节点    private Tree right;//右节点    private Object obj;//数据域    private List
    
      datas;//存储所有节点    public Tree(Tree left, Tree right, Object obj) {        super();        this.left = left;        this.right = right;        this.obj = obj;    }    public Tree(Object obj) {        this(null, null, obj);    }    public Tree() {        super();    }    /**     * 构建一个二叉树     * @param objs     */    public void createTree(Object[] objs){        datas=new ArrayList
     
      ();        for (Object obj : objs) {            datas.add(new Tree(obj));        }        root=datas.get(0);//将0作为根节点        for (int i = 0; i < objs.length/2; i++) {            datas.get(i).left=datas.get(i*2+1);            if(i*2+2

2、测试代码：

Tree tree = new Tree();    Object[] obj = {1,2,3,4,5,6};    tree.createTree(obj);        tree.preorder(tree.getRoot());    System.out.println("\n");    tree.inorder(tree.getRoot());    System.out.println("\n");    tree.postorder(tree.getRoot());复制代码

3、测试结果：

本篇文章就到这了，有哪里不对的请各位指点。

前言