理論基礎
二叉樹種類
滿二叉樹
如果一棵二叉樹只有度為0的結點和度為2的結點，并且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。
如圖所示：
image.png
這棵二叉樹為滿二叉樹，也可以說深度為k，有2^k-1個節(jié)點的二叉樹。
完全二叉樹
除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。滿二叉樹一定是完全二叉樹。
image.png
二叉搜索樹
前面介紹的樹，都沒有數(shù)值的，而二叉搜索樹是有數(shù)值的了，二叉搜索樹是一個有序樹。
- 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
-
它的左、右子樹也分別為二叉排序樹
下面這兩棵樹都是搜索樹
image.png
平衡二叉搜索樹
平衡二叉搜索樹：又被稱為AVL（Adelson-Velsky and Landis）樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
image.png
存儲方式
鏈式存儲
通過指針把分布在各個地址的節(jié)點串聯(lián)一起。一般用這個。
image.png
線性存儲
順序存儲的元素在內存是連續(xù)分布的
image.png
如果父節(jié)點的數(shù)組下標是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
遍歷方式
節(jié)點類型
- 根節(jié)點：樹的最頂端的節(jié)點。（根節(jié)點只有一個）
- 子節(jié)點：除根節(jié)點之外，并且本身下面還連接有節(jié)點的節(jié)點。
- 葉子結點：自己下面不再連接有節(jié)點的節(jié)點（即末端），稱為葉子節(jié)點（又稱為終端結點）。度為0
根節(jié)點、子節(jié)點、葉子節(jié)點是什么？-CSDN博客
二叉樹主要有兩種遍歷方式：
1、深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點再往回走。
2、廣度優(yōu)先遍歷：一層一層的去遍歷。
這兩種遍歷是圖論中最基本的兩種遍歷方式。
那么從深度優(yōu)先遍歷和廣度優(yōu)先遍歷進一步拓展，才有如下遍歷方式：
- 深度優(yōu)先遍歷，一般可用棧
** 前序遍歷（遞歸法，迭代法）
** 中序遍歷（遞歸法，迭代法）
** 后序遍歷（遞歸法，迭代法） - 廣度優(yōu)先遍歷，一般用隊列
** 層次遍歷（迭代法）
這里前中后，其實指的就是中間節(jié)點的遍歷順序，只要大家記住 前中后序指的就是中間節(jié)點的位置就可以了。
image.png
二叉樹定義
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
144. 二叉樹的前序遍歷 - 力扣（LeetCode）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def PreOrder(self, root: TreeNode, res):
if root is None:
return
res.append(root.val)
self.PreOrder(root.left, res)
self.PreOrder(root.right, res)
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.PreOrder(root, res)
return res
145. 二叉樹的后序遍歷 - 力扣（LeetCode）
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def PostOredr(self, root: TreeNode, res):
if root is None:
return
self.PostOredr(root.left, res)
self.PostOredr(root.right, res)
res.append(root.val)
return res
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.PostOredr(root,res)
return res
94. 二叉樹的中序遍歷 - 力扣（LeetCode）
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def InOredr(self, root:TreeNode, res):
if root is None:
return []
self.InOredr(root.left, res)
res.append(root.val)
self.InOredr(root.right, res)
return res
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.InOredr(root, res)
return res
