摘要:假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實(shí)現(xiàn)二叉樹節(jié)點(diǎn)定義來(lái)源驗(yàn)證二叉搜索樹解析
這是第六周的練習(xí)題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。
下面是之前分享的鏈接:
1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack)
2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList)
3.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Queue)
4.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Set)
5.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Dictionary 和 HashTable)
歡迎關(guān)注我的 個(gè)人主頁(yè) && 個(gè)人博客 && 個(gè)人知識(shí)庫(kù) && 微信公眾號(hào)“前端自習(xí)課”
本周練習(xí)內(nèi)容:數(shù)據(jù)結(jié)構(gòu)與算法 —— Tree
這些都是數(shù)據(jù)結(jié)構(gòu)與算法,一部分方法是團(tuán)隊(duì)其他成員實(shí)現(xiàn)的,一部分我自己做的,有什么其他實(shí)現(xiàn)方法或錯(cuò)誤,歡迎各位大佬指點(diǎn),感謝。
一、什么是樹?1.樹有什么特點(diǎn),什么是二叉樹和二叉搜索樹(BST: Binary Search Tree)?
2.生活中常見的例子有哪些?
解析:
樹有什么特點(diǎn),什么是二叉樹和二叉搜索樹:
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),以分層方式存儲(chǔ)數(shù)據(jù),用來(lái)表示有層級(jí)關(guān)系的數(shù)據(jù)。
每棵樹至多只有一個(gè)根結(jié)點(diǎn),根結(jié)點(diǎn)會(huì)有很多子節(jié)點(diǎn),每個(gè)子節(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)。
父結(jié)點(diǎn)和子節(jié)點(diǎn)是相對(duì)的。
生活中的例子:
如:家譜、公司組織架構(gòu)圖。
二、請(qǐng)實(shí)現(xiàn)二叉搜索樹(BST),并實(shí)現(xiàn)以下方法:insert(key):向樹中插入一個(gè)新的鍵;
search(key):樹中查找一個(gè)鍵,如果節(jié)點(diǎn)存在返回true,不存在返回false;
min():返回樹中最小的值/鍵;
max():返回樹中最大的值/鍵;
remove(key):移除某個(gè)鍵;
提示:所謂的鍵對(duì)應(yīng)于之前章節(jié)所學(xué)的節(jié)點(diǎn)(Node)
class Node { constructor(key){ this.key = key this.left = null this.right = null } } class BST { constructor(){ this.root = null } /** * 插入一個(gè)節(jié)點(diǎn) * @param {*} node 插入的位置節(jié)點(diǎn) * @param {*} newNode 插入的節(jié)點(diǎn) */ 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) } /** * 最小值的節(jié)點(diǎn) */ min (){ let node = this.root if(node === null) return null while(node && node.left !== null){ node = node.left } return node.key } /** * 最大值的節(jié)點(diǎn) */ max (){ let node = this.root if(node === null) return null while(node && node.right !== null){ node = node.right } return node.key } /** * 找到最小節(jié)點(diǎn) * @param {*} node */ findMinNode (node){ if(node === null) return null while(node && node.left !== null){ node = node.left } return node } /** * 刪除一個(gè)節(jié)點(diǎn) * @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.葉節(jié)點(diǎn) if(node.left === null && node.right === null){ node = null return node } // 2.只有一個(gè)子節(jié)點(diǎn) if(node.left === null){ node = node.right return node }else if(node.right === null){ node = node.left } // 3.有兩個(gè)子節(jié)點(diǎn) let curNode = this.findMinNode(node.right) node.key = curNode.key node.right = this.removeNode(node.right, curNode.key) return node } } /** * 刪除一個(gè)節(jié)點(diǎn) * @param {*} key */ remove (key){ if(this.root === null) return null this.root = this.removeNode(this.root, key) } }三、基于題二實(shí)現(xiàn)二叉搜索樹擴(kuò)展以下方法:
preOrderTraverse(): 通過(guò)先序遍歷方式遍歷所有節(jié)點(diǎn);
inOrderTraverse(): 通過(guò)中序遍歷方式遍歷所有節(jié)點(diǎn);
postOrderTraverse(): 通過(guò)后序遍歷方式遍歷所有節(jié)點(diǎn);
提示:
先序:先訪問根節(jié)點(diǎn),然后以同樣方式訪問左子樹和右子樹;(根==>左==>右)
輸出 =》 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
中序:先訪問左子樹,再訪問根節(jié)點(diǎn),最后訪問右字?jǐn)?shù);以升序訪問所有節(jié)點(diǎn);(左==>根==>右)
輸出 =》 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
后序:先訪問葉子節(jié)點(diǎn),從左子樹到右子樹,再到根節(jié)點(diǎn)。(左==>右==>根)
輸出 =》 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) }四、請(qǐng)實(shí)現(xiàn)從上往下打印二叉樹
給定的二叉樹為:[3, 9 , 20, null, null, 15, 7]
3 / 9 20 / 15 7
請(qǐng)實(shí)現(xiàn)一個(gè) printLevelOrder 方法,輸出以下結(jié)果:
[ [3], [9, 20], [15, 7] ]
來(lái)源: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]) } }五、給定一個(gè)二叉樹,判斷其是否是一個(gè)有效的二叉搜索樹。
假設(shè)一個(gè)二叉搜索樹具有如下特征:
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入: 2 / 1 3 輸出: true
示例 2:
輸入: 5 / 1 4 / 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]。 根節(jié)點(diǎn)的值為 5 ,但是其右子節(jié)點(diǎn)值為 4 。
代碼實(shí)現(xiàn):
/** * 二叉樹節(jié)點(diǎn)定義 */ function TreeNode(val) { this.val = val; this.left = this.right = null; } /** - @param {TreeNode} root - @return {boolean} */ function isValidBST(root) {};
來(lái)源:99.驗(yàn)證二叉搜索樹
解析:
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 };
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/109680.html
摘要:假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實(shí)現(xiàn)二叉樹節(jié)點(diǎn)定義來(lái)源驗(yàn)證二叉搜索樹解析這是第六周的練習(xí)題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 下面是之前分享的鏈接: 1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack) 2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList) 3...
摘要:什么是散列表和散列函數(shù)哈希表,也叫散列表,是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。根據(jù)鍵值從散列表中移除值。請(qǐng)實(shí)現(xiàn)散列表將和存在一個(gè)對(duì)象中即可定義一個(gè)包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習(xí)題,上周忘記發(fā)啦,這周是復(fù)習(xí) Dictionary 和 Hash...
摘要:什么是散列表和散列函數(shù)哈希表,也叫散列表,是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。將字典的所有鍵名以數(shù)組的形式返回。根據(jù)鍵值從散列表中移除值。這是第五周的練習(xí)題,上周忘記發(fā)啦,這周是復(fù)習(xí) Dictionary 和 HashTable。 下面是之前分享的鏈接: 1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack) 2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList) 3.每周一練 之 數(shù)據(jù)結(jié)構(gòu)...
摘要:一集合是什么與它相關(guān)數(shù)學(xué)概念有哪些解題集合定義集合是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)。集合中的元素稱為成員,集合最重要的兩個(gè)特點(diǎn)集合中的成員是無(wú)序集合中不存在相同成員即無(wú)序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習(xí)題,五一放假結(jié)束,該收拾好狀態(tài)啦。 下面是之前分享的鏈接: ...
摘要:與堆棧區(qū)別隊(duì)列的操作方式和堆棧類似,唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。移除隊(duì)列的第一項(xiàng),并返回被移除的元素。三使用隊(duì)列計(jì)算斐波那契數(shù)列的第項(xiàng)。前兩項(xiàng)固定為,后面的項(xiàng)為前兩項(xiàng)之和,依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第二周的練習(xí)題,這里補(bǔ)充下咯,五一節(jié)馬上就要到了,自己的...
閱讀 1062·2021-11-24 10:27
閱讀 3337·2021-11-18 10:02
閱讀 2396·2021-11-16 11:45
閱讀 3161·2021-11-15 18:10
閱讀 822·2021-09-22 15:23
閱讀 1529·2019-08-30 15:53
閱讀 3021·2019-08-30 13:20
閱讀 1666·2019-08-30 12:53