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

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

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

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

根節(jié)點(diǎn)

子節(jié)點(diǎn)

葉子節(jié)點(diǎn)

層

子樹

路徑

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

二叉樹：

子節(jié)點(diǎn)不超過兩個(gè)

左節(jié)點(diǎn)

右節(jié)點(diǎn)

如果具備查找特性：

較小值在左，較大值在右

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

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

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

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

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é)點(diǎn)的鍵

left: 左節(jié)點(diǎn)

right: 右節(jié)點(diǎn)

getData: 獲取鍵

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

樹的對(duì)象以及樹的操作

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

    // 插入節(jié)點(diǎn)
    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)境下測(cè)試，所以導(dǎo)出一下 Tree 類:

module.exports = Tree;

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

中序遍歷的過程：

先序遍歷的過程：

后序遍歷的過程：

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

測(cè)試代碼如下：

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é)果如下：