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

亦凉 2022-06-06 00:13 192阅读 0赞

*   *  定义
     *  二叉树的几个重要性质
     *  二叉树的抽象数据类型ADT
     *  二叉树的存储结构
        
         *  顺序存储结构
         *  链式存储结构
            
             *   *  结点定义
                 *  二叉树初始化
                 *  二叉树的遍历
     *  测试二叉树的实现

## 定义 ##

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

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

![tree\_state][tree_state]

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

![left\_right\_tree][left_right_tree]

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

![skew\_tree][skew_tree]

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

![full\_tree][full_tree]

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

## 二叉树的几个重要性质： ##

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

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

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

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

对于二叉树的元素，主要的操作包括：  
1. 判别二叉树是否为空  
2. 遍历二叉树，按特定的顺序访问每个结点  
\- 前序遍历：根节点–>左子树–>右子树  
\- 中序遍历：左子树–>根节点–>右子树  
\- 后序遍历：左子树–>右子树–>根节点  
\- 层序遍历：从上至下，从左至右。  
3. 创建一个二叉树

## 二叉树的存储结构 ##

### 顺序存储结构 ###

![linear\_tree][linear_tree]

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

![linear\_tree\_array][linear_tree_array]

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

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

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

### 链式存储结构 ###

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

![link\_tree][link_tree]

##### 结点定义 #####

/**
     * 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

嗯，和预期想象的一致。

--------------------

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

[tree_state]: /images/20220606/c7eb9c2a713747b5aff38a24f48f1b3f.png
[left_right_tree]: /images/20220606/1dc0bce79e9e4c43b04132b5580c56dc.png
[skew_tree]: /images/20220606/edc594253ae94fe5a3d66b153824efb4.png
[full_tree]: /images/20220606/984efabec84547d88c16ecf58ff21471.png
[linear_tree]: /images/20220606/2c24f875228548d88e7c0e1023035edc.png
[linear_tree_array]: /images/20220606/63462d3a1afc4bf8a837de66e48c3322.png
[link_tree]: /images/20220606/aa26413907e64abeb3e514f4b69076d4.png