Python|实现二叉树
问题描述
在树的种类中，有这样一类树，它每个节点下面有两个新的左右节点(一般称为该节点的左右子树)，且每个节点的子树有左右之分不能颠倒，这样的树叫做二叉树。接下来就用python来实现二叉树。
解决方案
首先要找准二叉树的结构特点：由根节点引出以下的左右的两个子节点，然后再由子节点引出相应的子节点,且每一个节点的子树之分不能颠倒。
第一步：
创建一个节点类，其中包含左右两个子树与节点的值：
class Node(object): def __init__(self,item): self.elem=item #创建节点值 self.left=None #创建左子树 self.right=None #创建右子树 |
|---|
第二步：
创建一个二叉树类，创建一个根节点：
class Tree(object): def __init__(self):#root定义的根节点 self.root=None |
|---|
在二叉树类中定义一个增加的方法，这里利用的队列来进行二叉树的添加，具体操作是：先把节点放入队列中，然后取出节点，再判断是否有左右子树，没有左右子树就添加左右子树；再取出节点再判断,再增加：
def add(self,item): node=Node(item)#将Node类实例化参数node if self.root is None: self.root=node return queue=[self.root]#创建一个队列，将根节点放入队列中 while queue: cur_node=queue.pop(0)#向队列queue中取出第一个节点进行判断 if cur_node.left is None: cur_node.left=node return else: queue.append(cur_node.left) if cur_node.right is None: cur_node.right=node return else: queue.append(cur_node.right) |
|---|
第三步：
定义一个广度遍历的方法来判断添加的节点是否正确。
def breadth(self): if self.root is None: #首先判断根节点是否为空，为空则返回 return queue=[self.root]#将根节点放入队列中 while queue: cur_node = queue.pop(0)#取出节点 print(cur_node.elem,end=' ')#打印节点值，也是广度遍历的值 if cur_node.left is not None:#判断左子树 queue.append(cur_node.left) if cur_node.right is not None:#判断右子树 queue.append(cur_node.right) |
|---|
第四步
创建完毕，来试试效果吧！
if __name__ == "__main__": t=Tree()#实例化二叉树类，调用add方法，向二叉树中添加元素 t.add(0) t.add(1) t.add(2) t.add(3) t.add(4) t.add(5) t.add(6) t.add(7) t.add(8) t.breadth()#调用breadth方法，打印二叉树# 输出结果：#0 1 2 3 4 5 6 7 8 |
|---|
结语
本文主要介绍了如何用python来实现二叉树的操作，主要利用了队列元素的取出，判断，增添来实现。以后将会继续介绍用python实现二叉树的几种遍历方法，敬请期待。
END
编 辑 | 王楠岚
责 编 | 王卓越
where2go 团队