二叉樹 是一種特殊的“樹”結(jié)構(gòu)棋傍，它每個節(jié)點(diǎn)最多有兩個子樹救拉。
樹
樹 是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合瘫拣。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉湟谛酰簿褪钦f它是根朝上，而葉朝下的麸拄。樹跟圖的區(qū)別就在于派昧，樹是有 層次結(jié)構(gòu) 的。
樹中只有子節(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)的節(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)全都靠左排列陆错，除了最后一層的葉子節(jié)點(diǎn)意外其他任何一層的節(jié)點(diǎn)都是滿的，這樣的二叉樹金赦。
二叉樹存儲方式
二叉樹可以使用鏈表來實(shí)現(xiàn)音瓷，也可以使用數(shù)組來實(shí)現(xiàn)，這兩種存儲方式各有各的優(yōu)缺點(diǎn)夹抗。
鏈?zhǔn)酱鎯?/h3>
![]()
鏈?zhǔn)酱鎯Φ亩鏄?png
二叉樹使用鏈?zhǔn)酱鎯ι鳎恳粋€節(jié)點(diǎn)都需要包含三部分的內(nèi)容：本節(jié)點(diǎn)的值、左子節(jié)點(diǎn)指針漠烧、右子節(jié)點(diǎn)指針杏愤。這種方式只要知道父節(jié)點(diǎn)，就能依次找到該節(jié)點(diǎn)的子節(jié)點(diǎn)已脓。這種鏈?zhǔn)酱鎯Φ姆绞矫總€節(jié)點(diǎn)需要包含這三部分珊楼，所以會浪費(fèi)一定的存儲空間，但是實(shí)現(xiàn)起來很容易度液，對于內(nèi)存空間的使用比較靈活厕宗。
順序存儲
二叉樹使用順序存儲，需要使用一個數(shù)組堕担。由于數(shù)組是一個連續(xù)的存儲空間已慢，所以，數(shù)組的下標(biāo)是連續(xù)的照宝，且可以計算出來的蛇受。這樣就免去了鏈?zhǔn)酱鎯χ忻總€節(jié)點(diǎn)都需要記錄子節(jié)點(diǎn)指針的空間，每個節(jié)點(diǎn)只需要記錄自己的值就可以了厕鹃。
從圖中的值可以看出來兢仰，假設(shè)父節(jié)點(diǎn)的存儲位置設(shè)為i，那么剂碴，左子節(jié)點(diǎn)位置 = 2 × i把将；右子節(jié)點(diǎn)位置 = 2 × i + 1。這樣我們就可以通過下標(biāo)計算來計算出來各個節(jié)點(diǎn)的位置了忆矛。
另外察蹲，如圖请垛，如果二叉樹不是完全二叉樹的話，那么圖中的G點(diǎn)(怪怪的感覺??)就不存在洽议，那么右邊的存儲數(shù)組的第6個位置就會不存儲任何東西宗收，這樣的話，造成了數(shù)組存儲的離散亚兄，導(dǎo)致空間浪費(fèi)混稽。如果這樣的情況多了，空間就會浪費(fèi)的多的多审胚。所以如果最后一排葉子節(jié)點(diǎn)都靠左排列匈勋，即二叉樹為完全二叉樹的時候，空間才會是最省的膳叨，所以完全二叉樹的概念并不是沒有用的洽洁。
二叉樹遍歷
要想從頭到尾將二叉樹遍歷完全，可以有很多種方式菲嘴。先饿自、中、后序遍歷(深度優(yōu)先)临谱；層次遍歷(廣度優(yōu)先)……層次遍歷的話可以采用一個隊(duì)列來實(shí)現(xiàn)璃俗，這個在廣度優(yōu)先算法一篇寫過了。深度優(yōu)先的話悉默，可以有三種遍歷的方式：先序遍歷城豁、中序遍歷、后序遍歷抄课。
這三種遍歷方式就是跟節(jié)點(diǎn)的區(qū)別在于對于每個節(jié)點(diǎn)的訪問邏輯順序不同唱星，都是利用遞歸(非遞歸先不考慮)來進(jì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)的右子節(jié)點(diǎn)
后序遍歷：①訪問父節(jié)點(diǎn)的左子節(jié)點(diǎn) => ②訪問父節(jié)點(diǎn)的右子節(jié)點(diǎn) => ③打印父節(jié)點(diǎn)
所謂的前中后，指的是打印父節(jié)點(diǎn)值的時機(jī)跟磨。先序遍歷是先打印父節(jié)點(diǎn)间聊，然后遞歸訪問父節(jié)點(diǎn)的左子節(jié)點(diǎn)，然后再遞歸訪問父節(jié)點(diǎn)的右子節(jié)點(diǎn)……
算法實(shí)現(xiàn)
# -*- coding: utf-8 -*-
# @Time : 2019-03-25 16:41
# @Author : Jaedong
# @Version : 3.6
# @File : TraversingBinaryTree.py
# @Software: PyCharm
class Node:
value = ''
leftNode = None
rightNode = None
def __init__(self, value, leftNode, rightNode):
self.value = value
self.leftNode = leftNode
self.rightNode = rightNode
# 先序遍歷就是：根節(jié)點(diǎn)->左子樹->右子樹
def preorder_traversal(root):
if root == None:
return
print(root.value)
preorder_traversal(root.leftNode)
preorder_traversal(root.rightNode)
# 中序遍歷就是：左子樹->根節(jié)點(diǎn)->右子樹
def inorder_traversal(root):
if root == None:
return
inorder_traversal(root.leftNode)
print(root.value)
inorder_traversal(root.rightNode)
# 后序遍歷就是：左子樹->右子樹->根節(jié)點(diǎn)
def postorder_traversal(root):
if root == None:
return
postorder_traversal(root.leftNode)
postorder_traversal(root.rightNode)
print(root.value)
# 簡單粗暴抵拘，先來一棵二叉樹
node_d = Node('D', None, None)
node_e = Node('E', None, None)
node_b = Node('B', node_d, node_e)
node_f = Node('F', None, None)
node_c = Node('C', None, node_f)
root = Node('A', node_b, node_c)
print('先序遍歷：')
preorder_traversal(root)
print('中序遍歷：')
inorder_traversal(root)
print('后序遍歷：')
postorder_traversal(root)
結(jié)果是：
