Java 数据结构 二叉树

基本术语

1. 结点：树中的一个独立的单元。包含一个数据元素及若干个分支（二叉树最多两个）
2. 结点的度：结点拥有的子树数称为结点的度
3. 树的度：树的度是树内各个结点中最大的度
4. 叶子：度为0的结点称为叶子或终端结点
5. 非终端结点：非叶子的结点
6. 双亲和孩子：结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲
7. 兄弟：父结点相同的结点即为兄弟结点
8. 树的深度：树中结点的最大层次称为树的深度或高度

介绍

与前面所介绍循序表以及链表的结构所不同，树结构是一种描述非线性层次关系的数据结构。
其主要有一下几个特点：

• 在一个树结构中，有且仅有一个结点没有直接前驱，那这个结点就是树的根结点
• 除了根结点外，其余结点有且仅有一个直接前驱
• 每个结点可以有n个直接后驱（二叉树最多只有两个）
  而在树结构中，二叉树是最简单的一种形式。在研究树结构时，二叉树是树结构内容中的重点。二叉树的描述、处理相对简单，而且更重要的是，任意的树都可以转为二叉树，因此，二叉树是所有树的基础。

二叉树 结构图

二叉树-循环存储.png

二叉树遍历算法

主要有以下三种：

• 先序遍历
• 中序遍历

• 后序遍历

  
  先序遍历.png
  中序遍历.png
  后序遍历.png

Java代码实现

/**
 * 二叉树结构
 * Created by Sheldon on 2019/4/3.
 * Project Name: alstudy.
 * Package Name: tree.
 */

// 二叉树结构
public class ChainTree {

    // 结点数据
    String data;
    // 左子树
    ChainTree leftTree;
    // 右子树
    ChainTree rightTree;
    // 二叉树根结点
    ChainTree root;

    /**
     * 初始化二叉树，向根结点插入数据
     * @param data
     */
    ChainTree(String data){
        this.data = data;
        this.root = this;
    }

    public static ChainTree bulieTree(String[] datas, int index){
        ChainTree node = null;
        if (index<datas.length){
            String value = datas[index];
            if (value=="#"){
                return null;
            }
            node = new ChainTree(value);
//            node.leftTree = bulieTree(datas, 2*index+1);
//            node.rightTree = bulieTree(datas,2*index+2);
            node.addLeftTree(bulieTree(datas, 2*index+1));
            node.addRightTree(bulieTree(datas,2*index+2));
            return node;
        }
        return node;
    }

    /**
     * 添加左子树
     * @return
     */
    public void addLeftTree(ChainTree node){
        leftTree = node;
    }

    /**
     * 添加右子树
     * @return
     */
    public void addRightTree(ChainTree node){
        rightTree = node;
    }

    /**
     * 先序遍历
     * @param root
     */
    public void DLR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            System.out.printf(node.data+", ");
            DLR(node.leftTree);
            DLR(node.rightTree);
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    public void LDR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LDR(node.leftTree);
            System.out.printf(node.data+", ");
            LDR(node.rightTree);
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    public void LRD(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LRD(node.leftTree);
            LRD(node.rightTree);
            System.out.printf(node.data+", ");
        }
    }

    /**
     * 二叉树深度
     * @param node
     * @return
     */
    public int depth(ChainTree node){
        int depleft, depright;
        if (node==null){
            return 0;
        }else {
            depleft = depth(node.leftTree);
            depright = depth(node.rightTree);
            if (depleft>depright){
                return depleft+1;
            }else {
                return depright+1;
            }
        }
    }

    public static void main(String[] args) {
        String[] datas = new String[]{"0","1","2","3","4","5","6","7","8","9","10"};
        // 构建双叉树
        ChainTree chainTree = bulieTree(datas,0);
        // 先序遍历（中->左->右）
        chainTree.DLR(chainTree.root);
        System.out.println();
        // 中序遍历（左->右->中）
        chainTree.LDR(chainTree.root);
        System.out.println();
        // 后序遍历（左->右->中）
        chainTree.LRD(chainTree.root);
        System.out.println();
        // 二叉树深度
        System.out.println(chainTree.depth(chainTree.root));;
    }
}

运行结果：

运行结果