数据结构（七）：二叉树

梦里梦外; 2021-09-11 08:44 320阅读 0赞

## 二叉树的定义 ##

*  二叉树是 n （n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树）或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成

![9434708-3ffd72a2c875b75c.png][]

图1

*  折半规律很适合作为二叉树建模

![9434708-91f006d2c6f2abaa.png][]

图2

*  **二叉树特点**
    
     *  每个节点最多有两棵子树
     *  左子树和右子树是有顺序的，次序不能任意颠倒
     *  即使树中某节点只有一棵子树也要区分它是左子树还是右子树
 *  **特殊二叉树**
    
     *  **斜树**：所有的节点都只有左子树的二叉树叫做左斜树，反之右斜树
     *  **满二叉树**：所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上
    
    ![9434708-b81d10b62d7f4b5a.png][]
    
    满二叉树
    
     *  **完全二叉树**：叶子节点只能出现在最下两层，最下层的叶子一定集中在左部连续位置，倒数二层，若有叶子节点，一定都在右部连续位置，如果节点度为 1，则该节点只有左孩子，既不存在右子树情况，同样节点数的二叉树，完全二叉树的深度最小
    
    ![9434708-757f3769f5980131.png][]
    
    完全二叉树

## 二叉树的性质 ##

### 二叉树性质1 ###

*  在二叉树的第 i 层上至多有 2的i-1次方个节点 (i>=1)

### 二叉树性质2 ###

*  深度为 k 的二叉树至多有 2的k次方-1个节点 （k>=1）

### 二叉树性质3 ###

*  如果端节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1
 *  终端节点其实就是叶子节点数，而一棵二叉树除了叶子节点外，剩下的就是度为 1 或 2 的节点数了，我们设 n1 为度是 1 的节点数，则树节点总数是 n=n0+n1+n2
 *  图5 度为2的节点数 n2 = 4，则叶子节点数 n0 = 4+1，树节点总数 n=4+1+5

![9434708-232bcaed95680b1b.png][]

图5

#### 二叉树性质4 ####

*  具有 n 个节点的完全二叉树的深度为 \[log2n\]+1 (\[x\] 表示不大于 x 的最大整数)
 *  如 图1 有 10 个节点，则深度 4 = log 以2为底10的对数 + 1 = 3 + 1

#### 二叉树性质5 ####

*  对于一棵有 n 个节点的完全二叉树（其深度为 \[log2n\]+1）的节点按层序编号（从第 1 层到第 \[log2n\]+1 层，每层从左到右），对任一节点 i 有：
    
     *  如果 i =1，则节点 i 是二叉树的根，则无双亲，如果 i > 1，则其双亲是节点 \[i/2\]（下图节点7，它的双亲就是 \[7/2\] = 3）
     *  如果 2i > n，则节点 i 无左子树（节点 i 为叶子节点），否则其左子树是节点 2i，（下图节点6，因为 2\*6=12 超过了节点总数 10，所以它无左子树，而节点5 因为等于10，所以它的左子树节点为 10）
     *  如果 2i + 1 > n，则节点 i 无右子树，否则其右子树是节点 2i+1，（下图节点5，因为 2\*5+1=11 大于节点总数 10，所以它无右子树，因为节点2 小于 10，所以它的右子树节点为 7）

![9434708-ae2eb6ccf4d27d46.png][]

图6

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

### 二叉树顺序存储 ###

*  二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系，比如双亲与子节点、兄弟节点的关系

![9434708-e8f295f18e7b3e75.png][]

图7

*  对于一般的二叉树，层序编号不能反应逻辑关系，但是可以将其按完全二叉树编号，把不存在的节点设置为 "^"

![9434708-f1738e75bf4de09c.png][]

图8

*  考虑一种极端情况，一棵深度为 k 的右斜树，它只有 k 个节点，却要分配 2的k次方-1 个存储单元空间，这显然是对存储空间的浪费，所以顺序存储结构一般只用于完全二叉树

![9434708-2a2685229f8fe4c3.png][]

图9

### 二叉链表 ###

*  二叉树每个节点最多有两个子节点，所以为它设计一个数据域与两个指针域

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">lchild</th> 
   <th style="text-align:center">data</th> 
   <th style="text-align:center">rchild</th> 
  </tr> 
 </thead> 
 <tbody> 
 </tbody> 
</table>

## 遍历二叉树 ##

*  二叉树的遍历是指从根节点触发，按照某种次序依次访问二叉树中所有的节点，使得每个节点都被访问一次且仅被访问一次

### 1. 前序遍历 ###

*  先访问根节点，然后前序遍历左子树，再前序遍历右子树，遍历顺序为：ABDGHCEIF

![9434708-031dd7e5e289df29.png][]

[avtTz.png][]

### 2. 中序遍历 ###

*  中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树，遍历顺序为：GDHBAEICF

![9434708-cd8264808ceed803.png][]

[av1Sa.png][]

### 3. 后续遍历 ###

*  从左到右先叶子后节点的方式遍历左右子树，最后访问根节点，遍历顺序为：GHDBIEFCA

![9434708-536e89ae4dbc8832.png][]

[av64S.png][]

### 4. 层序遍历 ###

*  从树的根节点开始访问，从上而下逐层遍历，在同一层中，从左到右顺序对节点逐个访问，遍历顺序为：ABCDEFGHI

![9434708-bba5891b567f7b58.png][]

[avKP2.png][]

## 简单的二叉树代码例子 ##

import java.util.ArrayList;
    import java.util.List;
    
    public class BinTree {
        private BinTree root;       // 根节点
        private BinTree lChild;   // 左子树
        private BinTree rChild;  // 右子树
        private Object data;    // 数据域
        private List<BinTree> datas;    // 存储的所有节点
    
        public BinTree(BinTree lChild, BinTree rChild, Object data) {
            this.lChild = lChild;
            this.rChild = rChild;
            this.data = data;
        }
    
        public BinTree(Object data) {
            this.data = data;
        }
    
        public BinTree() {
        }
    
        public void createTree(Object[] objs) {
            datas = new ArrayList<>();
            for (Object object : objs) {
                datas.add(new BinTree(object));
            }
            root = datas.get(0);// 将第一个节点作为根节点
            for (int i = 0; i < datas.size() / 2; i++) {
                datas.get(i).lChild = datas.get(i * 2 + 1);     // 设置左子树
                if ((i * 2 + 2) < datas.size()) {   // 避免越界
                    datas.get(i).rChild = datas.get(i * 2 + 2); // 设置右子树
                }
            }
        }
    
        // 前序遍历：从根节点开始，先遍历左子树，再遍历右子树
        public void preorder(BinTree root) {
            if (root != null) {
                System.out.println(root.getData());
                preorder(root.lChild);
                preorder(root.rChild);
            }
        }
    
        // 中序遍历：从根节点先遍历左子树，在根节点，最后右子树
        public void inorder(BinTree root) {
            if (root != null) {
                inorder(root.lChild);
                System.out.println(root.getData());
                inorder(root.rChild);
            }
        }
    
        // 后续遍历：从左到右最后再根节点
        public void afterorder(BinTree root){
            if(root != null){
                afterorder(root.lChild);
                afterorder(root.rChild);
                System.out.println(root.getData());
            }
        }
    
        public Object getData() {
            return data;
        }
    
        public BinTree getRoot() {
            return root;
        }
    
        public static void main(String[] args) {
            BinTree binTree = new BinTree();
            Object[] objects = new Object[]{1, 2, 3, 4, 5, 6, 7, 8,9,10};
            binTree.createTree(objects);
            binTree.afterorder(binTree.getRoot());
        }
    }

[9434708-3ffd72a2c875b75c.png]: /images/20210811/851115a9fe4b47afa41655842fb7d9fb.png
[9434708-91f006d2c6f2abaa.png]: /images/20210811/95e593f05ca94f62b2797678a8fabb5f.png
[9434708-b81d10b62d7f4b5a.png]: /images/20210811/d0144d9031c443b59b0a4f6b7c94acc5.png
[9434708-757f3769f5980131.png]: /images/20210811/49c40562e0054ae88ed1ae68a4a535cd.png
[9434708-232bcaed95680b1b.png]: /images/20210811/94622d3051b44c3385b20967260e0a9c.png
[9434708-ae2eb6ccf4d27d46.png]: /images/20210811/8ad5e5249e054d8a93c7de9752be472f.png
[9434708-e8f295f18e7b3e75.png]: /images/20210811/f041be7ac54e4e25be45a4be567410e1.png
[9434708-f1738e75bf4de09c.png]: /images/20210811/4219ec734f534af7b66f17aa50e626d3.png
[9434708-2a2685229f8fe4c3.png]: /images/20210811/596b46509e8f4af3bdc6e66c8ed3e6ff.png
[9434708-031dd7e5e289df29.png]: /images/20210811/263afd5ea86d442c8da779ec67dfcd2d.png
[avtTz.png]: https://simimg.com/i/avtTz
[9434708-cd8264808ceed803.png]: /images/20210811/3387c695049645fc9aa3393972dab87c.png
[av1Sa.png]: https://simimg.com/i/av1Sa
[9434708-536e89ae4dbc8832.png]: /images/20210811/b59b7c29d19b4d4e909b06ee89dbf845.png
[av64S.png]: https://simimg.com/i/av64S
[9434708-bba5891b567f7b58.png]: /images/20210811/0e8eb06465ae4d9db229a02e9a7280bc.png
[avKP2.png]: https://simimg.com/i/avKP2