国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

二叉樹簡單兩三下

lwx12525 / 794人閱讀

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

前言

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

簡單介紹下?

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

樹的常見術語有幾個:

根節點

子節點

葉子節點

子樹

路徑

鍵(這里是抽象主要的數據)

二叉樹:

子節點不超過兩個

左節點

右節點

如果具備查找特性:

較小值在左,較大值在右

這里準備一組值來構建樹:

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

然后我需要構建的樹的成品是:

具體實現

首先需要構造一個節點對象,來表示節點這一個描述元素

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: 節點的鍵

left: 左節點

right: 右節點

getData: 獲取鍵

output: 輔助輸出函數

樹的對象以及樹的操作

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

    // 插入節點
    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();
        }
    }

    // 執行路徑的 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 環境下測試,所以導出一下 Tree 類:

module.exports = Tree;

對于每一種排序后的結果是不一樣的,可以用圖形來表示一下:

中序遍歷的過程:

先序遍歷的過程:

后序遍歷的過程:

其實看圖是最直觀的,其實算法這玩意最好的就是能夠體會思想,然后根據實際的場景進行映射建立數據結構模型,以最優或更平衡的去解決問題。

測試代碼如下:

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) );

終端跑的結果如下:

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/91258.html

相關文章

  • 叉樹就是這么簡單

    前言 只有光頭才能變強。 文本已收錄至我的GitHub倉庫,歡迎Star:https://github.com/ZhongFuCheng3y/3y 一、二叉樹就是這么簡單 本文撇開一些非常苦澀、難以理解的概念來講講二叉樹,僅入門觀看(或復習).... 首先,我們來講講什么是樹: 樹是一種非線性的數據結構,相對于線性的數據結構(鏈表、數組)而言,樹的平均運行時間更短(往往與樹相關的排序時間復雜度都...

    Cruise_Chan 評論0 收藏0
  • 叉樹那些事兒

    摘要:大家在聊到二叉樹的時候,總會離不開鏈表。受限線性表主要包括棧和隊列,受限表示對結點的操作受限制。存儲結構線性表主要由順序表示或鏈式表示。鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素,稱為線性表的鏈式存儲結構。 大家在聊到二叉樹的時候,總會離不開鏈表。這里先帶大家一起了解一些基本概念。 線性表 概念 線性表是最基本、最簡單、也是最常用的一種數據結構。 線性表中數據元素之間的關...

    Little_XM 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<