- Python算法详解
- 张玲玲
- 460字
- 2020-06-27 17:50:53
5.3.4 实践演练——使用嵌套列表表示树
下面的实例文件qian.py演示了使用嵌套列表表示树的过程。
源码路径：daima\第5章\qian.py
（1）通过如下代码构建一棵二叉树，该二叉树只是构建包含一个根节点和两个空子节点的列表。为了将左子树添加到树的根，我们需要插入一个新的列表到根列表的第二个位置。我们必须注意，如果列表中已经有值在第二个位置，我们需要跟踪它，将新节点插入树中作为其直接的左子节点。
def BinaryTree(r):
return [r, [], []]
（2）通过如下insertLeft()函数插入一个左子节点，首先判断当前左子节点的列表（可能是空的）长度是否大于1。如果大于1，在添加新的左子节点后，将原来的左子节点作为新节点的左子节点。这使我们能够将新节点插入到树中的任何位置。
def insertLeft(root,newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root
（3）通过如下代码插入一个右子节点，具体原理和上面的插入左子节点相同。
def insertRight(root,newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
（4）为了完善树的实现，编写如下几个用于获取和设置根值的函数，以及几个用于获得左边或右边子树的函数。
def getRootVal(root):
return root[0]
def setRootVal(root,newVal):
root[0] = newVal
def getLeftChild(root):
return root[1]
def getRightChild(root):
return root[2]
（5）通过如下代码进行测试：
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())
执行后会输出：
a None <__main__.BinaryTree object at 0x00000221FC779AC8> b <__main__.BinaryTree object at 0x00000221FC779B00> c hello