数据结构-二叉树的存储结构与遍历

定义

一个有穷的结点集合，可以为空。若不为空，则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。

1. 二叉树的五种基本形态：

1. 二叉树的子树是有顺序之分的，称为左子树和右子树

1. 几种特殊的二叉树
   • 斜二叉树

• 完美二叉树（满二叉树）

• 完全二叉树
  有n个结点的二叉树，对树中结点按从上之下，从左至右的顺序进行编号，编号为i(1<=1<=n)结点与满二叉树中编号为i结点在二叉树中位置相同

二叉树的几个重要性质：

1. 在二叉树的第i层上最多有2^i-1个节点 。（i>=1）
2. 二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）
3. 对任何非空二叉树T，若n₀表示度数为0的节点 n₂表示度数为2的节点,那么n₀=n₂+1;
4. 具有n个结点的完全二叉树的深度为 log₂n + 1

这里在补充一下树的其他一些性质和概念：

1. 结点的度：结点所拥有的子树的个数称为结点的度；
2. 树的度：树中各节点的度的最大值；因此，二叉树的度最大为2；
3. 结点的层数：规定根节点的层数为1，其余结点的层数为他的双亲结点层数加1
4. 输的深度：树中所有结点的最大层数。

二叉树的抽象数据类型(ADT)

对于二叉树的元素，主要的操作包括：

1. 判别二叉树是否为空
2. 遍历二叉树，按特定的顺序访问每个结点
   • 前序遍历：根节点-->左子树-->右子树
   • 中序遍历：左子树-->根节点-->右子树
   • 后序遍历：左子树-->右子树-->根节点
   • 层序遍历：从上至下，从左至右。
3. 创建一个二叉树

二叉树的存储结构

顺序存储结构

使用顺序存储结构，对完全二叉树这种结构是非常合适的。可以按照从上之下，从左至右顺序存储n个结点的完全二叉树的结点父子关系。

完全二叉树的这种存储结构，有以下特点

• 非根节点（序号i>1)的父节点序号（数组下标）是 i/2 (取整）。
• 结点（序号为i）的左孩子结点的序号是2i,如果2i>n,则没有左孩子；
• 结点（序号为i）的右孩子结点的序号是2i+1,如果2i+1>n,则没有右孩子。

一般普通的二叉树，在其空余位置补充控制，当做是完全二叉树，采用数组结构存储，将导致存储空间的浪费。

链式存储结构

二叉树的链式存储结构中，每一个结点包含三个关键属性:指向左子树的指针，数据域，指向右子树的指针；根据这个叙述，我们可以按如下结构定义结点。

结点定义

/**
 * Created by engineer on 2017/10/23.
 * <p>
 * 二叉树结点定义
 */
 
public class TreeNode < T > {
 
    // 数据域
    private T data;
    // 左子树
    private TreeNode < T > leftChild;
    // 右子树
    private TreeNode < T > rightChild;
 
    public TreeNode(T data) {
        this(null, data, null);
    }
 
    public TreeNode(TreeNode < T > leftChild, T data, TreeNode < T > rightChild) {
        this.leftChild = leftChild;
        this.data = data;
        this.rightChild = rightChild;
    }
 
    public T getData() {
        return data;
    }
 
    public TreeNode < T > getLeftChild() {
        return leftChild;
    }
 
    public TreeNode < T > getRightChild() {
        return rightChild;
    }
}

二叉树初始化

我们就以下图为例，构造一颗二叉树。

/**
     * 构建二叉树
     *
     * @return 树根
     */
TreeNode CreateTree() {
    TreeNode < String > nodeH = new TreeNode < >("H");
    TreeNode < String > nodeG = new TreeNode < >("G");
 
    TreeNode < String > nodeF = new TreeNode < >(nodeH, "F", null);
    TreeNode < String > nodeE = new TreeNode < >(nodeG, "E", null);
    TreeNode < String > nodeD = new TreeNode < >("D");
 
    TreeNode < String > nodeC = new TreeNode < >(null, "C", nodeF);
    TreeNode < String > nodeB = new TreeNode < >(nodeD, "B", nodeE);
    TreeNode < String > nodeA = new TreeNode < >(nodeB, "A", nodeC);
    return nodeA;
}

这样，我们就按上图所示构建了一颗二叉树，返回二叉树的根结点。

二叉树的遍历

二叉树的遍历是二叉树最要的操作，也是二叉树的核心。从二叉树的定义我们可以得知，二叉树是一种递归形式的数据结构，根结点下的左右子树又分别是二叉树；因此这使得二叉树的遍历离不开递归这种思想。

很显然，对于二叉树的三种遍历，我们就可以借助其自身的特性，通过递归实现。

• 二叉树的递归遍历实现

/**
     * 访问每个结点
     *
     * @param node
     */
 
private void visitNode(TreeNode node) {
    System.out.print(node.getData().toString());
    System.out.print(" ");
}
 
/**
     * 前序遍历-递归实现
     *
     * @param node
     */
void preTraversal(TreeNode node) {
    if (node != null) {
        visitNode(node);
        preTraversal(node.getLeftChild());
        preTraversal(node.getRightChild());
    }
}
 
/**
     * 中序遍历-递归实现
     *
     * @param node
     */
void traversal(TreeNode node) {
    if (node != null) {
        traversal(node.getLeftChild());
        visitNode(node);
        traversal(node.getRightChild());
    }
}
 
/**
     * 后序遍历-递归实现
     * @param node
     */
void postTraversal(TreeNode node) {
    if (node != null) {
        postTraversal(node.getLeftChild());
        postTraversal(node.getRightChild());
        visitNode(node);
    }
}

可以看到，使用递归实现二叉树的遍历十分简单，但我们也可以考虑使用非递归的形式，使用栈。

严格来说，使用栈实现二叉树的遍历，其实还是递归思想，只不过是我们自己用栈完成了递归实现中系统帮我们完成的工作。

本质上来说，二叉树这种递归的数据结构，他的遍历是离不开递归思想的，只不过看我们怎么去理解递归的实现了。

• 二叉树的非递归实现

/**
     * 前序遍历-迭代实现
     * @param node
     */
void preTraversalIteration(TreeNode node) {
    // 创建一个栈
    Stack < TreeNode > mStack = new Stack < >();
    while (true) {
        while (node != null) { // 非叶子结点的子树
            // 前序遍历，先访问根结点
            visitNode(node);
            // 将当前结点压入栈
            mStack.push(node);
            // 对左子树继续进行前序遍历
            node = node.getLeftChild();
        }
 
        if (mStack.isEmpty()) {
            //所有元素已遍历完成
            break;
        }
        // 弹出栈顶结点
        node = mStack.pop();
        // 右子树前序遍历
        node = node.getRightChild();
    }
}
 
/**
     * 中序遍历-迭代实现
     * @param node
     */
void TraversalIteration(TreeNode node) {
    // 创建一个栈
    Stack < TreeNode > mStack = new Stack < >();
    while (true) {
        while (node != null) { // 非叶子结点的子树
            // 将当前结点压入栈
            mStack.push(node);
            // 对左子树继续进行中序遍历
            node = node.getLeftChild();
        }
 
        if (mStack.isEmpty()) {
            //所有元素已遍历完成
            break;
        }
        // 弹出栈顶结点
        node = mStack.pop();
        // 中序遍历，访问根结点
        visitNode(node);
        // 右子树中序遍历
        node = node.getRightChild();
    }
}
 
/**
     * 后序遍历-迭代实现
     * @param node
     */
void postTraversalIteration(TreeNode node) {
    // 创建一个栈
    Stack < TreeNode > mStack = new Stack < >();
    while (true) {
        if (node != null) {
            //当前结点非空，压入栈
            mStack.push(node);
            // 左子树继续遍历
            node = node.getLeftChild();
        } else {
            // 左子树为空
            if (mStack.isEmpty()) {
                return;
            }
 
            if (mStack.lastElement().getRightChild() == null) {
                // 栈顶元素右子树为空，则当前结点为叶子结点，输出
                node = mStack.pop();
                visitNode(node);
                while (node == mStack.lastElement().getRightChild()) {
                    visitNode(mStack.lastElement());
                    node = mStack.pop();
                    if (mStack.isEmpty()) {
                        break;
                    }
                }
            }
 
            if (!mStack.isEmpty()) {
                node = mStack.lastElement().getRightChild();
            } else {
                node = null;
            }
        }
    }
}

可以看到，虽说是非递归实现，但本质上还是依靠栈先进后出的特性，实现了递归访问每个结点的操作，无非就是在前、中、后三种顺序下，访问结点的时机不同而已。这里，前序和中序遍历的实现其实很容易理解，后续遍历的实现很考究对栈的使用理解。

• 层序遍历

最后，再来说一说层序遍历。顾名思义，层序遍历就是从上到下按层，从左至右依次访问每个结点。这种遍历非常用规律，就是从根节点下一层开始，优先访问每一层所有的双亲结点，然后依次访问每个结点的左右儿子。也就是说，从上到下，先遇见到结点先访问，后遇到的结点后访问，这典型的就是队列的思想，因此我们可以使用队列实现二叉树的层序遍历。

/**
     * 层序遍历
     * @param node
     */
void levelTraversal(TreeNode node) {
    //创建队列
    Queue < TreeNode > mNodeQueue = new LinkedList < >();
    // 根结点加入队列
    mNodeQueue.add(node);
 
    TreeNode temp;
 
    while (!mNodeQueue.isEmpty()) {
        //元素出队列
        temp = mNodeQueue.poll();
        //输出
        visitNode(temp);
        if (temp.getLeftChild() != null) {
            // 左子树入队列
            mNodeQueue.add(temp.getLeftChild());
        }
 
        if (temp.getRightChild() != null) {
            //右子树入队列
            mNodeQueue.add(temp.getRightChild());
        }
    }
}

测试二叉树的实现

最后，用一个测试类测试一下我们对二叉树的实现。

/**
 * Created by engineer on 2017/10/24.
 */
 
public class BinaryTreeTest {
    
public
static
void
main
(String[] args)
{
        BinaryTree mBinaryTree = new BinaryTree();
 
        TreeNode root = mBinaryTree.CreateTree();
 
        System.out.print("前序遍历-递归实现:");
        mBinaryTree.preTraversal(root);
        System.out.print("\n中序遍历-递归实现:");
        mBinaryTree.traversal(root);
        System.out.print("\n后序遍历-递归实现:");
        mBinaryTree.postTraversal(root);
        System.out.println();
        System.out.print("\n前序遍历-迭代实现:");
        mBinaryTree.preTraversalIteration(root);
        System.out.print("\n中序遍历-迭代实现:");
        mBinaryTree.TraversalIteration(root);
        System.out.print("\n后序遍历-迭代实现:");
        mBinaryTree.postTraversalIteration(root);
        System.out.println();
        System.out.print("\n层序遍历:");
        mBinaryTree.levelTraversal(root);
 
    }
}

得到输出：

前序遍历-递归实现:A B D E G C F H 
中序遍历-递归实现:D B G E A C H F 
后序遍历-递归实现:D G E B H F C A 
 
前序遍历-迭代实现:A B D E G C F H 
中序遍历-迭代实现:D B G E A C H F 
后序遍历-迭代实现:D G E B H F C A 
 
层序遍历:A B C D E F G H

嗯，和预期想象的一致。

---

好了，二叉树的存储结构和遍历就到这里了。