数据结构基础学习之（树与二叉树）

主要知识点：
- 一、树
  - 1. 概念：
二、二叉树
三、哈夫曼树及哈夫曼编码
四、树、森林与二叉树的转换
- 1. 树转换为二叉树
2. 森林转换二叉树
五、树的存储结构

主要知识点：

树的定义及常用术语
树的存储表示
二叉树、满二叉树和完成二叉树的定义
二叉树的遍历此操作实现
哈夫曼树及其编码
树、森林与二叉树之间的转换

一、树

1. 概念：

定义：树是由n（n≥0）个结点组成的有限集合
特点：

有且仅有一个称为根(Root)的结点；
其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

树的常用术语

结点(node)

由一个数据元素及关联其子树的边组成

结点路径

若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从k1到kj的一条路径(Path)或道路。

路径的长度

指路径所经过的边(即连接两个结点的线段)的数目

结点的度(degree)

结点拥有的子树的数目

树的度

一棵树中最大的结点度数（拥有最多子树的节点，即结点的度最大值）

叶子结点(leaf)

结点的度为0的结点(没有子树的节点)，也叫终端结点

分支结点

结点的度不为0的结点（有子树的节点），也叫非终端结点

孩子结点

一个结点的孩子结点是指这个结点的子树的根结点

双亲结点(parents)

一个结点有孩子结点，则这个结点称为它孩子结点的双亲结点

子孙结点

即一个结点A所有子树的结点称为该结点A的子孙结点

祖先结点

即一个结点A的祖先结点是指路径中除结点A外的的结点

兄弟结点(sibling)

同一双亲结点的孩子结点之间互成为兄弟结点

结点的层次

从根结点算起，根为第一层，它的孩子为第二层

树的深度

树中结点的最大层次数

有序树与无序树

如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树

森林

m(m>=0)棵互不相交的树的集合

二、二叉树

定义：

二叉树(BinaryTree): 是n(n≥0)个结点的有限集, 它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
满二叉树：是二叉树的特殊形态，除叶节点外的所有结点都有左右子树的二叉树，称为满二叉树
完全二叉树：也是二叉树的特殊形态，
单分支树：所有节点都没有左结点（或右结点）的二叉树

二叉树五种基本形态

数据结构基础学习之（树与二叉树） - 图1

二叉树的性质

二叉树第i层上的结点数目最多为 $数据结构基础学习之（树与二叉树） - 图2$ #card=math&code=2%5E%7Bi%7D%28i%E2%89%A50%29)
深度为k的二叉树至多有 $数据结构基础学习之（树与二叉树） - 图3$ #card=math&code=2%5E%7Bk%7D-1%20%28k%E2%89%A51%29)个结点。
在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
具有n个结点的完全二叉树，其深度为 $数据结构基础学习之（树与二叉树） - 图4$ 或 $数据结构基础学习之（树与二叉树） - 图5$ #card=math&code=%5Clog_2%20%28n%2B1%29)
对于具有n个结点的完全二叉树，若从根结点开始自上而下，从左到右开始编号，对于任意编号i（0<=i

若i=0,则结点为根结点，没有双亲，若i>0,则它的双亲结点编号为 $数据结构基础学习之（树与二叉树） - 图6$
若2i+1 >=n ,则编号i结点无左孩子，否则编号2i+1的结点就是它的左孩子
若2i+2 >=n ,则编号i结点无右孩子，否则编号2i+2的结点就是它的右孩子

满二叉树和完全二叉树示意图

数据结构基础学习之（树与二叉树） - 图7

二叉树存储结构

顺序存储结构示意图

数据结构基础学习之（树与二叉树） - 图8

链式存储结构示意图

数据结构基础学习之（树与二叉树） - 图9

数据结构基础学习之（树与二叉树） - 图10

二叉树的遍历

前序遍历

/**
     * 递归的前序遍历
     * <p>
     * 1. 从根结点出发
     * 2. 先遍历完左子树
     * 3. 再遍历右子树
     * <p>
     * （注意：顺序: 中左右）
     *
     * @param treeNode
     */
    public void preOrderTraverse(BiTreeNode treeNode) {
        if (treeNode == null) return;
        //结点数据
        System.out.println(treeNode.data.toString());
        //先遍历左子树
        preOrderTraverse(treeNode.LChild);
        //然后遍历右子树
        preOrderTraverse(treeNode.RChild);
    }
    /**
     * 非递归的前序遍历
     */
    public void preOrderTraverse() {
        //获取根结点
        BiTreeNode<T> node = root;
        if (node == null) return;
        //构造一个栈，由于存储右子树结点
        LinkStack<BiTreeNode> stack = new LinkStack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            //弹出栈顶结点
            node = stack.pop();
            //访问该结点
            System.out.println(node.data.toString());
            while (node != null) {
                //如果左结点不为空，则访问
                if (node.LChild != null)
                    System.out.println(node.LChild.data);
                //如果右结点不为空，则先压入栈中
                if (node.RChild != null)
                    stack.push(node.RChild);
                //继续遍历左结点
                node = node.LChild;
            }
        }
    }

中序遍历

/**
     * 中序遍历（递归方式）
     * <p>
     * 1. 从左子树出发开始遍历
     * 2. 遍历到根结点
     * 3. 又从根结点出发，遍历右子树
     * <p>
     * （注意：顺序: 左中右）
     *
     * @param treeNode
     */
    public void inOrderTraverse(BiTreeNode treeNode) {
        if (treeNode == null) return;
        //遍历左子树
        inOrderTraverse(treeNode.LChild);
        //结点数据
        System.out.println(treeNode.data.toString());
        //遍历右子树
        inOrderTraverse(treeNode.RChild);
    }
    /**
     * 中序遍历（非递归）
     */
    public void inOrderTraverse() {
        BiTreeNode<T> node = this.root;
        if (node != null) {
            LinkStack<BiTreeNode> stack = new LinkStack<>();
            stack.push(node);
            while (!stack.isEmpty()) {
                while (stack.peek() != null)
                    stack.push(stack.peek().LChild);  //把左结点入栈，直到最左下的结点
                //弹出空结点
                stack.pop();
                if (!stack.isEmpty()) {
                    node = stack.pop();
                    //打印结点
                    System.out.print(node.data.toString());
                    //把该结点的右子结点入栈
                    stack.push(node.RChild);
                }
            }
        }
    }

后序遍历

/**
     * 后序遍历
     * <p>
     * 1. 以从左到右的方式
     * 2. 先遍历左子树
     * 3. 然后遍历右子树
     * 4. 最后遍历右子树
     * <p>
     * 顺序： 左右中
     */
    public void postOrderTraverse(BiTreeNode treeNode) {
        if (treeNode == null) return;
        postOrderTraverse(treeNode.LChild);
        postOrderTraverse(treeNode.RChild);
        System.out.println(treeNode.data.toString());
    }
    /**
     * 后序遍历（非递归）
     */
    public void postOrderTraverse() {
        //获取根结点
        BiTreeNode node = this.root;
        if (node != null) {
            LinkStack<BiTreeNode> stack = new LinkStack<>();
            //将根结点入栈
            stack.push(node);
            //设置结点访问标识
            boolean flag;
            //设置指针，指向访问过的结点
            BiTreeNode p = null;
            while (!stack.isEmpty()) {
                //将结点的左子结点入栈
                while (stack.peek() != null)
                    stack.push(stack.peek().LChild);
                //弹出空结点
                stack.pop();
                while (!stack.isEmpty()) {
                    //查看栈顶元素
                    node = stack.peek();
                    //如果该结点的右子结点为空，或已访问过，则该结点可以出栈访问
                    if (node.RChild == null || node.RChild == p) {
                        //访问结点
                        System.out.print(node.data.toString());
                        //出栈
                        stack.pop();
                        //已访问指针指向该结点
                        p = node;
                        //标识为已访问
                        flag = true;
                    } else {
                        //否则，将该结点的右子结点入栈，
                        stack.push(node.RChild);
                        // 标识该结点还没访问
                        flag = false;
                    }
                    if (!flag) {
                        break;
                    }
                }
            }
        }
    }

层次遍历

/**
     * 层次遍历
     */
    public void levelTraverse() {
        BiTreeNode<T> node = this.root;
        if (node != null) {
            //初始化队列
            LinkQueue<BiTreeNode> queue = new LinkQueue<>();
            //根结点入队列
            queue.offer(node);
            while (!queue.isEmpty()) {
                //出队列
                node = queue.poll();
                //访问该结点
                System.out.println(node.data.toString());
                //该结点的左子结点入队列
                if (node.LChild != null) {
                    queue.offer(node.LChild);
                }
                //该结点的右子结点入队列
                if (node.RChild != null) {
                    queue.offer(node.RChild);
                }
            }
        }
    }

二叉树的建立

由前序遍历和中序遍历，或后序遍历和中序遍历推导建立二叉树

/**
     * 二叉树的建立
     *
     * @param preOrder 前序遍历的序列
     * @param inOrder  中序遍历的序列
     * @param preIndex 前序遍历开始位置
     * @param inIndex  中序遍历开始位置
     * @param count    结点数
     */
    public LinkBiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {
        if (count > 0) {
            //获取前序遍历的序列的根结点
            char r = preOrder.charAt(preIndex);
            //记录根结点在中序遍历中的位置
            int i = 0;
            for (; i < count; i++) {
                if (r == inOrder.charAt(i + inIndex)) {
                    break;
                }
            }
            root = new BiTreeNode(r);
            root.LChild = new LinkBiTree(preOrder, inOrder, preIndex + 1, inIndex, i).root;
            root.RChild = new LinkBiTree(preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1).root;
        }
    }

由标明空子树的前序遍历建立二叉树

/**
     * 由标明的空子树建立二叉树
     *
     * @param preOrder
     */
    private static int preIndex = 0;
    public LinkBiTree(String preOrder) {
        //获取前序遍历中的根结点
        char c = preOrder.charAt(preIndex++);
        //如果字符不为#
        if ('#' != c) {
            //创建根结点
            root = new BiTreeNode(c);
            //创建左子树
            root.LChild = new LinkBiTree(preOrder).root;
            //创建右子树
            root.RChild = new LinkBiTree(preOrder).root;
        } else {
            root = null;
        }
    }

由完全二叉树顺序存储序列建立二叉树

/**
     * 使用完全二叉树的顺序存储结构建立二叉链式存储结构
     *
     * @param sqBiTree 序列
     * @param index    根结点标识
     */
    public LinkBiTree(String sqBiTree, int index) {
        if (index < sqBiTree.length()) {
            root = new BiTreeNode(sqBiTree.charAt(index));
            //建立左右子树
            root.LChild = new LinkBiTree(sqBiTree, 2 * index + 1).root;
            root.RChild = new LinkBiTree(sqBiTree, 2 * index + 2).root;
        }
    }