当前位置:  编程技术>python

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

    来源: 互联网  发布时间:2014-10-04

    本文导语:  一、获取二叉树的深度就是二叉树最后的层次,如下图: 实现代码: 代码如下:def getheight(self):        ''' 获取二叉树深度 '''        return self.__get_tree_height(self.root)    def __get_tree_height(self, root):        if root is 0:...

一、获取二叉树的深度

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



实现代码:

代码如下:

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

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

'''

    
 
 

您可能感兴趣的文章:

  • 数据结构:图(有向图,无向图),在Python中的表示和实现代码示例
  • python数据结构树和二叉树简介
  • Python常用列表数据结构小结
  • python数据结构之二叉树的建立实例
  • python实现bitmap数据结构详解
  • python数据结构之二叉树的遍历实例
  • Python常见数据结构详解
  • Python namedtuple(命名元组)使用实例
  • python实现的重启关机程序实例
  • Python 3 Tkinter教程之事件Event绑定处理代码实例
  • python调用短信猫控件实现发短信功能实例
  • Python文件操作类操作实例详解
  • python 基础学习第二弹 类属性和实例属性
  • Python实现冒泡,插入,选择排序简单实例
  • Python 时间处理datetime实例
  • Python实现类继承实例
  • Python continue语句用法实例
  • python3编写C/S网络程序实例教程
  • 在python中的socket模块使用代理实例
  • python实现进程间通信简单实例
  • python字典多条件排序方法实例
  • python中enumerate的用法实例解析
  • python解析xml文件实例分享
  • python的绘图工具matplotlib使用实例
  • Python Tkinter简单布局实例教程
  • Python中__call__用法实例
  • 使用Python判断IP地址合法性的方法实例
  • Python中apply函数的用法实例教程
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • Python3中内置类型bytes和str用法及byte和string之间各种编码转换
  • python iis7站长之家
  • Python将日期时间按照格式转换成字符串
  • Python到C++的转换工具 ShedSkin
  • python类型强制转换long to int的代码
  • Python字符转换
  • python 将字符串转换成字典dict
  • python转换摩斯密码示例
  • Python中实现字符串类型与字典类型相互转换的方法
  • python中将字典转换成其json字符串
  • python实现批量转换文件编码(批转换编码示例)
  • Python时间戳与时间字符串互相转换实例代码
  • python3图片转换二进制存入mysql
  • Python实现全角半角转换的方法
  • Python内置函数bin() oct()等实现进制转换
  • python抓取网页时字符集转换问题处理方案分享
  • python将人民币转换大写的脚本代码
  • python中将阿拉伯数字转换成中文的实现代码
  • 常用python数据类型转换函数总结
  • 使用Python进行新浪微博的mid和url互相转换实例(10进制和62进制互算)
  • Python GUI编程:tkinter实现一个窗口并居中代码
  • 让python同时兼容python2和python3的8个技巧分享
  • Python不使用print而直接输出二进制字符串
  • 使用setup.py安装python包和卸载python包的方法
  • Python中实现json字符串和dict类型的互转
  • 不小心把linux自带的python卸载了,导致安装一个依赖原python的软件不能安装,请问该怎么办?
  • python异常信息堆栈输出到日志文件
  • Python开发者社区整站源码 Pythoner
  • python下用os.execl执行centos下的系统时间同步命令ntpdate
  • python读取csv文件示例(python操作csv)
  • Python namedtuple对象json序列化/反序列化及对象恢复


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3