快捷導(dǎo)航

python數(shù)據(jù)結(jié)構(gòu)之二叉樹的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例

更新時(shí)間：2014年04月29日 09:16:33 作者：

這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之二叉樹的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例，例如統(tǒng)計(jì)二叉樹的葉子、分支節(jié)點(diǎn)，以及二叉樹的左右兩樹互換等,需要的朋友可以參考下

一、獲取二叉樹的深度

就是二叉樹最后的層次，如下圖：

實(shí)現(xiàn)代碼：

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

def getheight(self):
        ''' 獲取二叉樹深度 '''
        return self.__get_tree_height(self.root)

    def __get_tree_height(self, root):
        if root is 0:
            return 0
        if root.left is 0 and root.right is 0:
            return 1
        else:
            left = self.__get_tree_height(root.left)
            right = self.__get_tree_height(root.right)
            if left < right:
                return right + 1
            else:
                return left + 1

二、葉子的統(tǒng)計(jì)

葉子就是二叉樹的節(jié)點(diǎn)的 left 指針和 right 指針分別指向空的節(jié)點(diǎn)

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

def getleafcount(self):
        ''' 獲取二叉樹葉子數(shù) '''
        return self.__count_leaf_node(self.root)

    def __count_leaf_node(self, root):
        res = 0
        if root is 0:
            return res
        if root.left is 0 and root.right is 0:
            res += 1
            return res
        if root.left is not 0:
            res += self.__count_leaf_node(root.left)
        if root.right is not 0:
            res += self.__count_leaf_node(root.right)
        return res

三、統(tǒng)計(jì)葉子的分支節(jié)點(diǎn)

與葉子節(jié)點(diǎn)相對的其他節(jié)點(diǎn) left 和 right 的指針指向其他節(jié)點(diǎn)

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

def getbranchcount(self):
        ''' 獲取二叉樹分支節(jié)點(diǎn)數(shù) '''
        return self.__get_branch_node(self.root)

    def __get_branch_node(self, root):
        if root is 0:
            return 0
        if root.left is 0 and root.right is 0:
            return 0
        else:
            return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)

四、二叉樹左右樹互換

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

def replacelem(self):
        ''' 二叉樹所有結(jié)點(diǎn)的左右子樹相互交換 '''
        self.__replace_element(self.root)

    def __replace_element(self, root):
        if root is 0:
            return
        root.left, root.right = root.right, root.left
        self.__replace_element(root.left)
        self.__replace_element(root.right)

這些方法和操作，都是運(yùn)用遞歸。其實(shí)二叉樹的定義也是一種遞歸。附上最后的完整代碼：

復(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 BinaryTree(object):

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

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

    def create(self):
        temp = input('enter a value:')
        if temp is '#':
            return 0
        treenode = TreeNode(data=temp)
        if self.root is 0:
            self.root = treenode

        treenode.left = self.create()
        treenode.right = self.create()

    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

    def preorders(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 inorders(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 postorders(self, treenode):
        '后序（post-order，LRN）非遞歸遍歷'
        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 postorders(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 levelorders(self, treenode):
        '層序（post-order，LRN）非遞歸遍歷'
        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)

    def getheight(self):
        ''' 獲取二叉樹深度 '''
        return self.__get_tree_height(self.root)

    def __get_tree_height(self, root):
        if root is 0:
            return 0
        if root.left is 0 and root.right is 0:
            return 1
        else:
            left = self.__get_tree_height(root.left)
            right = self.__get_tree_height(root.right)
            if left < right:
                return right + 1
            else:
                return left + 1

    def getleafcount(self):
        ''' 獲取二叉樹葉子數(shù) '''
        return self.__count_leaf_node(self.root)

    def __count_leaf_node(self, root):
        res = 0
        if root is 0:
            return res
        if root.left is 0 and root.right is 0:
            res += 1
            return res
        if root.left is not 0:
            res += self.__count_leaf_node(root.left)
        if root.right is not 0:
            res += self.__count_leaf_node(root.right)
        return res

    def getbranchcount(self):
        ''' 獲取二叉樹分支節(jié)點(diǎn)數(shù) '''
        return self.__get_branch_node(self.root)

    def __get_branch_node(self, root):
        if root is 0:
            return 0
        if root.left is 0 and root.right is 0:
            return 0
        else:
            return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)

    def replacelem(self):
        ''' 二叉樹所有結(jié)點(diǎn)的左右子樹相互交換 '''
        self.__replace_element(self.root)

    def __replace_element(self, root):
        if root is 0:
            return
        root.left, root.right = root.right, root.left
        self.__replace_element(root.left)
        self.__replace_element(root.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 = BinaryTree(root)

print u'''

生成的二叉樹

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

-------------------------

'''