🧑‍💻JavaScript算法與數據結構-HowieCong

務必要熟悉JavaScript使用再來學！

一、樹是什麼？

• 數據結構中的樹，對於現實世界中的樹簡化——樹根抽象為“根節點”，樹枝抽象為“邊”，樹枝的兩個端點抽象為“結點”，樹葉抽象為“葉子結點”

• 計算機中的樹如下：

二、樹的重點

• 樹的層次計算規則：根結點所在的那一層為第一層，其子節點為第二層，以此類推
• 結點和樹的高度計算規則：葉子結點高度為1，每向上一層高度就加1，逐層向上累加至目標結點時，所得到的值就是目標結點的高度。樹種結點的最大高度，為“樹的高度”
• 度的概念：一個結點開叉出去多少個子樹，被稱為結點的“度”，比如如上圖所示，根節點的“度”就是3
• 葉子結點：葉子結點就是度為0的結點，上圖所示，最後一層的結點的度全部為0，所以這一層的結點都是葉子節點

三、二叉樹是什麼？

• 二叉樹的要求

  • 它可以沒有根節點，作為一顆空樹存在
  • 如果不是空樹，那麼必須由根結點、子樹和右子樹組成，且左右子樹都是二叉樹

  

  • 二叉樹不能被簡單定義為每個結點的度都是2的樹，普通的樹並不會區分左子樹和右子樹，但在二叉樹中，左右子樹的位置是嚴格約定的、不能交互的，如上圖，也就是B和C、D、E、F和G是不能交換的

四、二叉樹的實現

• 在JavaScript中，二叉樹使用對象的定義。結構分為三部分：

  • 數據域
  • 左側子結點（左子樹根結點）的引用
  • 右側子結點（右子樹根結點）的引用
• 在定義二叉樹構造函數時，需要把左側子結點和右側子結點都預製為空

//function TreeNode(val){
    this.val = val;
    this.left = this.right =null;
}

• 當創建一個二叉樹結點時，直接調用構造函數、傳入數據域的值就行

const node = new TreeNode(1)

• 就可以得到值為1的二叉樹結點，結構如下：

• 以這個結點為根節點，可以通過給left/right賦值拓展其子樹信息，延展出一棵二叉樹，如下：

❓其他

1. 疑問與作者HowieCong聲明

• 如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
• 若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
• 聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！

2. 作者社交媒體/郵箱-HowieCong

• HowieCong Social Meida : Wechat|Instagram|Feishu|Juejin|Segmentfault...
• HowieCong Mail : mailto:howiecong@163.com