日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

[[425982]]

本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比劍閣網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式劍閣網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋劍閣地區(qū)。費(fèi)用合理售后完善，10余年實(shí)體公司更值得信賴。

一、是什么

在計(jì)算機(jī)領(lǐng)域，樹(shù)形數(shù)據(jù)結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，可以表示數(shù)據(jù)之間一對(duì)多的關(guān)系。以樹(shù)與二叉樹(shù)最為常用，直觀看來(lái)，樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)

二叉樹(shù)滿足以下兩個(gè)條件：

• 本身是有序樹(shù)
• 樹(shù)中包含的各個(gè)節(jié)點(diǎn)的度不能超過(guò) 2，即只能是 0、1 或者 2

如下圖，左側(cè)的為二叉樹(shù)，而右側(cè)的因?yàn)轭^結(jié)點(diǎn)的子結(jié)點(diǎn)超過(guò)2，因此不屬于二叉樹(shù)：

同時(shí)，二叉樹(shù)可以繼續(xù)進(jìn)行分類，分成了滿二叉樹(shù)和完成二叉樹(shù)：

滿二叉樹(shù)：如果二叉樹(shù)中除了葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度都為 2

完成二叉樹(shù)：如果二叉樹(shù)中除去最后一層節(jié)點(diǎn)為滿二叉樹(shù)，且最后一層的結(jié)點(diǎn)依次從左到右分布

二、操作

關(guān)于二叉樹(shù)的遍歷，常見(jiàn)的有：

• 前序遍歷
• 中序遍歷
• 后序遍歷
• 層序遍歷

前序遍歷

前序遍歷的實(shí)現(xiàn)思想是：

• 訪問(wèn)根節(jié)點(diǎn)
• 訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)
• 若當(dāng)前節(jié)點(diǎn)無(wú)左子樹(shù)，則訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子

根據(jù)遍歷特性，遞歸版本用代碼表示則如下：

 
 
 
 

  
  
  
  
const preOrder = (root) => { 
  
  
  
  
  if(!root){ return } 
  
  
  
  
  console.log(root) 
  
  
  
  
  preOrder(root.left) 
  
  
  
  
  preOrder(root.right) 
  
  
  
  
} 
 
 
 
 

如果不使用遞歸版本，可以借助棧先進(jìn)后出的特性實(shí)現(xiàn)，先將根節(jié)點(diǎn)壓入棧，再分別壓入右節(jié)點(diǎn)和左節(jié)點(diǎn)，直到棧中沒(méi)有元素，如下：

 
 
 
 

  
  
  
  
const preOrder = (root) => { 
  
  
  
  
  if(!root){ return } 
  
  
  
  
  const stack = [root] 
  
  
  
  
  while (stack.length) { 
  
  
  
  
    const n = stack.pop() 
  
  
  
  
    console.log(n.val) 
  
  
  
  
    if (n.right) { 
  
  
  
  
      stack.push(n.right) 
  
  
  
  
    } 
  
  
  
  
    if (n.left) { 
  
  
  
  
      stack.push(n.left) 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
} 
 
 
 
 

中序遍歷

前序遍歷的實(shí)現(xiàn)思想是：

• 訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)
• 訪問(wèn)根節(jié)點(diǎn)
• 訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子

遞歸版本很好理解，用代碼表示則如下：

 
 
 
 

  
  
  
  
const inOrder = (root) => { 
  
  
  
  
  if (!root) { return } 
  
  
  
  
  inOrder(root.left) 
  
  
  
  
  console.log(root.val) 
  
  
  
  
  inOrder(root.right) 
  
  
  
  
} 
 
 
 
 

非遞歸版本也是借助棧先進(jìn)后出的特性，可以一直首先一直壓入節(jié)點(diǎn)的左元素，當(dāng)左節(jié)點(diǎn)沒(méi)有后，才開(kāi)始進(jìn)行出棧操作，壓入右節(jié)點(diǎn)，然后有依次壓入左節(jié)點(diǎn)，如下：

 
 
 
 

  
  
  
  
const inOrder = (root) => { 
  
  
  
  
  if (!root) { return } 
  
  
  
  
  const stack = [root] 
  
  
  
  
  let p = root 
  
  
  
  
  while(stack.length || p){ 
  
  
  
  
    while (p) { 
  
  
  
  
      stack.push(p) 
  
  
  
  
      p = p.left 
  
  
  
  
    } 
  
  
  
  
    const n = stack.pop() 
  
  
  
  
    console.log(n.val) 
  
  
  
  
    p = n.right 
  
  
  
  
  } 
  
  
  
  
} 
 
 
 
 

后序遍歷

前序遍歷的實(shí)現(xiàn)思想是：

• 訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)
• 訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子
• 訪問(wèn)根節(jié)點(diǎn)

遞歸版本，用代碼表示則如下：

 
 
 
 

  
  
  
  
const postOrder = (root) => { 
  
  
  
  
  if (!root) { return } 
  
  
  
  
  postOrder(root.left) 
  
  
  
  
  postOrder(root.right) 
  
  
  
  
  console.log(n.val) 
  
  
  
  
 } 
 
 
 
 

后序遍歷非遞歸版本實(shí)際跟全序遍歷是逆序關(guān)系，可以再多創(chuàng)建一個(gè)棧用來(lái)進(jìn)行輸出，如下：

 
 
 
 

  
  
  
  
const preOrder = (root) => { 
  
  
  
  
  if(!root){ return } 
  
  
  
  
  const stack = [root] 
  
  
  
  
  const outPut = [] 
  
  
  
  
  while (stack.length) { 
  
  
  
  
    const n = stack.pop() 
  
  
  
  
    outPut.push(n.val) 
  
  
  
  
    if (n.right) { 
  
  
  
  
      stack.push(n.right) 
  
  
  
  
    } 
  
  
  
  
    if (n.left) { 
  
  
  
  
      stack.push(n.left) 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
  while (outPut.length) { 
  
  
  
  
    const n = outPut.pop() 
  
  
  
  
    console.log(n.val) 
  
  
  
  
  } 
  
  
  
  
} 
 
 
 
 

層序遍歷

按照二叉樹(shù)中的層次從左到右依次遍歷每層中的結(jié)點(diǎn)

借助隊(duì)列先進(jìn)先出的特性，從樹(shù)的根結(jié)點(diǎn)開(kāi)始，依次將其左孩子和右孩子入隊(duì)。而后每次隊(duì)列中一個(gè)結(jié)點(diǎn)出隊(duì)，都將其左孩子和右孩子入隊(duì)，直到樹(shù)中所有結(jié)點(diǎn)都出隊(duì)，出隊(duì)結(jié)點(diǎn)的先后順序就是層次遍歷的最終結(jié)果

用代碼表示則如下：

 
 
 
 

  
  
  
  
const levelOrder = (root) => { 
  
  
  
  
    if (!root) { return [] } 
  
  
  
  
    const queue = [[root, 0]] 
  
  
  
  
    const res = [] 
  
  
  
  
    while (queue.length) { 
  
  
  
  
        const n = queue.shift() 
  
  
  
  
        const [node, leval] = n 
  
  
  
  
        if (!res[leval]) { 
  
  
  
  
            res[leval] = [node.val] 
  
  
  
  
        } else { 
  
  
  
  
            res[leval].push(node.val) 
  
  
  
  
        } 
  
  
  
  
        if (node.left) { queue.push([node.left, leval + 1]) } 
  
  
  
  
        if (node.right) { queue.push([node.right, leval + 1]) } 
  
  
  
  
    } 
  
  
  
  
    return res 
  
  
  
  
}; 
 
 
 
 

三、總結(jié)

樹(shù)是一個(gè)非常重要的非線性結(jié)構(gòu)，其中二叉樹(shù)以二叉樹(shù)最常見(jiàn)，二叉樹(shù)的遍歷方式可以分成前序遍歷、中序遍歷、后序遍歷

同時(shí)，二叉樹(shù)又分成了完成二叉樹(shù)和滿二叉樹(shù)

參考文獻(xiàn)

https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91

http://data.biancheng.net/view/27.html

網(wǎng)站名稱：面試官：說(shuō)說(shuō)你對(duì)樹(shù)的理解？相關(guān)的操作有哪些？
分享地址：http://m.5511xx.com/article/djsiios.html