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

太过爱你忘了你带给我的痛 2024-03-23 19:09 33阅读 0赞

## **1** **问题** ##

何利用python进行二叉树的实现。

## **2** **方法** ##

（1）通过创建二叉树的两个对象，一个是节点对象，一个是树对象。

（2）给这树添加基本方法：增加节点

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class Node: &nbsp; &nbsp;#节点类 &nbsp; &nbsp;def __init__(self, elem, lchild=None, rchild=None): &nbsp; &nbsp; &nbsp; &nbsp;self.elem = elem &nbsp; &nbsp; &nbsp; &nbsp;self.lchild = lchild &nbsp; &nbsp; &nbsp; &nbsp;self.rchild = rchild class Tree: &nbsp; &nbsp;#树类 &nbsp; &nbsp;def __init__(self, root=None): &nbsp; &nbsp; &nbsp; &nbsp;self.root = root class Node: &nbsp; &nbsp;#节点类 &nbsp; &nbsp;def __init__(self, elem, lchild=None, rchild=None): &nbsp; &nbsp; &nbsp; &nbsp;self.elem = elem &nbsp; &nbsp; &nbsp; &nbsp;self.lchild = lchild &nbsp; &nbsp; &nbsp; &nbsp;self.rchild = rchild class Tree: &nbsp; &nbsp;#树类 &nbsp; &nbsp;def __init__(self, root=None): &nbsp; &nbsp; &nbsp; &nbsp;self._root = root &nbsp; &nbsp;def add(self, item): &nbsp; &nbsp; &nbsp; &nbsp;node = Node(item) &nbsp; &nbsp; &nbsp; &nbsp;if not self._root: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self._root = node &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return &nbsp; &nbsp; &nbsp; &nbsp;queue = [self._root] &nbsp; &nbsp; &nbsp; &nbsp;while queue: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur = queue.pop(0) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if not cur.lchild: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur.lchild = node &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;elif not cur.rchild: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur.rchild = node &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;queue.append(cur.rchild) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;queue.append(cur.lchild)</td> 
 </tr> 
 </tbody> 
</table>

## **3** **结语** ##

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