python数据结构之二叉树的统计与转换实例

419次阅读  |  发布于5年以前

**一、获取二叉树的深度

**就是二叉树最后的层次,如下图:

实现代码:

复制代码 代码如下:

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  

二、叶子的统计

叶子就是二叉树的节点的 left 指针和 right 指针分别指向空的节点

复制代码 代码如下:

def getleafcount(self):
''' 获取二叉树叶子数 '''
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  

三、统计叶子的分支节点

与叶子节点相对的其他节点 left 和 right 的指针指向其他节点

复制代码 代码如下:

def getbranchcount(self):
''' 获取二叉树分支节点数 '''
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):
''' 二叉树所有结点的左右子树相互交换 '''
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)  

这些方法和操作,都是运用递归。其实二叉树的定义也是一种递归。附上最后的完整代码:

复制代码 代码如下:

-- 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):  
    ''' 获取二叉树叶子数 '''  
    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):  
    ''' 获取二叉树分支节点数 '''  
    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):  
    ''' 二叉树所有结点的左右子树相互交换 '''  
    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

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

'''

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8