概念

在樹的結(jié)構(gòu)上，每一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)不超過兩個(gè)，此時(shí)的樹稱之為二叉樹

二叉樹中一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為空，則這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)，反之則不是

二叉樹都用頭節(jié)點(diǎn)來標(biāo)識(shí)

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
if __name__ == '__main__':
    t1 = TreeNode(1)
    t2 = TreeNode(2)
    t3 = TreeNode(3)
    t4 = TreeNode(4)
    t5 = TreeNode(5)
    t6 = TreeNode(6)
    t7 = TreeNode(7)
    t8 = TreeNode(8)
    # 生成二叉樹
    t1.left = t2
    t1.right = t3
    t2.left = t4
    t2.right = t5
    t3.left = t6
    t3.right = t7
    t6.left = t8

二叉樹的遍歷

深度優(yōu)先

從開頭走到最深處，然后折返

一上面的數(shù)據(jù)結(jié)構(gòu)為例，如果需要找到所有的數(shù)據(jù)，為以下順序：

t1 --> t2 --> t4 --> t2 --> t5 --> t1 --> t3 --> t6 --> t8 --> t6 --> t7 --> end

先序遍歷

先遍歷輸入根，遍歷走到哪個(gè)數(shù)值則輸出哪個(gè)數(shù)值；以上面的順序?yàn)槔敵鼋Y(jié)果為

1,2,3,4,5,6,7,8

python實(shí)現(xiàn)先序遍歷

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 遞歸方式
def preOrderRecusive(root):
    if root == None:
        return None
    print(root.val)
    preOrderRecusive(root.left)
    preOrderRecusive(root.right)

# 非遞歸方式
def preOrder(root):
    if root == None:
        return None
    stack = []
    tmpNode = root
    while tmpNode or stack:
        while tmpNode:
            print(tmpNode.val)
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack.pop()
        tmpNode = node.right

中序遍歷

先遍歷輸出所有的左子樹，當(dāng)節(jié)點(diǎn)或跟的左子樹全部輸出后，再輸出節(jié)點(diǎn)或跟，然后開始遍歷右子樹子樹，進(jìn)行輸出；以上邊數(shù)據(jù)為例，中序遍歷結(jié)果為

4，2，5，1，6，8，3，7

python實(shí)現(xiàn)中序遍歷

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 遞歸方式
def midOrderRecusive(root):
    if root == None:
        return None
    midOrderRecusive(root.left)
    print(root.val)
    midOrderRecusive(root.right)

# 非遞歸方式
def midOrder(root):
    if root == None:
        return None
    stack = []
    tmpNode = root
    while tmpNode or stack:
        while tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack.pop()
        print(node.val)
        tmpNode = node.right

后序遍歷

對(duì)于根或子節(jié)點(diǎn)來說，先輸出其左子樹，再輸出右子樹，最后輸出根或子節(jié)點(diǎn)；一上面數(shù)據(jù)為例，后序遍歷的結(jié)果為

4，5，2，8，6，7，3，1

python實(shí)現(xiàn)后序遍歷

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 遞歸方式
def latOrderRecusive(root):
    if root == None:
        return None
    latOrderRecusive(root.left)
    latOrderRecusive(root.right)
    print(root.val)
# 非遞歸方式
def latOrder(root):
    if root is None:
        return None
    stack = []
    tmpNode = root
    while tmpNode or stack:
        while tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack[-1]
        tmpNode = node.right
        if node.right is None:
            node = stack.pop()
            print(node.val)
            while stack and node == stack[-1].right:
                node = stack.pop()
                print(node.val)