七十六、 數(shù)據(jù)結(jié)構(gòu)二叉樹及其代碼實現(xiàn)

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

樹

樹是一種非常重要的非線性結(jié)構(gòu)，本身具有遞歸的性質(zhì)(在其后的編程中體現(xiàn)的淋漓盡致)。

看下圖，A 節(jié)點就是 B 節(jié)點的父節(jié)點，B 節(jié)點是 A 節(jié)點的子節(jié)點。B、C、D 這三個節(jié)點的父節(jié)點是同一個節(jié)點A，沒有父節(jié)點的叫做根節(jié)點，也就是 E 。

沒有子節(jié)點的節(jié)點叫作葉子節(jié)點或者葉節(jié)點，圖中的G，H，I，J，K，L

關(guān)于“樹”，還有三個比較相似的概念：高度（Height）、深度（Depth），層（level）

二叉樹（binary Tree）

二叉樹是n(n>=0)個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹組成。

上圖中，編號1是普通二叉樹，編號2又是滿二叉樹，編號2又是完全二叉樹。

滿二叉樹：在一棵二叉樹中。如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹的特點有：

• 葉子只能出現(xiàn)在最下一層。出現(xiàn)在其它層就不可能達(dá)成平衡。
• 非葉子結(jié)點的度一定是2。
• 在同樣深度的二叉樹中，滿二叉樹的結(jié)點個數(shù)最多，葉子數(shù)最多。

編號3是完全二叉樹

「對一顆具有n個結(jié)點的二叉樹按層編號，如果編號為i(1<=i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹?！?/strong>

就是保證葉子節(jié)點的上面層都要達(dá)到最大，最低下兩層，最后一層的葉子節(jié)點都靠左排列

二叉樹具備以下數(shù)學(xué)性質(zhì)：

• 在二叉樹的第i層上至多有個結(jié)點（i>0）
• 深度為k的二叉樹至多有個結(jié)點（k>0）
• 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則;
• 具有n個結(jié)點的完全二叉樹的深度必為

二叉樹的遍歷和節(jié)點的刪除

二叉樹的遍歷是指從二叉樹的根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次，且僅被訪問一次。

• 中序遍歷：先左子樹，再根節(jié)點，最后右子樹
• 前序遍歷：先根節(jié)點，再左子樹，最后右子樹
• 后序遍歷：先左子樹，再右子樹，最后根節(jié)點。

前序遍歷通俗的說就是從二叉樹的根結(jié)點出發(fā)，當(dāng)?shù)谝淮蔚竭_(dá)結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。

中序遍歷就是從二叉樹的根結(jié)點出發(fā)，當(dāng)?shù)诙蔚竭_(dá)結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。

后序遍歷就是從二叉樹的根結(jié)點出發(fā)，當(dāng)?shù)谌蔚竭_(dá)結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。

刪除共有三種情況

• 被刪除的節(jié)點是葉子節(jié)點，這時候只要把這個節(jié)點刪除，再把指向這個節(jié)點的父節(jié)點指針置為空就行

• 被刪除的節(jié)點有左子樹，或者有右子樹，而且只有其中一個，那么只要把當(dāng)前刪除節(jié)點的父節(jié)點指向被刪除節(jié)點的左子樹或者右子樹就行。

• 如果要刪除的節(jié)點有兩個子節(jié)點，需要找到這個節(jié)點的右子樹的最小節(jié)點，把它替換到要刪除的節(jié)點上，然后再刪除掉這個最小節(jié)點，因為最小節(jié)點肯定沒有左子節(jié)點

代碼具體實現(xiàn)二叉樹

上面就是二叉樹全部內(nèi)容，下面用Pytho代碼具體實現(xiàn)二叉樹。

按下來就是編程實現(xiàn)了，請動手自己實現(xiàn)一把。

先實現(xiàn)一個 node 節(jié)點類：

class?Node(object):
????def?__init__(self,?item):
????????self.item?=?item
????????self.left?=?None
????????self.right?=?None

????def?__str__(self):
????????return?str(self.item)

這里的 __str__ 方法是為了方便打印。在 print 一個 Node 類時會打印__str__的返回值,例如：print(Node(5)) 就會打印出字符串 5 。

實現(xiàn)一個二叉樹類：

class?Tree(object):
????def?__init__(self):
????????#?根節(jié)點定義為 root 永不刪除，做為哨兵使用。
????????self.root?=?Node('root')
????#?添加節(jié)點操作
????def?add(self,?item):
????????node?=?Node(item)
????????if?self.root?is?None:
????????????self.root?=?node
????????else:
????????????q?=?[self.root]
????????????while?True:
????????????????pop_node?=?q.pop(0)
????????????????if?pop_node.left?is?None:
????????????????????pop_node.left?=?node
????????????????????return
????????????????elif?pop_node.right?is?None:
????????????????????pop_node.right?=?node
????????????????????return
????????????????else:
????????????????????q.append(pop_node.left)
????????????????????q.append(pop_node.right)

????def?get_parent(self,?item):
????????'''
????????找到?Item?的父節(jié)點
????????'''
????????if?self.root.item?==?item:
????????????return?None??#?根節(jié)點沒有父節(jié)點
????????tmp?=?[self.root]
????????while?tmp:
????????????pop_node?=?tmp.pop(0)
????????????if?pop_node.left?and?pop_node.left.item?==?item:
????????????????return?pop_node
????????????if?pop_node.right?and?pop_node.right.item?==?item:
????????????????return?pop_node
????????????if?pop_node.left?is?not?None:
????????????????tmp.append(pop_node.left)
????????????if?pop_node.right?is?not?None:
????????????????tmp.append(pop_node.right)
????????return?None

????def?delete(self,?item):
????????'''
????????從二叉樹中刪除一個元素
????????先獲取?待刪除節(jié)點?item?的父節(jié)點
????????如果父節(jié)點不為空，
????????????判斷?item?的左右子樹
????????????如果左子樹為空，那么判斷?item?是父節(jié)點的左孩子，還是右孩子，如果是左孩子，將父節(jié)點的左指針指向?item?的右子樹，反之將父節(jié)點的右指針指向?item?的右子樹
????????????如果右子樹為空，那么判斷?item?是父節(jié)點的左孩子，還是右孩子，如果是左孩子，將父節(jié)點的左指針指向?item?的左子樹，反之將父節(jié)點的右指針指向?item?的左子樹
????????????如果左右子樹均不為空，尋找右子樹中的最左葉子節(jié)點 x ，將 x 替代要刪除的節(jié)點。
????????刪除成功，返回?True
????????刪除失敗,?返回?False

????????'''
????????if?self.root?is?None:??#?如果根為空，就什么也不做
????????????return?False

????????parent?=?self.get_parent(item)
????????if?parent:
????????????del_node?=?parent.left?if?parent.left.item?==?item?else?parent.right??#?待刪除節(jié)點
????????????if?del_node.left?is?None:
????????????????if?parent.left.item?==?item:
????????????????????parent.left?=?del_node.right
????????????????else:
????????????????????parent.right?=?del_node.right
????????????????del?del_node
????????????????return?True
????????????elif?del_node.right?is?None:
????????????????if?parent.left.item?==?item:
????????????????????parent.left?=?del_node.left
????????????????else:
????????????????????parent.right?=?del_node.left
????????????????del?del_node
????????????????return?True
????????????else:??#?左右子樹都不為空
????????????????tmp_pre?=?del_node
????????????????tmp_next?=?del_node.right
????????????????if?tmp_next.left?is?None:
????????????????????#?替代
????????????????????tmp_pre.right?=?tmp_next.right
????????????????????tmp_next.left?=?del_node.left
????????????????????tmp_next.right?=?del_node.right

????????????????else:
????????????????????while?tmp_next.left:??#?讓tmp指向右子樹的最后一個葉子
????????????????????????tmp_pre?=?tmp_next
????????????????????????tmp_next?=?tmp_next.left
????????????????????#?替代
????????????????????tmp_pre.left?=?tmp_next.right
????????????????????tmp_next.left?=?del_node.left
????????????????????tmp_next.right?=?del_node.right
????????????????if?parent.left.item?==?item:
????????????????????parent.left?=?tmp_next
????????????????else:
????????????????????parent.right?=?tmp_next
????????????????del?del_node
????????????????return?True
????????else:
????????????return?False

????def?traverse(self):??#?層次遍歷
????????if?self.root?is?None:
????????????return?None
????????q?=?[self.root]
????????res?=?[self.root.item]
????????while?q?!=?[]:
????????????pop_node?=?q.pop(0)
????????????if?pop_node.left?is?not?None:
????????????????q.append(pop_node.left)
????????????????res.append(pop_node.left.item)

????????????if?pop_node.right?is?not?None:
????????????????q.append(pop_node.right)
????????????????res.append(pop_node.right.item)
????????return?res

????def?preorder(self,?root):??#?先序遍歷
????????if?root?is?None:
????????????return?[]
????????result?=?[root.item]
????????left_item?=?self.preorder(root.left)
????????right_item?=?self.preorder(root.right)
????????return?result?+?left_item?+?right_item

????def?inorder(self,?root):??#?中序遍歷
????????if?root?is?None:
????????????return?[]
????????result?=?[root.item]
????????left_item?=?self.inorder(root.left)
????????right_item?=?self.inorder(root.right)
????????return?left_item?+?result?+?right_item

????def?postorder(self,?root):??#?后序遍歷
????????if?root?is?None:
????????????return?[]
????????result?=?[root.item]
????????left_item?=?self.postorder(root.left)
????????right_item?=?self.postorder(root.right)
????????return?left_item?+?right_item?+?result

運行測試：

if?__name__?==?'__main__':
????t?=?Tree()
????for?i?in?range(10):
????????t.add(i)
????print('層序遍歷:',?t.traverse())
????print('先序遍歷:',?t.preorder(t.root))
????print('中序遍歷:',?t.inorder(t.root))
????print('后序遍歷:',?t.postorder(t.root))

????for?i?in?range(10):
????????print(i,?"?的父親",?t.get_parent(i))

????for?i?in?range(0,?15,?3):
????????print(f"刪除?{i}",?'成功'?if?t.delete(i)?else?'失敗')
????????print('層序遍歷:',?t.traverse())
????????print('先序遍歷:',?t.preorder(t.root))
????????print('中序遍歷:',?t.inorder(t.root))
????????print('后序遍歷:',?t.postorder(t.root))

執(zhí)行結(jié)果如下：

層序遍歷:?['root',?0,?1,?2,?3,?4,?5,?6,?7,?8,?9]
先序遍歷:?['root',?0,?2,?6,?7,?3,?8,?9,?1,?4,?5]
中序遍歷:?[6,?2,?7,?0,?8,?3,?9,?'root',?4,?1,?5]
后序遍歷:?[6,?7,?2,?8,?9,?3,?0,?4,?5,?1,?'root']
0??的父親?root
1??的父親?root
2??的父親?0
3??的父親?0
4??的父親?1
5??的父親?1
6??的父親?2
7??的父親?2
8??的父親?3
9??的父親?3
刪除?0?成功
層序遍歷:?['root',?8,?1,?2,?3,?4,?5,?6,?7,?9]
先序遍歷:?['root',?8,?2,?6,?7,?3,?9,?1,?4,?5]
中序遍歷:?[6,?2,?7,?8,?3,?9,?'root',?4,?1,?5]
后序遍歷:?[6,?7,?2,?9,?3,?8,?4,?5,?1,?'root']
刪除?3?成功
層序遍歷:?['root',?8,?1,?2,?9,?4,?5,?6,?7]
先序遍歷:?['root',?8,?2,?6,?7,?9,?1,?4,?5]
中序遍歷:?[6,?2,?7,?8,?9,?'root',?4,?1,?5]
后序遍歷:?[6,?7,?2,?9,?8,?4,?5,?1,?'root']
刪除?6?成功
層序遍歷:?['root',?8,?1,?2,?9,?4,?5,?7]
先序遍歷:?['root',?8,?2,?7,?9,?1,?4,?5]
中序遍歷:?[2,?7,?8,?9,?'root',?4,?1,?5]
后序遍歷:?[7,?2,?9,?8,?4,?5,?1,?'root']
刪除?9?成功
層序遍歷:?['root',?8,?1,?2,?4,?5,?7]
先序遍歷:?['root',?8,?2,?7,?1,?4,?5]
中序遍歷:?[2,?7,?8,?'root',?4,?1,?5]
后序遍歷:?[7,?2,?8,?4,?5,?1,?'root']
刪除?12?失敗
層序遍歷:?['root',?8,?1,?2,?4,?5,?7]
先序遍歷:?['root',?8,?2,?7,?1,?4,?5]
中序遍歷:?[2,?7,?8,?'root',?4,?1,?5]
后序遍歷:?[7,?2,?8,?4,?5,?1,?'root']

Binarytree是一個Python庫，它通過一個簡單的API生成二叉樹，可以進(jìn)行檢查和操作。Github：https://github.com/joowani/binarytree/releases。

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

?