摘要:二叉樹的層級遍歷創建一個二叉樹輸出函數先訪問左子樹,再訪問自身,再訪問右子樹先訪問自身,再訪問左子樹,再訪問右子樹先訪問左子樹,再訪問右子樹再訪問自身層級遍歷多叉樹的層級遍歷創建一個多叉樹輸出函數遞歸遍歷每個節點方法方法方法層級遍歷每
1、二叉樹的層級遍歷
創建一個二叉樹
class Binary{ constructor(data,left,right){ this.data = data this.left = left this.right = right } }
輸出函數
function Output(){ const left = new Binary(1, new Binary(2),new Binary(3)) const right = new Binary(4,new Binary(5),new Binary(6)) const root = new Binary(0,left,right) //console.log(root) /* 0 / 1 4 / / 2 3 5 6 */ inOrder(root) // 2 1 3 0 5 4 6 preOrder(root) //0 1 2 3 4 5 6 postOrder(root) //2,3,1,5,6,4,0 levelOrder(root) // 0,1,4,2,3,5,6 }()
先訪問左子樹,再訪問自身,再訪問右子樹
function inOrder(root){ if(root){ inOrder(root.left) console.log(root.data) inOrder(root.right) } }
先訪問自身,再訪問左子樹,再訪問右子樹
function preOrder(root){ if(root){ console.log(root.data) preOrder(root.left) preOrder(root.right) } }
先訪問左子樹,再訪問右子樹再訪問自身
function postOrder(root){ if(root){ postOrder(root.left) postOrder(root.right) console.log(root.data) } }
層級遍歷
function levelOrder(root){ var queue = [] queue.unshift(root) while(queue.length){ var current = queue.pop() console.log(current.data) if(current.left){ queue.unshift(current.left) } if(current.right){ queue.unshift(current.right) } } }2、多叉樹的層級遍歷
創建一個多叉樹
class TreeNode { constructor(data){ this.data = data this.children = [] } }
輸出函數
function main(){ const root = new TreeNode(0) const node2 = new TreeNode(2) cosnt node2.children.push(new TreeNode(7)) const node2.chilfren.push(new TreeNode(8)) const node2.children.push(new TreeNode(9)) const node4 = new TreeNode(4) const node3 = new TreeNode(3) const node3.children.push(new TreeNode(6)) const node3.children.push(new TreeNode(5)) root.children.push(node2) root.children.push(node4) root.children.push(node3) //console.log(root) /* 0 / | 2 4 3 / | / 7 8 9 6 5 */ traverse1(root) traverse2(traverse2[root]) var result = [] traverse3([root],result) console.log(result) levelOrder(root) }()遞歸遍歷每個節點
方法1
function traverse1(node){ if(!node){ return [] } var result = [] result.push(node.data) if(node.children){ for(var i = 0;i<=node.children.length-1;i++){ result = result.concat(traverse1(node.children[i])) } return result } }
方法2
function tranverse2(nodeList){ if(!nodeList){ return [] } var result = [] for(var i=0;i<=nodeList.length-1;i++){ result.push(nodeList[i].data) if(nodeList[i].children){ result = result.concat(traverse2(nodeList[i].children)) } } return result }
方法3
function traverse3(nodeList,result){ if(!nodeList){ return false } for(var i=0;i<=nodeList.length-1;i++){ resule.push(nodeList[i].data) if(nodeList[i].childern){ traverse3(nodeList[i].children,result) } } }層級遍歷每個節點
funciton levelOrder(root){ var queue = [] queue.unshift(root) var result = [] while(quue.length){ var current = queue.pop() result.push(current.data) for(var i =0;i<=current.children.length-1;i++){ if(current.children[i]){ queue.unshift(current.children[i]) } } } console.log(result) }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/109904.html
摘要:二叉樹和二叉查找樹一個父節點的兩個子節點分別稱為左節點和右節點。下圖展示了一顆二叉樹當考慮某種特殊的二叉樹,比如二叉查找樹時,確定子節點非常重要。實現二叉查找樹定義對象。現在可以創建一個類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。 樹是計算機科學中經常用到的一種數據結構。樹是一種非線性的數據結構,以分層的方式存儲數據。 樹被用來存儲具有層級關系的數據,比如文件系統中的文件。 ...
摘要:在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構,二叉樹具有一個唯一的根節點,也就是最上面的節點。二叉樹每個節點最多有兩個孩子,一個孩子都沒有的節點通常稱之為葉子節點,二叉樹每個節點最多有一個父親,根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
摘要:在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構,二叉樹具有一個唯一的根節點,也就是最上面的節點。二叉樹每個節點最多有兩個孩子,一個孩子都沒有的節點通常稱之為葉子節點,二叉樹每個節點最多有一個父親,根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
閱讀 1630·2023-04-25 18:19
閱讀 2078·2021-10-26 09:48
閱讀 1079·2021-10-09 09:44
閱讀 1730·2021-09-09 11:35
閱讀 3027·2019-08-30 15:54
閱讀 2021·2019-08-30 11:26
閱讀 2285·2019-08-29 17:06
閱讀 884·2019-08-29 16:38