毎週月曜日に練習するデータ構造とアルゴリズム(Tree)

8499 ワード
データ構造とアルゴリズム javascript
これは第六週の練習問題です.最近残業が多いです.先週は主にGraphQL入門教程を完成しました.興味のある仲間は見てもいいです.
以下は前に共有したリンクです.
  • 1.毎週月曜日に行われるデータ構造とアルゴリズム(Stck)
  • .毎週月曜日に行われるデータ構造とアルゴリズム(LinkdList)
  • 3.毎週月曜日に行われるデータ構造とアルゴリズム(Queue)
  • .毎週月曜日に行われるデータ構造とアルゴリズム(Set)
  • .毎週月曜日に行われるデータ構造とアルゴリズム
    • 私のホームページ&個人ブログ&個人知識庫&WeChat公衆番号「フロントエンド自習課」に注目してください.
    今週の練習内容:データ構造とアルゴリズム――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 10 15 12 14 20 25
  • の中で、まず左の子樹を訪問して、ルートノードを訪問して、最後に右の字数を訪問します.すべてのノードに昇順でアクセスします.(左=>根=>右)
    • 出力=>3 5 6 7 7 9 10 12 13 15 18 25
  • 後の順序:まず葉っぱノードにアクセスし、左の子樹から右の子樹まで、ルートノードに行く.(左=>右=>根)
    • 出力=>3 6 5 8 10 9 9月12日13日18時20分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.二叉樹の階層巡回解析:
  • 方法1:
    • 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
}
  • 方法2:
    • 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
};
    Node.js Pathモジュール学習