python实现二叉树及其基本方法-阿里云开发者社区

开发者社区> python之战> 正文

python实现二叉树及其基本方法

简介: 什么是二叉树:每个节点最多有两个子树的树结构,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。 二叉树具备以下数学性质: 在二叉树的第i层上至多有2^(i-1)个结点(i>0) 深度为k的二叉树至多有2^k - 1个结点(k>0) ...
+关注继续查看

什么是二叉树:每个节点最多有两个子树的树结构,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

二叉树具备以下数学性质:

  • 在二叉树的第i层上至多有2^(i-1)个结点(i>0)

  • 深度为k的二叉树至多有2^k - 1个结点(k>0)

  • 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

  • 具有n个结点的完全二叉树的深度必为 log2(n+1)

  • 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)



两个子概念:

满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树

2019-04-11-21_14_47.png

完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

2019-04-11-21_14_47.png


二叉树的实现

二叉树由两个对象组成,一个是节点对象,一个是树对象

class Node:
    """节点类"""
    def __init__(self, elem, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """树类"""
    def __init__(self, root=None):
        self.root = root


接下来给这树添加基本方法:增加节点

class Node:
    """节点类"""
    def __init__(self, elem, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """树类"""
    def __init__(self, root=None):
        self._root = root

    def add(self, item):
        node = Node(item)
        if not self._root:
            self._root = node
            return
        queue = [self._root]
        while queue:
            cur = queue.pop(0)
            if not cur.lchild:
                cur.lchild = node
                return
            elif not cur.rchild:
                cur.rchild = node
                return
            else:
                queue.append(cur.rchild)
                queue.append(cur.lchild)


对二叉树节点的操作是通过列表存储节点的形式来操作,但是二叉树数据本身是通过链表的形式来存储,节点的操作一般使用递归函数。

二叉树的遍历又分为深度遍历和广度遍历,深度遍历还要分中序遍历/先序遍历/后序遍历,将在下一篇来给二叉树增加遍历方法。

2019-04-11-21_14_48.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10089 0
创建二叉树来实现指路问题
  生活中我们经常会遇到这样的问题,对话如下。路人:“同学,请问湘大图书馆怎么走啊?” 学生:“前面路口左转,然后直走,第三个路口左转,之后再右转就到了。”这里就涉及到创建二叉树来解决此类问题的方法了。
656 0
【算法与数据结构】查找二叉树的实现
(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目介绍     二叉树是一种基本的数据结构。查找二叉树是一种方便与查找,删除,插入等功能的二叉树,它要求每个父节点的左分支小于父节点,右分支大于父节点。下面我们来实现下面这个查找二叉树。 2.java代码实现 public class BinaryTree { priv
730 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13892 0
javascript二叉树基本功能实现
都是常用的功能。 删除是最复杂的。。 test function BinarySearchTree(){ var Node = function(key){ this.
838 0
二叉排序树C实现(含完整源码) - 兰亭风雨的专栏 - 博客频道 - CSDN.NET
来源:http://blog.csdn.net/ns_code/article/details/19823463#1536434-hi-1-95667-42d97150898b1af15ddaae52f91f09c2
713 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载