python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實(shí)例

2019-11-25 18:25:40

字體：大中小

供稿：網(wǎng)友

遍歷方案
   　從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：
   　1).訪問結(jié)點(diǎn)本身(N)
   　2).遍歷該結(jié)點(diǎn)的左子樹(L)
   　3).遍歷該結(jié)點(diǎn)的右子樹(R)

有次序：
　NLR、LNR、LRN

遍歷的命名

　根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名：
NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷)) ――訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
LNR：中序遍歷(InorderTraversal) ――訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)。
LRN：后序遍歷(PostorderTraversal) ――訪問結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

注：由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

遍歷算法

1)．先序遍歷的遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.訪問根結(jié)點(diǎn)
b.遍歷左子樹
c.遍歷右子樹

2)．中序遍歷的遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.遍歷左子樹
b.訪問根結(jié)點(diǎn)
c.遍歷右子樹

3)．后序遍歷得遞歸算法定義：
若二叉樹非空，則依次執(zhí)行如下操作：
a.遍歷左子樹
b.遍歷右子樹
c.訪問根結(jié)點(diǎn)

一、二叉樹的遞歸遍歷：

復(fù)制代碼代碼如下:

# -*- coding: utf - 8 - *-

class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data


class BTree(object):

    def __init__(self, root=0):
        self.root = root

    def is_empty(self):
        if self.root is 0:
            return True
        else:
            return False

    def preorder(self, treenode):
        '前序（pre-order，NLR）遍歷'
        if treenode is 0:
            return
        print treenode.data
        self.preorder(treenode.left)
        self.preorder(treenode.right)

    def inorder(self, treenode):
        '中序（in-order，LNR'
        if treenode is 0:
            return
        self.inorder(treenode.left)
        print treenode.data
        self.inorder(treenode.right)

    def postorder(self, treenode):
        '后序（post-order，LRN）遍歷'
        if treenode is 0:
            return
        self.postorder(treenode.left)
        self.postorder(treenode.right)
        print treenode.data


node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

bt = BTree(root)

print u'''

#生成的二叉樹

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

'''
print '前序（pre-order，NLR）遍歷：/n'
bt.preorder(bt.root)

print '中序（in-order，LNR) 遍歷：/n'
bt.inorder(bt.root)

print '后序（post-order，LRN）遍歷：/n'
bt.postorder(bt.root)

二、.二叉樹的非遞歸遍歷

下面就用非遞歸的方式實(shí)現(xiàn)一遍。主要用到了 stack 和 queue維護(hù)一些數(shù)據(jù)節(jié)點(diǎn)：

復(fù)制代碼代碼如下:

# -*- coding: utf - 8 - *-

     
class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data

     
class BTree(object):

    def __init__(self, root=0):
        self.root = root

    def is_empty(self):
        if self.root is 0:
            return True
        else:
            return False

    def preorder(self, treenode):
        '前序（pre-order，NLR）遍歷'
        stack = []
        while treenode or stack:
            if treenode is not 0:
                print treenode.data
                stack.append(treenode)
                treenode = treenode.left
            else:
                treenode = stack.pop()
                treenode = treenode.right

    def inorder(self, treenode):
        '中序（in-order，LNR) 遍歷'
        stack = []
        while treenode or stack:
            if treenode:
                stack.append(treenode)
                treenode = treenode.left
            else:
                treenode = stack.pop()
                print treenode.data
                treenode = treenode.right

    # def postorder(self, treenode):
    #     stack = []
    #     pre = 0
    #     while treenode or stack:
    #         if treenode:
    #             stack.append(treenode)
    #             treenode = treenode.left
    #         elif stack[-1].right != pre:
    #             treenode = stack[-1].right
    #             pre = 0
    #         else:
    #             pre = stack.pop()
    #             print pre.data

    def postorder(self, treenode):
        '后序（post-order，LRN）遍歷'
        stack = []
        queue = []
        queue.append(treenode)
        while queue:
            treenode = queue.pop()
            if treenode.left:
                queue.append(treenode.left)
            if treenode.right:
                queue.append(treenode.right)
            stack.append(treenode)
        while stack:
            print stack.pop().data

    def levelorder(self, treenode):
        from collections import deque
        if not treenode:
            return
        q = deque([treenode])
        while q:
            treenode = q.popleft()
            print treenode.data
            if treenode.left:
                q.append(treenode.left)
            if treenode.right:
                q.append(treenode.right)

     
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

     
bt = BTree(root)

print u'''

#生成的二叉樹

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

'''
print '前序（pre-order，NLR）遍歷 ：/n'
bt.preorder(bt.root)

print '中序（in-order，LNR) 遍歷 ：/n'
bt.inorder(bt.root)

print '后序（post-order，LRN）遍歷 ：/n'
bt.postorder(bt.root)

print '層序（level-order，LRN）遍歷 ：/n'
bt.levelorder(bt.root)