数据结构04-二叉树

一、树的基本概念

1.树

树是n(n>=0)个节点的有限集。n=0时称为空树。在任意一颗非空树中：

1. 有且仅有一个特定的称为根(Root)的节点；
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、......、Tm，其中每一个集合本事又是一颗树，并且称为根的子树(SubTree)。

2.度

节点的度是节点拥有的子树数。度为0的节点称为叶子节点或终端节点，度不为0的节点称为非终端节点或分支节点。除根节点以外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。

3.层次

节点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某节点在第n层，则其字数的根就在第n+1层。其双亲在同一层的节点互为堂兄弟。树中节点的最大层次称为树的深度(Depth)或高度。

4.森林

森林(Forest)是m(m>=0)棵互不相交的集合。

5.树的存储结构

简单的顺序存储不能满足树的实现，一般结合顺序存储和链式存储来实现，有四种表示方法：

• 双亲表示法：在每个节点中，附设一个指示器指示其双亲节点到链表中的位置。
• 孩子表示法：在每个节点中，附设几个指示器指示子节点到链表中的位置。
• 双亲孩子表示法：在每个节点中，附设2个指示器，一个指示双亲节点，一个指示孩子链表(由它的孩子节点组成的单链表)。
• 孩子兄弟表示法：在每个节点中，附设2个指示器，一个指示它的第一个孩子节点，一个指向它的下一个兄弟节点。

二、二叉树的基本概念

1.二叉树

二叉树(Binary Tree)是n(n>=0)个节点的有限集合，该集合或者位空集(称为空二叉树)，或者有一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

2.斜树

斜树是所有的节点都只有左子树或右子树的二叉树，拥有左子树的叫左斜树，拥有右子树的叫右斜树。

3.满二叉树

满二叉树是所有的分支节点都存在左子树和右子树，并且所有叶子都在同一层的二叉树。

4.完全二叉树

对一颗具有n个节点的而擦汗数按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则这颗二叉树就是完全二叉树。完全二叉树可以理解位连续的二叉树。

5.二叉树的性质

性质1：在二叉树的第i层上至多有2^(i-1)个节点（i>=1）。

性质2：深度为k的二叉树至多有2^k-1个节点（k>=1）。

性质3：对任何一颗二叉树T，如果其终端节点数为n0,度为2的节点数为n1，则n0 = n1+1。

性质4：具有n个节点的完全二叉树深度为log(2)(n)+1。

性质5：如果对一颗有n个节点的完全二叉树的节点按层序编号（从第1层到第log(2)(n)+1层，每层从左到 右），对任意一个节点i(1<=i<=n)有：

1. 如果i=1,则节点i是二叉树的根，无双亲；如果i>1,则其双亲是结 点[i/2]
2. 如果2i>n,则节点i无左孩子（节点i为叶子节点）；否则其左孩 子是节点2i。
3. 如果2i+1>n,则节点i无右孩子；否则其右孩子是节点2i+1。

6、二叉树的实现

二叉树有两种实现方式：数组和链表。

三、二叉树的遍历

二叉树有3种遍历：

• 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
• 中序遍历：规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树
• 后序遍历：规则是若树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点

二叉树的遍历可以用递归和栈来实现。递归实现很简单，但是栈实现也需要知道。

1.递归

/**
 * 递归遍历
 *
 * @param root 根节点
 * @param type 遍历方式：0代表前序，1代表中序，2代表后序
 */
public void ergodicRecursion(Node<E> root, int type) {
    if (root == null) {
        return;
    }
    if (type == PREORDER) {
        ToolShow.log("前序：" + root.toString());
    }
    ergodicRecursion(root.left, type);
    if (type == INORDER) {
        ToolShow.log("中序：" + root.toString());
    }
    ergodicRecursion(root.right, type);
    if (type == AFTERORDER) {
        ToolShow.log("后序：" + root.toString());
    }
}

2.栈

/**
 * 用栈遍历
 *
 * @param curr 当前节点
 * @param type 遍历方式：0代表前序，1代表中序，2代表后序
 */
public void ergodicStack(Node<E> curr, int type) {
    //存放节点
    Stack<Node<E>> stack = new Stack<>();
    //记录已经添加过的节点
    List<Node<E>> nodeList = new ArrayList();
    stack.push(curr);
    nodeList.add(curr);
    while (curr != null) {
        //第一次递归之前：只执行一次
        if (type == PREORDER && !nodeList.contains(curr.left) && !nodeList.contains(curr.right)) {
            ToolShow.log("前序：" + curr.data);
        }
        //相当于第一次递归:已经添加过的节点不能重复添加
        if (curr.left != null && !nodeList.contains(curr.left)) {
            curr = curr.left;
            stack.push(curr);
            nodeList.add(curr);
        } else {
            //第二次递归之前：只执行一次
            if (type == INORDER && !nodeList.contains(curr.right)) {
                ToolShow.log("中序：" + curr.data);
            }
            //相当于第二次递归
            if (curr.right != null && !nodeList.contains(curr.right)) {
                curr = curr.right;
                stack.push(curr);
                nodeList.add(curr);
                //两次递归结束
            } else {
                if (type == AFTERORDER) {
                    ToolShow.log("后序：" + curr.data);
                }
                stack.pop();
                curr = stack.isEmpty() ? null : stack.lastElement();
            }
        }
    }
}

四、树的转换

1.树转二叉树

1. 加线。在所有兄弟节点之间就加一条连线。
2. 去线。对树中每一个节点，只保留它与第一个孩子节点的连线，删除它与其他孩子节点之间的连线。
3. 层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树节点的左孩子，兄弟转换过来的孩子是节点的右孩子。

2.森林转二叉树

1. 把每棵树转为二叉树
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子，用线连接起来。当所有的二叉树连接起来后，就得到了右森林转换的二叉树。

3.二叉树转树

1. 加线。若某节点的左孩子存在，则将这个左孩子的右孩子、右孩子的右孩子、...，即这个左孩子的n个右孩子作为此节点的孩子。将该节点与这些右孩子节点用线连起来。
2. 去线。删除原二叉树中所有节点与其右孩子节点的连线。
3. 层次调整。使之层次分明。

4.二叉树转森林

判断一颗二叉树能转换成一颗树还是森林，只要看这颗二叉树的根节点有没有右孩子，有就是森林，没有就是一棵树。转换森林的步骤如下：

1. 从根节点开始，若有右孩子存在，则把与右孩子节点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除...，直到所有右孩子连线都删除位置，得到分离的二叉树。
2. 再将每颗分离的二叉树转为树即可。

最后

代码地址：https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/datastructure/tree/TreeBinary.java

数据结构与算法专题：https://www.jianshu.com/nb/25128590

喜欢请点赞，谢谢！