概述
- 前言
- 什么是樹
- 什么是二叉樹
- 深度優(yōu)先
- 廣度優(yōu)先
- 后記
前言
前面說到算法被虐了，這回我要好好把它啃下來。哪里跌倒就要從哪里站起來。這是我復(fù)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)時(shí)的小筆記，這里就 po 出來，給大家也復(fù)習(xí)一下舊的知識點(diǎn)，查缺補(bǔ)漏。如果我的文章對你有幫助，歡迎關(guān)注、點(diǎn)贊、轉(zhuǎn)發(fā)，這樣我會更有動(dòng)力做原創(chuàng)分享。
什么是樹
在計(jì)算器科學(xué)中，樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。
樹的特點(diǎn)
- 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；
- 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
- 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹
術(shù)語
- 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；
- 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
- 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；
- 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)；
- 父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
- 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
- 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
- 深度：對于任意節(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長，根的深度為0；
- 高度：對于任意節(jié)點(diǎn)n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0；
- 堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
- 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
- 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
- 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
什么是二叉樹
二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹；
完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹；
滿二叉樹：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹；
深度優(yōu)先
深度優(yōu)先遍歷即是先按深度來遍歷二叉樹，包括：
前序遍歷
遍歷順序 --> 根節(jié)點(diǎn) -> 左子樹 -> 右子樹
中序遍歷
遍歷順序--> 左子樹 -> 根節(jié)點(diǎn) -> 右子樹
后序遍歷
遍歷順序--> 左子樹 -> 右子樹 -> 根節(jié)點(diǎn)
首先，定義 TreeNode：
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子樹
self.right = right # 右子樹
實(shí)例化一個(gè) TreeNode：
node1 = TreeNode("A",
TreeNode("B",
TreeNode("D"),
TreeNode("E")
),
TreeNode("C",
TreeNode("F"),
TreeNode("G")
)
)
前序遍歷
def preTraverse(root):
if root is None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
運(yùn)行結(jié)果：
A
B
D
E
C
F
G
中序遍歷
def midTraverse(root):
if root is None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
運(yùn)行結(jié)果：
D
B
E
A
F
C
G
后序遍歷
def afterTraverse(root):
if root is None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
運(yùn)行結(jié)果：
D
E
B
F
G
C
A
廣度優(yōu)先
廣度優(yōu)先遍歷即是層次遍歷，按一層一層地遍歷。
def levelOrder(root):
# write your code here
res = []
# 如果根節(jié)點(diǎn)為空，則返回空列表
if root is None:
return res
# 模擬一個(gè)隊(duì)列儲存節(jié)點(diǎn)
q = []
# 首先將根節(jié)點(diǎn)入隊(duì)
q.append(root)
# 列表為空時(shí)，循環(huán)終止
while len(q) != 0:
length = len(q)
for i in range(length):
# 將同層節(jié)點(diǎn)依次出隊(duì)
r = q.pop(0)
if r.left is not None:
# 非空左孩子入隊(duì)
q.append(r.left)
if r.right is not None:
# 非空右孩子入隊(duì)
q.append(r.right)
res.append(r.value)
print(r.value)
return res
運(yùn)行結(jié)果：
A
B
C
D
E
F
G
后記
這次復(fù)習(xí)先是到這里了。這里嘮叨一下，數(shù)據(jù)結(jié)構(gòu)與算很重要，很多東西的實(shí)現(xiàn)都少不了數(shù)據(jù)結(jié)構(gòu)與算法，就如 mysql 的實(shí)現(xiàn)就用到了 B+ 樹，如果我們懂其中的原理，對數(shù)據(jù)庫性能優(yōu)化會有很大的幫助。還有一點(diǎn)比較重要的是，大廠的面試肯定少不了算法與數(shù)據(jù)結(jié)構(gòu)。想進(jìn)大廠？還是乖乖滴學(xué)通算法。
本篇文章首發(fā)于公眾號「zone7」，關(guān)注公眾號獲取最新推文，后臺回復(fù)【國慶指數(shù)】獲取源碼。
