0.前言

一直以來(lái)都在做Android開(kāi)發(fā)，感覺(jué)算法這些都不是很好，所以準(zhǔn)備從基本的數(shù)據(jù)結(jié)構(gòu)開(kāi)始學(xué)習(xí)，也相當(dāng)于自己的學(xué)習(xí)筆記吧。

1.什么是二叉樹(shù)

二叉樹(shù)是樹(shù)的一種，每個(gè)節(jié)點(diǎn)最多可具有兩個(gè)子樹(shù)，即結(jié)點(diǎn)的度最大為2（結(jié)點(diǎn)度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)）。

例：

二叉樹(shù).png

2.二叉樹(shù)的種類

2.1 斜樹(shù)

所有結(jié)點(diǎn)都只有左子樹(shù)，或者右子樹(shù)。

左斜樹(shù).png

2.2 滿二叉樹(shù)

所有的分支節(jié)點(diǎn)都具有左右節(jié)點(diǎn)。

滿二叉樹(shù).png

2.3 完全二叉樹(shù)

若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

完全二叉樹(shù)與非完全二叉樹(shù).png

3.二叉樹(shù)的一些性質(zhì)

1. 二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為 2^(i-1) (i≥1)
2. 深度為h的二叉樹(shù)至多有2^h-1個(gè)結(jié)點(diǎn)(h≥1)
3. 包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為log2 (n+1)
4. 在任意一棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

4.二叉樹(shù)的遍歷方式

二叉樹(shù)的遍歷方式，一般分為前序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷。

前、中、后序遍歷是針對(duì)中間（父親）節(jié)點(diǎn)來(lái)說(shuō)的，如前序遍歷，即先遍歷中間（父親）節(jié)點(diǎn)；中序遍歷，就是第二個(gè)遍歷中間（父親）節(jié)點(diǎn)。這么說(shuō)也許還是有點(diǎn)抽象，下面就舉個(gè)栗子吧。

image.png

• 前序遍歷(中-左-右):1-2-4-8-9-5-10-3-6-7
• 中序遍歷:(左-中-右):8-4-9-2-10-5-1-6-3-7
• 后序遍歷(左-右-中):8-9-4-10-5-2-6-7-3-1

層次遍歷就更簡(jiǎn)單了，也就是逐層遍歷，接著上面例圖，它的層次遍歷結(jié)果為:1-2-3-4-5-6-7-8-9-10。值得一提的是，二叉樹(shù)的層次遍歷其實(shí)是利用了隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

光談理論總覺(jué)得差點(diǎn)什么，讓人提不起興趣。接下來(lái)就看看各個(gè)遍歷方法如何用代碼實(shí)現(xiàn)吧。正好最近在python，所以以下代碼均為python實(shí)現(xiàn)。
不過(guò)在此之前，我們還是看看如何來(lái)創(chuàng)建一棵二叉樹(shù)吧.

4.1 二叉樹(shù)的創(chuàng)建

class node:
    def __init__(self, k=None, l=None, r=None) -> None:
        super().__init__()
        self.key = k
        self.left = l
        self.right = r


# 生成二叉樹(shù)
def createBinaryTree():
    key = input("enter a value(# is the end of a leaf):")
    if key is "#":
        root = None
    else:
        root = node(key, createBinaryTree(), createBinaryTree())
    return root

首先定義了一個(gè)node類，只有三個(gè)屬性，key表示鍵值，left表示左孩子，right表示右孩子，當(dāng)然也可以加上父親節(jié)點(diǎn),不過(guò)這里還用不到父親節(jié)點(diǎn)，所以就不用加上了。
接著寫了一個(gè)createBinaryTree的方法，鍵入key的值，如果key的值為'#'，則代表一個(gè)左節(jié)點(diǎn)（右節(jié)點(diǎn)）的結(jié)束。如果不是'#'，那么就創(chuàng)建一個(gè)新的節(jié)點(diǎn)，利用遞歸思想繼續(xù)創(chuàng)建。
還是老規(guī)矩，舉個(gè)栗子，如果我們要?jiǎng)?chuàng)建以下這個(gè)二叉樹(shù)，如果鍵入呢?

image.png

答案是:A-B-D-#-#-#-C-#-#。怎么樣，是不是很簡(jiǎn)單呢。

好了知道如何創(chuàng)建一個(gè)二叉樹(shù)，就該正式講解如何遍歷二叉樹(shù)了。

4.2前序遍歷

# 前序遍歷
def pre_order(node):
    if node is None:
        return None
    else:
        print(node.key)
        pre_order(node.left)
        pre_order(node.right)

代碼依然很簡(jiǎn)單，主要還是利用了遞歸的思想，拿上圖來(lái)分析，A節(jié)點(diǎn)被傳入，首先判斷A是不是None，顯然不是，所以我們打印A節(jié)點(diǎn)的鍵值，接著將A的左孩子傳入，同樣的B不是None，所以我們打印B，又將B的左孩子傳入...，當(dāng)D遍歷然后，返回到B，B的右孩子為空，所以返回到A，傳入A的右孩子C...。所以最后的遍歷結(jié)果是:A-B-D-C

4.3 中序遍歷

# 中序遍歷
def in_order(node):
    if node is None:
        return None
    else:
        in_order(node.left)
        print(node.key)
        in_order(node.right)

分析同上，這里就不贅述了。遍歷結(jié)果:D-B-A-C

4.4 后續(xù)遍歷

# 后序遍歷
def post_order(node):
    if node is None:
        return None
    else:
        post_order(node.left)
        post_order(node.right)
        print(node.key)

分析還是同上,遍歷結(jié)果：D-B-C-A
其實(shí)，很容易發(fā)現(xiàn)，采用何種遍歷方式，就是講print(node.key)這句代碼放在哪個(gè)位置。

4.5 層次遍歷

# 層次遍歷
def levelOrderTravel(node):
    if node is None:
        return
    q = [node]
    while len(q):
        print(q[0].key)
        node = q.pop(0)
        if node.left is not None:
            q.append(node.left)
        if node.right is not None:
            q.append(node.right)

上文中曾提到，二叉樹(shù)的層次遍歷其實(shí)是運(yùn)用到了隊(duì)列，我們還是用上面那個(gè)簡(jiǎn)單的二叉樹(shù)來(lái)作分析，它的遍歷結(jié)果為:A-B-C-D。代碼是如何實(shí)現(xiàn)的呢？其實(shí)是首先將A入隊(duì)，然后然后讀取隊(duì)首，判斷其是否有左孩子，有則入隊(duì)，然后判斷右孩子，有則入隊(duì)，最后將隊(duì)首彈出，注意，隊(duì)列的彈出順序就是層次遍歷的順序。

image.png

5.寫在后面

二叉樹(shù)的一些基本內(nèi)容差不多就介紹這么多，之后準(zhǔn)備寫一點(diǎn)二叉樹(shù)的應(yīng)用。比如，二叉堆（堆排序），二叉搜索樹(shù)等。

持續(xù)更新中...
二叉樹(shù)（二）-二叉堆