python 数据结构 tree 的插入和遍历
博客专区 > hyhlinux 的博客 > 博客详情
python 数据结构 tree 的插入和遍历
hyhlinux 发表于2年前
python 数据结构 tree 的插入和遍历
  • 发表于 2年前
  • 阅读 12
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

摘要: tree

# 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
##########################

 

标签: tree python
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 7
博文 132
码字总数 51777
×
hyhlinux
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: