重温数据结构系列--二叉树、堆

二叉树是特殊的树，也是我们平时程序中用的比较多的一种数据结构，它具有以下特点：

1. 每个结点最多有两颗子树，结点的度最大为2。
2. 左子树和右子树是有顺序的，次序不能颠倒。
3. 即使某个结点只有一个子树，也要区分左右子树。

下面是二叉树的数据特性

4. 在二叉树的第i（根结点为1层）层上最多有2^(i-1)个结点（i>=1）。
5. 高度为k的二叉树，最多有2^k-1个结点（k>=0）。
6. 对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则 n=m+1。

特殊的二叉树及特点

1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。斜树应用场景较少。

2、满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。

满二叉树具有以下特点：

1. 叶子结点只能出现在最下一层。
2. 非叶子结点的度一定是2.
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点最多。

3、完全二叉树

对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。

完全二叉树具有以下特点：

1. 叶子结点只能出现在最底部两层。
2. 最底层叶子结点一定集中在左部连续位置。
3. 倒数第二层如果有叶子结点，一定出现在右部连续位置。
4. 同样数量结点的树，完全（满）二叉树的深度最小。
5. 对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：

• 如果i=1，则结点i是二叉树的根
• 如果i>1，则其双亲结点为i/2下取整。
• 如果2i<=n，则结点i的做孩子2i。
• 如果2i>n，则结点i无左孩子。
• 如果2i+1<=n，则结点i的右孩子为2i+1。
• 如果2i+1>n，则结点i无右孩子。

4、二叉 排序 树

二叉排序树，又称二叉查找树，也叫二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

(1) 若左子树不为空，则左子树上所有结点的值均小于或等于它的根结点的值。

(2) 若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值。

(3) 左、右子树也分别是二叉排序树。

，这篇文章中详细介绍了二叉排序树的创建（结点查找及插入），结点删除的过程，并且使用kotlin给出了相应程序实现。下面我们使用JavaScript实现二叉排序树创建、查找、删除的相关逻辑。

// 树的结点类
class Node {
    constructor(key, leftChild, rightChild) {
        this.key = key;
        this.left = leftChild;
        this.right = rightChild;
    }
}
// 二叉排序树类
class BinarySortTree {
    constructor() {}
    // 创建二叉排序树的数据结构
    create(data) {
        if(!(data instanceof Array) || data.length < 1) {
            return
        }
        var len = data.length;
        var tree = new Node(data[0], null, null);
        if(len == 1) {
            return tree;
        }
        for(let i=1; i<len; i++) {
            // i为0的位置为根结点，所以插入结点时i从1开始
            this.insertNode(tree, data[i]);
        }
        return tree;
    }
    // 只查找结点是否存在
    searchNode(tree, key) {
        if(!tree) {
            return false;
        }
        if(tree.key == key) {
            return true;
        }
        if(key < tree.key) {
            // 向左子树查找
            if(tree.left) {
                return this.searchNode(tree.left, key)
            }else {
                return false;
            }
        }else {
            // 向右子树查找
            if(tree.right) {
                return this.searchNode(tree.right, key)
            }else {
                return false;
            }
        }
    }
    // 插入结点
    insertNode(currentNode, key) {
        var node = new Node(key, null, null);
        if(key < currentNode.key) {
            // 如果key小于等于currentNode.key则将其插入到左子树上
            if(currentNode.left == null) {
                // 如果当前结点的左子树为空，说明当前结点为叶子结点，则直接为其添加孩子结点
                currentNode.left = node;
            }else {
                // 如果当前结点左子树不为空，则继续向下查找合适位置
                this.insertNode(currentNode.left, key);
            }
        }else {
            // 等于的情况下放到右子树，其他逻辑与左子树插入相同
            if(currentNode.right == null) {
                currentNode.right = node;
            }else {
                this.insertNode(currentNode.right, key);
            }
        }
    }
    // 删除指定key结点
    deleteNode(currentNode, key) {
        if(!currentNode) {
            return null;
        }
        if(!this.searchNode(currentNode, key)) {
            return currentNode;
        }
        
        if(key < currentNode.key) {
            currentNode.left = this.deleteNode(currentNode.left, key);
            return currentNode;
        }else if(key > currentNode.key) {
            currentNode.right = this.deleteNode(currentNode.right, key);
            return currentNode;
        }else {
            if(!currentNode.left && !currentNode.right) {
                // 如果是叶子结点
                currentNode = null;
                return currentNode;
            }
            if(!currentNode.right) {
                // 如果只有左子树
                currentNode = currentNode.left;
                return currentNode;
            }else if(!currentNode.left) {
                // 如果只有右子树
                currentNode = currentNode.right;
                return currentNode;
            }else {
                // 既有左子树又有右子树
                var minRightKey = this.findMinNode(currentNode.right);
                currentNode.key = minRightKey;
                currentNode.right = this.deleteNode(currentNode.right, minRightKey);
                return currentNode;
            }
        }
    }
    // 查找最小结点
    findMinNode(rightTree) {
        if(rightTree) {
            while(rightTree && rightTree.left) {
                rightTree = rightTree.left;
            }
            return rightTree.key;
        }
        return null;
    }
}

const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
var binSrotTree = new BinarySortTree();
var bstree = binSrotTree.create(arr);
console.log(bstree);
var searchResult = binSrotTree.searchNode(bstree, 100);
console.log(searchResult); // false
var newbstree = binSrotTree.deleteNode(bstree, 62);
console.log(newbstree);
复制代码

5、平衡二叉树

平衡二叉树（Balanced BinaryTree）又被称为AVL树（有别于AVL算法），它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注意：满二叉树和完全二叉树一定是平衡二叉树

二叉树的存储

1、链表存储（对象）

适用于所有二叉树，详细介绍见重温数据结构系列--树 树的存储--孩子兄弟表示法 。

2、顺序表存储（数组）

利用平衡二叉树平衡的特性，使用数组来存储完全二叉树，a[n]的左右子节点分别为a[2n+1]，a[2n+2]。

注：数组的下标是从0开始的，二叉树是从1开始的。

二叉树的遍历

1、先序遍历

基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。

图中先序遍历结果是：1，2，4，5，7，8，3，6。

先序遍历JavaScript实现见下面程序。

var sortedArr = [];
function preOrder(tree) {
    if(tree) {
        sortedArr.push(tree.key);
        middleOrder(tree.left);
        middleOrder(tree.right);
    }
}
复制代码

2、中序遍历

基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。

图中中序遍历结果是：4，2，7，8，5，1，3，6。

中序遍历JavaScript实现见下面程序。

var sortedArr = [];
function middleOrder(tree) {
    if(tree) {
        middleOrder(tree.left);
        sortedArr.push(tree.key);
        middleOrder(tree.right);
    }
}
middleOrder(bstree); // bstree为上文中创建的二叉排序树
console.log(sortedArr); //[ 35, 37, 47, 51, 58, 62, 73, 88, 93, 99 ]
复制代码

3、后序遍历

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。

图中后序遍历结果是：4，8，7，5，2，6，3，1。

后序遍历JavaScript实现见下面程序。

var sortedArr = [];
function postOrder(tree) {
    if(tree) {
        middleOrder(tree.left);
        middleOrder(tree.right);
        sortedArr.push(tree.key);
    }
}
复制代码

堆及特点

堆是什么？ 一般情况下 可以把堆认作是一种特殊的完全二叉树。非一般情况下堆是什么？阅读 堆和树有什么区别？堆为什么要叫堆，不叫树呢？

堆可以分为大根堆和小根堆。

大根堆：所有父结点都比子结点大的完全二叉树。

小根堆：所有父结点都比子结点小的完全二叉树。

总结

关于数据结构中二叉树相关的知识点有很多很多，本文提到的二叉树属于二叉树应用中比较常见的几种。还有更多的知识点可以阅读文章中引用的文章。此外，堆排序也是一种比较常见（经典）的排序方式，后序会有专门文章介绍。