二叉树的建立以及遍历的多种实现(python版)

2018-06-17 23:32:49来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

二叉树是很重要的数据结构,在面试还是日常开发中都是很重要的角色。

首先是建立树的过程,对比C或是C++的实现来讲,其涉及到了较为复杂的指针操作,但是在面向对象的语言中,就不需要考虑指针, 内存等。首先我们需要定义一个树节点, 我们采用基于链表设计的节点, 首先定义一个数据域, 其次就是左孩子和右孩子。如下定义:

# 树节点的定义
class Node:
    def __init__(self, data=-1, lchild=None, rchild=None):
        self.lchild = lchild  # 表示左子树
        self.rchild = rchild  # 表示右子树
        self.data = data  # 表示数据域

 

建立树的实现有两种,遍历建树与层次建树,这两种分别是基于堆栈和队列来实现的,先来看看最基本的递归建树。
递归建树的过程无非就是一路走到底,但是需要将节点的左右孩子节点对其余的节点相关联起来。因此,我们可以如此来实现:

def traversal_create(self, root):
data = input()
if data is "#":
return None
else:
root.data = data
root.lchild = self.traversal_create(root.lchild)
root.rchild = self.traversal_create(root.rchild)
return root

首先我们传入的参数是一个默认的节点,其data数据域为-1,然后我们接受输入的数据,赋值给节点数据域,然后就是递归了,将左右孩子节点关联起来。总体来讲,应该不难理解。

下面看看层次建树的实现,所谓层次建树其实就是基于队列的操作,利用队列先进先出的特点,每次我们访问一个节点的时候,将其存入队列中,待遍历玩当前节点的左右孩子节点,队列就弹出一个节点,之后的操作都是一样的。看看代码:

def add(self, elem):
node = Node(elem)
# 根节点
if self.root.data == -1:
self.root = node
self.myQueue.append(self.root)
else:
treeNode = self.myQueue[0] # 记录结点
if treeNode.lchild is None:
treeNode.lchild = node
self.myQueue.append(treeNode.lchild)
else:
treeNode.rchild = node
self.myQueue.append(treeNode.rchild)
self.myQueue.popleft() # 弹出已经处理好左右子树的父结点

我们输入一个数据,然后根据数据初始化一个节点,放入队列中,随后就是访问的操作了。

树的三序遍历就不用说了,基于递归的,很好理解,那么基于队列以及堆栈的的遍历呢?
对比下基于队列的建树,我们完全可以写出基于队列的遍历, 也是使用队列来存储节点,然后输出左右孩子的数据:

# 层次遍历 使用队列
def queue_tarversal(self, root):
if root is None:
return
q = deque()
q.append(root)
while q:
node = q.pop()
print(node.data)
if node.lchild is not None:
q.append(node.lchild)
else:
q.append(node.rchild)

基于堆栈的呢?联想下堆栈的特点,我们一路沿着左子树遍历下去,同时使用堆栈来存储元素,然后在弹出遍历右孩子节点:

# 使用堆栈来遍历
def stack_traversal(self, root):
if root is None:
return
mystack = []
node = root
while node or mystack:
while node:
print(node.data)
mystack.append(node)
node = node.lchild
node = mystack.pop()
node = node.rchild

数据结构是难点也是基础,不管怎么样都应该好好学习。

完整代码:

''' 二叉树的建立及实现 (递归与非递归) '''
from collections import deque


# 树节点的定义
class Node:
    def __init__(self, data=-1, lchild=None, rchild=None):
        self.lchild = lchild  # 表示左子树
        self.rchild = rchild  # 表示右子树
        self.data = data  # 表示数据域


class Create_Tree:
    def __init__(self):
        self.root = Node()  # 表示结点
        self.myQueue = deque()  # 使用队列不会有太多的内存开销

    # 按层次生成树
    def add(self, elem):
        node = Node(elem)
        # 根节点
        if self.root.data == -1:
            self.root = node
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]  # 记录结点
            if treeNode.lchild is None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.popleft()  # 弹出已经处理好左右子树的父结点

    # 递归建树
    def traversal_create(self, root):
        data = input()
        if data is "#":
            return None
        else:
            root.data = data
            root.lchild = self.traversal_create(root.lchild)
            root.rchild = self.traversal_create(root.rchild)
        return root

    # 前序遍历输出
    def digui(self, root):
        if root is None:
            return
        print(root.data)
        self.digui(root.lchild)
        self.digui(root.rchild)

    # 使用堆栈来遍历
    def stack_traversal(self, root):
        if root is None:
            return
        mystack = []
        node = root
        while node or mystack:
            while node:
                print(node.data)
                mystack.append(node)
                node = node.lchild
            node = mystack.pop()
            node = node.rchild

    # 层次遍历 使用队列
    def queue_tarversal(self, root):
        if root is None:
            return
        q = deque()
        q.append(root)
        while q:
            node = q.pop()
            print(node.data)
            if node.lchild is not None:
                q.append(node.lchild)
            else:
                q.append(node.rchild)


if __name__ == "__main__":
    elems = range(10)
    tree = Create_Tree()
    for i in elems:
        # 非递归建树,主要就是根据 队列FIFO的特点以及广度遍历的思路
        tree.add(i) 

    # 递归建树
    # tree.traversal_create(tree.root)

    # 递归遍历
    tree.digui(tree.root)
    # 栈遍历
    # tree.stack_traversal(tree.root)
View Code

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:paramiko的SFTP对象实现Linux的scp功能

下一篇:python定时利用QQ邮件发送天气预报