文档章节

python 数据结构 tree 的插入和遍历

hyhlinux
 hyhlinux
发布于 2016/11/17 16:25
字数 273
阅读 43
收藏 0

# coding:utf-8
class Node(object):
    """docstring for Node"""

    def __init__(self, item=-1, lchild=None, rchild=None):
        self.item = item
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """docstring for Tree"""

    def __init__(self):
        self.root = Node()

    def add(self, item):
        '''
        添加一个节点
        顺序:从上至下,从左至右.
        '''
        node = Node(item)

        if self.root.item == -1:
            self.root = node
        else:
            myqueue = []
            tree_node = self.root
            myqueue.append(tree_node)

            while myqueue:
                tree_node = myqueue.pop(0)
                if not tree_node.lchild:
                    # 左孩子空,添加到左孩子.
                    tree_node.lchild = node
                    return
                elif not tree_node.rchild:
                    tree_node.rchild = node
                    return
                else:
                    # 若左右都不为空,加入该节点的左右孩子到列表
                    myqueue.append(tree_node.lchild)
                    myqueue.append(tree_node.rchild)

    def front(self, root=None):
        if not root:
            return
        print(root.item)
        self.front(root.lchild)
        self.front(root.rchild)

    def middle(self, root=None):
        if not root:
            return
        self.middle(root.lchild)
        print(root.item)
        self.middle(root.rchild)

    def later(self, root=None):
        if not root:
            return
        self.later(root.lchild)
        self.later(root.rchild)
        print(root.item)

    def level_search(self, root):
        '''
        从上至下,从左至右.
        '''
        if not root:
            return

        myQueue = []
        node = root
        myQueue.append(node)

        while myQueue:
            tree_node = myQueue.pop(0)
            print(tree_node.item)

            if tree_node.lchild:
                myQueue.append(tree_node.lchild)

            if tree_node.rchild:
                myQueue.append(tree_node.rchild)


def main():
    tree = Tree()
    for i in xrange(7):
        tree.add(i)

    # tree.front(tree.root)
    # 0 1 3 4 2 5 6
    # tree.middle(tree.root)
    # 3 1 4 0 5 2 6
    # tree.later(tree.root)
    #3, 4, 1, 5, 6, 2, 0
    tree.level_search(tree.root)
    # 0 1 2 3 4 5 6

if __name__ == '__main__':
    main()

##########################
#             0
#     1       |     2
# 3       4   |  5      6
##########################

 

© 著作权归作者所有

上一篇: tornado wechat
下一篇: python 2.7 编码
hyhlinux
粉丝 8
博文 176
码字总数 59681
作品 0
海淀
程序员
私信 提问
python环境下使用mysql数据及数据结构和二叉树算法(图)

python环境下使用mysql数据及数据结构和二叉树算法(图): 1 python环境下使用mysql 2使用的是 pymysql库 3 开始-->创建connection-->获取cursor-->操作-->关闭cursor->关闭connection->结束......

原创小博客
2018/08/26
24
0
Python -二叉树 创建与遍历算法(很详细)

树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。 一个节点被标记为根节点。 除根节点之外的每个节点都与一个父节点关联。 每个节点可以有一个arbiatry编号的chid节点。 ...

小锋学长
08/08
0
0
《Python从小白到大牛》第9章 数据结构

当你有很多书时,你会考虑买一个书柜,将你的书分门别类摆放进入。使用了书柜不仅仅使房间变得整洁,也便于以后使用书时方便查找。在计算机程序中会有很多数据,这些数据也需要一个容器将他们...

tony关东升
2018/08/21
0
0
维基百科:PyPy 和 CPython 的性能比较测试

最近我在维基百科上完成了一些数据挖掘方面的任务。它由这些部分组成: 解析enwiki-pages-articles.xml的维基百科转储; 把类别和页存储到MongoDB里面; 对类别名称进行重新分门别类。 我对C...

oschina
2013/02/19
9.5K
20
《Python官方文档》5.数据结构

数据结构 本章会更细节的讲一些你已经学过的东西,同时也会加一些新的内容 5.1 List有关方法 list有许多方法,以下是list方法的所有实例: 添加1个item到list的末尾,等同于 以迭代器方式追加...

caomaocao
2018/01/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
15分钟前
1
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
17分钟前
4
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
19分钟前
3
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
25分钟前
4
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
49分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部