摘要：今天溫習的是樹中比較簡單常用的二叉樹。因為一個簡單固定的結(jié)構(gòu)更有利于查詢，所以有了二叉查找樹的概念。簡單介紹下研究依然以點線模型的分析理解，不過樹是從一個方向順勢的分支結(jié)構(gòu)。

樹和圖一樣，是常用的數(shù)據(jù)結(jié)構(gòu)模型，但是我的理解樹是圖的一個用于更具體的數(shù)據(jù)結(jié)構(gòu)。今天溫習的是樹中比較簡單、常用的二叉樹。因為一個簡單固定的結(jié)構(gòu)更有利于查詢，所以有了二叉查找樹的概念。內(nèi)容來源來自《JavaScript 數(shù)據(jù)結(jié)構(gòu)和算法》。

研究依然以點-線模型的分析理解，不過樹是從一個方向順勢的分支結(jié)構(gòu)。這里可以是自上向下，也可以自下向上。

樹的常見術(shù)語有幾個：

根節(jié)點

子節(jié)點

葉子節(jié)點

層

子樹

路徑

鍵（這里是抽象主要的數(shù)據(jù)）

二叉樹：

子節(jié)點不超過兩個

左節(jié)點

右節(jié)點

如果具備查找特性：

較小值在左，較大值在右

這里準備一組值來構(gòu)建樹：

[ 23, 45, 16, 37, 3, 99, 22 ]

然后我需要構(gòu)建的樹的成品是：

首先需要構(gòu)造一個節(jié)點對象，來表示節(jié)點這一個描述元素

class Node {
    constructor (data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    getData () {
        return this.data;
    }

    output() {
        console.log(this.data);
    }
}

主要包含：

data: 節(jié)點的鍵

left: 左節(jié)點

right: 右節(jié)點

getData: 獲取鍵

output: 輔助輸出函數(shù)

樹的對象以及樹的操作

class Tree {
    constructor () {
        // 根節(jié)點默認是 null
        this.root = null;
    }

    // 插入節(jié)點
    insert (data) {
        const node = new Node(data, null, null);

        if(this.root === null) {
            this.root = node;
        } else {
            let current = this.root;
            let parent = null;

            while(1) {
                parent = current;
                if(data < current.data) {

                    current = current.left;
                    if(current === null) {
                        parent.left = node;
                        break;
                    }
                } else {

                    current = current.right;
                    if(current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }

        return this;
    }

    // 中序遍歷
    ascOrder (node) {
        if(node !== null) {
            this.ascOrder(node.left);
            node.output();
            this.ascOrder(node.right);
        }
    }

    // 先序遍歷
    rootOrder (node) {
        if(node !== null) {
            node.output();
            this.rootOrder(node.left);
            this.rootOrder(node.right);
        }
    }

    // 后序遍歷
    leafOrder (node) {
        if(node !== null) {
            this.leafOrder(node.left);
            this.leafOrder(node.right);
            node.output();
        }
    }

    // 執(zhí)行路徑的 action: left or right
    action (path) {
        let node = this.root;

        while(node[path] !== null) {
            node = node[path];
        }

        return node;
    }

    // 最小值
    min () {
        return this.action("left");
    }

    // 最大值
    max () {
        return this.action("right");
    }

    // 查找固定值
    find (data) {
        let node = this.root;

        while(node !== null) {
            if(data === node.data) {
                return node;
            } else if(data < node.data) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }
}

最后我在 Node 環(huán)境下測試，所以導出一下 Tree 類:

module.exports = Tree;

對于每一種排序后的結(jié)果是不一樣的，可以用圖形來表示一下：

中序遍歷的過程：

先序遍歷的過程：

后序遍歷的過程：

其實看圖是最直觀的，其實算法這玩意最好的就是能夠體會思想，然后根據(jù)實際的場景進行映射建立數(shù)據(jù)結(jié)構(gòu)模型，以最優(yōu)或更平衡的去解決問題。

測試代碼如下：

const Tree = require("./binTree");

const log = s => console.log(s);

const tree = new Tree();
[23, 45, 16, 37, 3, 99, 22].forEach(n => tree.insert(n));

log("中-排序：");
tree.ascOrder(tree.root);

log("先-排序：");
tree.rootOrder(tree.root);

log("后-排序：");
tree.leafOrder(tree.root);

console.log("=====================");

log("最小值：");
log( tree.min() );

log("最大值：");
log( tree.max() );

log("查找 3：");
log( tree.find(3) );

log("查找 11：");
log( tree.find(11) );

終端跑的結(jié)果如下：