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

資訊專欄INFORMATION COLUMN

每周一練 之 數據結構與算法(Tree)

fizz / 2129人閱讀

摘要:假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析

這是第六周的練習題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。

下面是之前分享的鏈接:

1.每周一練 之 數據結構與算法(Stack)

2.每周一練 之 數據結構與算法(LinkedList)

3.每周一練 之 數據結構與算法(Queue)

4.每周一練 之 數據結構與算法(Set)

5.每周一練 之 數據結構與算法(Dictionary 和 HashTable)

歡迎關注我的 個人主頁 && 個人博客 && 個人知識庫 && 微信公眾號“前端自習課”

本周練習內容:數據結構與算法 —— Tree

這些都是數據結構與算法,一部分方法是團隊其他成員實現的,一部分我自己做的,有什么其他實現方法或錯誤,歡迎各位大佬指點,感謝。

一、什么是樹?

1.樹有什么特點,什么是二叉樹和二叉搜索樹(BST: Binary Search Tree)? 2.生活中常見的例子有哪些?


解析:

    樹有什么特點,什么是二叉樹和二叉搜索樹:

是一種非線性的數據結構,以分層方式存儲數據,用來表示有層級關系的數據

每棵樹至多只有一個根結點根結點會有很多子節點,每個子節點只有一個父結點

父結點子節點是相對的。

    生活中的例子:
    如:家譜、公司組織架構圖。

二、請實現二叉搜索樹(BST),并實現以下方法:

insert(key):向樹中插入一個新的鍵;

search(key):樹中查找一個鍵,如果節點存在返回true,不存在返回false;

min():返回樹中最小的值/鍵;

max():返回樹中最大的值/鍵;

remove(key):移除某個鍵;

提示:所謂的鍵對應于之前章節所學的節點(Node)

class Node {
    constructor(key){
        this.key = key
        this.left = null
        this.right = null
    }
}
class BST {
    constructor(){
        this.root = null
    }
    /**
     * 插入一個節點
     * @param {*} node 插入的位置節點
     * @param {*} newNode 插入的節點
     */
    insertNode (node, newNode){
        if(newNode.key < node.key){
            if(node.left === null && node.right === null){
                node.left = newNode
            }else if(node.left !== null && node.right === null){
                node.right = newNode
            }else{
                this.insertNode(node.left, newNode)
            }
        }else{
            if(node.left === null && node.right === null){
                node.left = newNode
            }else if(node.left !== null && node.right === null){
                node.right = newNode
            }else{
                this.insertNode(node.right, newNode)
            }
        }
    }
    /**
     * 插入操作
     * @param {*} key 
     */
    insert (key){
        let newNode = new Node(key)
        if(this.root === null){
            this.root = newNode
        }else{
            this.insertNode(this.root, newNode)
        }
    }
    searchNode (node, key){
        if(node === null) return false
        if(key < node.key){
            return this.searchNode(node.left, key)
        }else if(key > node.key){
            return this.searchNode(node.right, key)
        }else{
            return true
        }
    }
    /**
     * 搜索操作
     * @param {*} key 
     */
    search (key){
        return this.searchNode(this.root, key)
    }
    /**
     * 最小值的節點
     */
    min (){
        let node = this.root
        if(node === null) return null
        while(node && node.left !== null){
            node = node.left
        }
        return node.key
    }
    /**
     * 最大值的節點
     */
    max (){
        let node = this.root
        if(node === null) return null
        while(node && node.right !== null){
            node = node.right
        }
        return node.key
    }
    /**
     * 找到最小節點
     * @param {*} node 
     */
    findMinNode (node){
        if(node === null) return null
        while(node && node.left !== null){
            node = node.left
        }   
        return node
    }
    /**
     * 刪除一個節點
     * @param {*} node 
     * @param {*} key 
     */
    removeNode (node, key){
        if(node === null) return null
        if(key < node.key){
            node.left = this.removeNode(node.left, key)
            return node
        }else if(key > node.key){
            node.right = this.removeNode(node.right, key)
            return node
        }else{
            // 1.葉節點
            if(node.left === null && node.right === null){
                node = null
                return node
            }
            // 2.只有一個子節點
            if(node.left === null){
                node = node.right
                return node
            }else if(node.right === null){
                node = node.left
            }
            // 3.有兩個子節點
            let curNode = this.findMinNode(node.right)
            node.key = curNode.key
            node.right = this.removeNode(node.right, curNode.key)
            return node
        }
    }
    /**
     * 刪除一個節點
     * @param {*} key 
     */
    remove (key){
        if(this.root === null) return null
        this.root = this.removeNode(this.root, key)
    }
}

三、基于題二實現二叉搜索樹擴展以下方法:

preOrderTraverse(): 通過先序遍歷方式遍歷所有節點;

inOrderTraverse(): 通過中序遍歷方式遍歷所有節點;

postOrderTraverse(): 通過后序遍歷方式遍歷所有節點;

提示:

先序:先訪問根節點,然后以同樣方式訪問左子樹和右子樹;(根==>左==>右)

輸出 =》 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

中序:先訪問左子樹,再訪問根節點,最后訪問右字數;以升序訪問所有節點;(左==>根==>右)

輸出 =》 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

后序:先訪問葉子節點,從左子樹到右子樹,再到根節點。(左==>右==>根)

輸出 =》 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11


解析:

// 1. 先序
BST.prototype.preOrderTraverseNode = function(node, callback){
    if(node !== null){
        callback(node.key)
        this.preOrderTraverseNode(node.left, callback)
        this.preOrderTraverseNode(node.right, callback)
    }
}
BST.prototype.preOrderTraverse = function(callback){
    this.preOrderTraverseNode(this.root, callback)
}

// 2. 中序
BST.prototype.inOrderTraverseNode = function(node, callback){
    if(node !== null){
        this.inOrderTraverseNode(node.left, callback)
        callback(node.key)
        this.inOrderTraverseNode(node.right, callback)
    }
}
BST.prototype.inOrderTraverse = function(callback){
    this.inOrderTraverseNode(this.root, callback)
}

// 3. 后序
BST.prototype.postOrderTraverseNode = function(node, callback){
    if(node !== null){
        this.postOrderTraverseNode(node.left, callback)
        this.postOrderTraverseNode(node.right, callback)
        callback(node.key)
    }
}
BST.prototype.postOrderTraverse = function(callback){
    this.postOrderTraverseNode(this.root, callback)
}

四、請實現從上往下打印二叉樹

給定的二叉樹為:[3, 9 , 20, null, null, 15, 7]

    3
   / 
  9  20
     / 
    15  7

請實現一個 printLevelOrder 方法,輸出以下結果:

[
  [3],
  [9, 20],
  [15, 7]
]

來源:102.二叉樹的層次遍歷
解析:

方法一:

BST.prototype.printLevelOrder = function (root, arr = [], i = 0){
    if (root && (root.key || root.key === 0)) {
      !arr[i] && (arr[i] = [])
      arr[i].push(root.key)
      i++
      root.left && this.printLevelOrder(root.left, arr, i)
      root.right && this.printLevelOrder(root.right, arr, i)
    }
    return arr
}

方法二:

BST.prototype.printLevelOrder = function (){
    if(this.root === null) return []
    let result = [], queue = [this.root]
    while(true){
        let len = queue.length, arr = []
        while(len > 0){
            console.log(queue)
            let node = queue.shift()
            len -= 1
            arr.push(node.key)
            if(node.left !== null) queue.push(node.left)
            if(node.right !== null) queue.push(node.right)
        }
        if(arr.length === 0) return result
        result.push([...arr])
    }
}

五、給定一個二叉樹,判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特征:

節點的左子樹只包含小于當前節點的數。

節點的右子樹只包含大于當前節點的數。

所有左子樹和右子樹自身必須也是二叉搜索樹。

示例 1:

輸入:
    2
   / 
  1   3
輸出: true

示例 2:

輸入:
    5
   / 
  1   4
     / 
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節點的值為 5 ,但是其右子節點值為 4 。

代碼實現:

/**
 * 二叉樹節點定義
 */
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
- @param {TreeNode} root
- @return {boolean}
*/
function isValidBST(root) {};

來源:99.驗證二叉搜索樹
解析:

function isValidBST(root) {
    let arr = []
    function inOrderTraverse(node){
        if(node === null) return;
        node.left && inOrderTraverse(node.left);
        arr.push(node.val);
        node.right && inOrderTraverse(node.right);
    }
    inOrderTraverse(root)
    for(let i = 0; i < arr.length - 1; i++){
        if(arr[i] >= arr[i+1]) return false
    }
    return true
};

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

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

相關文章

  • 周一 數據結構算法Tree

    摘要:假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 ...

    zhonghanwen 評論0 收藏0
  • 周一 數據結構算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數哈希表,也叫散列表,是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題,上周忘記發啦,這周是復習 Dictionary 和 Hash...

    eternalshallow 評論0 收藏0
  • 周一 數據結構算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數哈希表,也叫散列表,是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。這是第五周的練習題,上周忘記發啦,這周是復習 Dictionary 和 HashTable。 下面是之前分享的鏈接: 1.每周一練 之 數據結構與算法(Stack) 2.每周一練 之 數據結構與算法(LinkedList) 3.每周一練 之 數據結構...

    ingood 評論0 收藏0
  • 周一 數據結構算法(Set)

    摘要:一集合是什么與它相關數學概念有哪些解題集合定義集合是一種包含不同元素的數據結構。集合中的元素稱為成員,集合最重要的兩個特點集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習題,五一放假結束,該收拾好狀態啦。 下面是之前分享的鏈接: ...

    silvertheo 評論0 收藏0
  • 周一 數據結構算法(Queue)

    摘要:與堆棧區別隊列的操作方式和堆棧類似,唯一的區別在于隊列只允許新數據在后端進行添加。移除隊列的第一項,并返回被移除的元素。三使用隊列計算斐波那契數列的第項。前兩項固定為,后面的項為前兩項之和,依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第二周的練習題,這里補充下咯,五一節馬上就要到了,自己的...

    anquan 評論0 收藏0

發表評論

0條評論

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