成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

「算法與數(shù)據(jù)結(jié)構(gòu)」二叉樹之美

作者：TianTianUp
開發(fā) 前端 算法
這次梳理的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)專題中的「樹」，如果你看到樹這類數(shù)據(jù)結(jié)構(gòu)時，滿腦子頭疼，覺得它很難理解，如果是這樣子的話，那么本文可能對你或許有點幫助。

[[349809]]

 前言

這次梳理的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)專題中的「樹」，如果你看到樹這類數(shù)據(jù)結(jié)構(gòu)時，滿腦子頭疼，覺得它很難理解，如果是這樣子的話，那么本文可能對你或許有點幫助。

俗話說得好，要想掌握理解的話，我們得先了解它的概念，性質(zhì)等內(nèi)容。

圍繞以下幾個點來展開介紹樹👇

樹的基本概念

  • 基本術(shù)語
  • 樹的種類
  • 二叉樹概念
  • 二叉樹的遍歷
  • 二叉樹題目匯總

腦圖👇

 

 

 

 

樹的基本概念

樹是用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。或者你可以把它認(rèn)為是一種「抽象數(shù)據(jù)結(jié)構(gòu)」或是實現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。

那么根據(jù)維基百科給出的定義，我們似乎可以這么理解：

它是由n(n>0)個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

  • 每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點;
  • 沒有父節(jié)點的節(jié)點稱為根節(jié)點;
  • 每一個非根節(jié)點有且只有一個父節(jié)點;
  • 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹;
  • 樹里面沒有環(huán)路(cycle)

這個時候，我們就需要拿出一張圖來看👇

 

 

 

 

從圖中來看，以上的五個特點都可以很好的總結(jié)出來

  • A節(jié)點作為根節(jié)點，沒有父節(jié)點，所以是根節(jié)點。
  • 除根節(jié)點(A)外，其他的節(jié)點都有父節(jié)點，并且每個節(jié)點只有有限個子節(jié)點或無子節(jié)點。
  • 從某個節(jié)點開始，可以分為很多個子樹，舉個例子，從B節(jié)點開始，即是如此。

既然對樹有一定認(rèn)識后，我們需要了解它的一些術(shù)語。

基本術(shù)語

 


樹的基本術(shù)語

 

 

為了更加規(guī)范的總結(jié)，這里給出的描述來自于維基百科：

  • 「節(jié)點的度」：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度;
  • 「樹的度」：一棵樹中，最大的節(jié)點度稱為樹的度;
  • 「葉節(jié)點」或「終端節(jié)點」：度為零的節(jié)點;
  • 「非終端節(jié)點」或「分支節(jié)點」：度不為零的節(jié)點;
  • 「父親節(jié)點」或「父節(jié)點」：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點;
  • 「孩子節(jié)點」或「子節(jié)點」：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點;
  • 「兄弟節(jié)點」：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點;
  • 節(jié)點的「層次」：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推;
  • 「深度」：對于任意節(jié)點n,n的深度為從根到n的唯一路徑長，根的深度為0;
  • 「高度」：對于任意節(jié)點n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0;
  • 「堂兄弟節(jié)點」：父節(jié)點在同一層的節(jié)點互為堂兄弟;
  • 「節(jié)點的祖先」：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點;
  • 「子孫」：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫;
  • 「森林」：由m(m>=0)棵互不相交的樹的集合稱為森林。

可以結(jié)合上述的圖來理解這些概念，通過兩者的結(jié)合，你一定會對樹有進一步的了解的。

有以上基本概念，以及一些專業(yè)術(shù)語的掌握，接下來我們需要對樹進行一個分類，看看樹有哪些種類。

樹的種類

理解了樹的概念以及基本術(shù)語，接下來，我們需要拓展的內(nèi)容就是樹的種類。

我們可以根據(jù)維基百科的依據(jù)來作為分類的標(biāo)準(zhǔn)👇

  • 無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹;
  • 有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系，這種樹稱為有序樹;
  • 完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹;
  • 平衡二叉樹(AVL樹)：當(dāng)且僅當(dāng)任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹;
  • 排序二叉樹(英語：Binary Search Tree))：也稱二叉搜索樹、有序二叉樹;
  • 滿二叉樹：所有葉節(jié)點都在最底層的完全二叉樹;
  • 二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹;
  • 霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹;
  • B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多于兩個子樹。

既然樹的分類有這么多的話，那么我們是不是都需要一一掌握呢，我個人覺得，掌握二叉樹這種結(jié)構(gòu)就足夠了，它也是樹最簡單、應(yīng)用最廣泛的種類。

那么接下來，我們就來介紹一下二叉樹吧。

二叉樹的概念

二叉樹是一種典型的樹樹狀結(jié)構(gòu)。如它名字所描述的那樣，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)，通常子樹被稱作“左子樹”和“右子樹”。

 

 


二叉樹

 

 

從這個圖片的內(nèi)容來看，應(yīng)該很清楚的展示了二叉樹的結(jié)構(gòu)。

至于二叉樹的性質(zhì)的話，可以參考下圖，作為補充知識吧，個人覺得這個不是重點。

 

 


二叉樹的性質(zhì)

 

 

重點的話，我們需要掌握的應(yīng)該是它的遍歷方式。

二叉樹的遍歷

我們知道對于二叉樹的遍歷而言，有常見得三種遍歷方式，分別是以下三種：

  • 前序遍歷
  • 中序遍歷
  • 后續(xù)遍歷

對于任何一種遍歷方式而言，我們不僅需要掌握它的非遞歸版本，同時對于它的遞歸版本來說，更是考察一個人的算法基本功，那么接下來，我們來看看吧。

前序遍歷

點擊這里，練習(xí)二叉樹的前序遍歷

給你二叉樹的根節(jié)點 root ，返回它節(jié)點值的 「前序」 遍歷。

假設(shè)我們mock一下假數(shù)據(jù)👇

  1. 輸入: [1,null,2,3] 
  2.    1 
  3.     \ 
  4.      2 
  5.     / 
  6.    3 
  7. 輸出: [1,3,2] 

那么根據(jù)我們對前序遍歷的理解，我們可以寫出解題偽代碼👇

  1. //   TianTianUp 
  2. //   * function TreeNode(val, left, right) { 
  3. //   *     this.val = (val===undefined ? 0 : val) 
  4. //   *     this.left = (left===undefined ? null : left) 
  5. //   *     this.right = (right===undefined ? null : right) 
  6. //   * } 
  7. let inorderTraversal  = (root, arr = []) => { 
  8.   if(root) { 
  9.     inorderTraversal(root.left, arr) 
  10.     arr.push(root.value) 
  11.     inorderTraversal(root.right, arr) 
  12.   } 
  13.   return arr 
  14. } 

非遞歸版本👇

對于非遞歸的話，我們需要借助一個數(shù)據(jù)結(jié)構(gòu)去存儲它的節(jié)點，需要使用的就是棧，它的思路可以借鑒👇

  • 根節(jié)點為目標(biāo)節(jié)點，開始向它子節(jié)點遍歷
  • 1.訪問目標(biāo)節(jié)點
  • 2.左孩子入棧 -> 直至左孩子為空的節(jié)點
  • 3.節(jié)點出棧，以右孩子為目標(biāo)節(jié)點，再依次執(zhí)行1、2、3
  1. let preorderTraversal = (root, arr = []) => { 
  2.   const stack = [], res = [] 
  3.   let current = root 
  4.   while(current || stack.length > 0) { 
  5.     while (current) { 
  6.       res.push(current.val) 
  7.       stack.push(current) 
  8.       current = current.left 
  9.     } 
  10.     current = stack.pop() 
  11.     current = current.right 
  12.   } 
  13.   return res 
  14. } 

中序遍歷

給定一個二叉樹，返回它的中序 遍歷。

示例:

  • 輸入: [1,null,2,3] 1
  • 2 / 3
  • 輸出: [1,3,2]

進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎?

遞歸版本👇

  1. const inorderTraversal  = (root, arr = []) => { 
  2.   if(root) { 
  3.     inorderTraversal(root.left, arr) 
  4.     arr.push(root.val) 
  5.     inorderTraversal(root.right, arr) 
  6.   } 
  7.   return arr 
  8. } 

非遞歸版本，這里就不解釋了，跟前序遍歷一樣，思路一樣，用棧維護節(jié)點信息。

  1. const inorderTraversal = (root, arr = []) => { 
  2.   const stack = [], res = [] 
  3.   let current = root 
  4.   while(current || stack.length > 0) { 
  5.     while (current) { 
  6.       stack.push(current) 
  7.       current = current.left 
  8.     } 
  9.     current = stack.pop() 
  10.     res.push(current.val) 
  11.     current = current.right 
  12.   } 
  13.   return res 
  14. } 

后續(xù)遍歷

給定一個二叉樹，返回它的 后序 遍歷。

示例:

  • 輸入: [1,null,2,3]
  • 1
  • 2 / 3
  • 輸出: [3,2,1]

進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎?

來源：力扣(LeetCode) 鏈接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

遞歸版本👇

  1. const postorderTraversal  = (root, arr = []) => { 
  2.   if(root) { 
  3.     postorderTraversal(root.left, arr) 
  4.     postorderTraversal(root.right, arr) 
  5.     arr.push(root.val) 
  6.   } 
  7.   return arr 
  8. } 

非遞歸版本👇

其實，嗯，做完前面兩個后，會發(fā)現(xiàn)都是有套路滴~

  1. const postorderTraversal = (root, arr = []) => { 
  2.   const stack = [], res = [] 
  3.   let current = root, last = null  // last指針記錄上一個節(jié)點 
  4.   while(current || stack.length > 0) { 
  5.     while (current) { 
  6.       stack.push(current) 
  7.       current = current.left 
  8.     } 
  9.     current = stack[stack.length - 1] 
  10.     if (!current.right || current.right == last) { 
  11.       current = stack.pop() 
  12.       res.push(current.val) 
  13.       last = current 
  14.       current = null              // 繼續(xù)彈棧 
  15.     } else { 
  16.       current = current.right 
  17.     } 
  18.   } 
  19.   return res 
  20. } 

二叉樹的層次遍歷 ⭐⭐

鏈接：二叉樹的層序遍歷

給你一個二叉樹，請你返回其按 「層序遍歷」 得到的節(jié)點值。(即逐層地，從左到右訪問所有節(jié)點)。

示例：二叉樹：[3,9,20,null,null,15,7],

  • 3
  • /
  • 9 20 /
  • 15 7

返回其層次遍歷結(jié)果：

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

來源：力扣(LeetCode) 鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

遞歸版本👇

  1. const levelOrder = function(root) { 
  2.   if(!root) return [] 
  3.   let res = [] 
  4.   dfs(root, 0, res) 
  5.   return res 
  6. } 
  7.  
  8. function dfs(root, step, res){ 
  9.   if(root){ 
  10.       if(!res[step]) res[step] = [] 
  11.       res[step].push(root.val) 
  12.       dfs(root.left, step + 1, res) 
  13.       dfs(root.right, step + 1, res) 
  14.     } 
  15. } 

非遞歸版本👇

這里借助的就是隊列這個數(shù)據(jù)結(jié)構(gòu)，先進先出的機制。

  1. const levelOrder = (root) => { 
  2.   let queue = [], res = [] 
  3.   if (root) queue.push(root); 
  4.   while (queue.length) { 
  5.       let next_queue = [], 
  6.           now_res = [] 
  7.       while (queue.length) { 
  8.           root = queue.shift() 
  9.           now_res.push(root.val) 
  10.           root.left && next_queue.push(root.left) 
  11.           root.right && next_queue.push(root.right) 
  12.       } 
  13.       queue = next_queue 
  14.       res.push(now_res) 
  15.   } 
  16.   return res 
  17. } 

題目匯總

還是那句話，題目做不完的，剩下的就靠刷leetcode了，我還準(zhǔn)備了一些常見的二叉樹題集，題目的質(zhì)量還是不錯的👇

  • 二叉樹的最小深度⭐
  • 二叉樹的最大深度⭐
  • 相同的樹⭐
  • 二叉搜索樹的范圍和⭐
  • 對稱二叉樹⭐
  • 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹⭐
  • 二叉樹的層次遍歷 II⭐⭐
  • 二叉樹的最近公共祖先⭐⭐
  • 驗證二叉搜索樹⭐⭐
  • 路徑總和 III⭐⭐
  • 存在重復(fù)元素 III⭐⭐
  • 計算右側(cè)小于當(dāng)前元素的個數(shù)⭐⭐⭐

 

 

責(zé)任編輯：姜華 來源： 前端UpUp
算法與數(shù)據(jù)結(jié)構(gòu)
相關(guān)推薦

2020-09-23 18:25:40

算法二叉樹多叉樹

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建

2021-04-01 10:34:18

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2021-03-19 10:25:12

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹Tree

2021-04-20 08:37:14

數(shù)據(jù)結(jié)構(gòu)二叉樹樹

2021-03-22 09:00:22

Java數(shù)據(jù)結(jié)構(gòu)算法

2013-01-30 10:34:02

數(shù)據(jù)結(jié)構(gòu)

2020-10-30 09:56:59

Trie樹之美

2023-04-06 07:39:48

2021-01-07 08:12:47

數(shù)據(jù)結(jié)構(gòu)二叉樹樹

2021-03-29 10:13:47

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2013-07-15 16:35:55

二叉樹迭代器

2021-09-29 10:19:00

算法平衡二叉樹

2020-04-27 07:05:58

二叉樹左子樹右子樹

2021-03-22 08:23:29

LeetCode二叉樹節(jié)點

2018-03-15 08:31:57

二叉樹存儲結(jié)構(gòu)

2021-09-15 07:56:32

二叉樹層次遍歷

2021-10-12 09:25:11

二叉樹樹形結(jié)構(gòu)

2019-08-22 09:22:44

數(shù)據(jù)結(jié)構(gòu)二叉搜索樹
點贊
收藏

51CTO技術(shù)棧公眾號

主站蜘蛛池模板： 午夜精品网站 | 国产精品视频在线播放 | 野狼在线社区2017入口 | 国产精品免费高清 | 日韩a v在线免费观看 | 国产一二区免费视频 | 国产精品中文字幕一区二区三区 | 久久精品国产一区老色匹 | 国产成人99av超碰超爽 | 超级碰在线 | 老司机成人在线 | 韩日在线观看视频 | 玖玖玖在线| 国产福利91精品一区二区三区 | 一区日韩 | 日本久久综合 | 亚洲国产专区 | 操操操日日日 | 国产成人久久精品一区二区三区 | 精品欧美一区二区中文字幕视频 | 欧美中文字幕一区 | 999久久久| 亚洲精品区 | www.欧美.com | 激情91 | 男女精品久久 | 久久伊人精品 | 一片毛片 | 狠狠骚| 国产精品黄视频 | 国产欧美一区二区精品久导航 | 精品视频一区二区三区在线观看 | 日韩欧美三区 | 911影院| 精品国产乱码久久久久久闺蜜 | 中文日韩在线视频 | 欧美日韩亚洲一区二区 | www.久久精品视频 | 成人欧美一区二区三区黑人孕妇 | 成人黄视频在线观看 | 成人av电影网 |