python数据结构与算法 37 树的实现
树的实现
记住上一节树的定义，在定义的基础上，我们用以下的函数创建并操作二叉树：
- BinaryTree() 创建一个二叉树实例
- getLeftChild() 返回节点的左孩子
- getRightChild() 返回节点的右孩子
- setRootVal(val) 把val变量值赋给当前节点
- getRootVal() 返回当前节点对象。
- insertLeft(val) 创建一个新二叉树作为当前节点的左孩子
- insertRight(val) 创建一个新二叉树作为当前节点的右孩子。
实现树的关键点是合适的存储技术。Python提供两种可用方法，所以在做出决定之前，先查验一下两种技术。第一种叫“列表的列表”，第二种叫“节点与引用”
列表的列表表示法
在列表的列表方法中，我们使用列表数据结构来实现上面的函数，虽然这种操作方法与我们以前的抽象数据结构很不相同，不过它很有意思的一点是，这是一个简单的递归结构，我们可以直接查看和检查。
在列表的列表树中，根节点的数值是列表的第一个元素，第二个元素是它的左子树，第三个元素就是它的右子树。为说明这个存储结构，我们看一个例子。图1所示为一个如此实现的简单树。
myTree = [‘a‘, #root
[‘b‘, #left subtree
[‘d‘ [], []],
[‘e‘ [], []] ],
[‘c‘, #right subtree
[‘f‘ [], []],
[] ]
]
有没有发现我们可以直接用列表的索引来访问子树。树根是myTree[0],左子树是myTree[1],右子树是myTree[2]。下面的代码就是用列表创建了一棵树，完成之后，就可以访问它的根和子树，它的好处在于列表中的“元素列表”就代表了子树，与树有相同的结构，所以它的结构是递归的。如果一个子树有根节点，但是左右子树都是空列表，那么它就是叶子。另一个好处是这种方法产生的树可以推广到“多叉树”而不仅是二叉树，因为另一个子树也不过是一个列表而已。
myTree = [‘a‘, [‘b‘, [‘d‘,[],[]], [‘e‘,[],[]] ], [‘c‘, [‘f‘,[],[]], []] ] print(myTree) print(‘left subtree = ‘, myTree[1]) print(‘root = ‘, myTree[0]) print(‘right subtree = ‘, myTree[2])
现在来为这种树形数据结构定义一些函数以方便使用。注意我们没有定义一个二叉树类，这些函数只是帮助操作一个列表，即使工作对象是一个树。
def BinaryTree(r):
return [r, [], []]
BinaryTree函数简单地创建了一个列表，内中只有一个根节点和两个空列表作为孩子。要增加左子树的话，就要插入一个新列表到根列表的第二个位置上。要小心一点，如果第二个位置上已经保存了数据，需要跟踪这个数据，并把它下压一级，作为新插入列表的左孩子。Listing1是插入左孩子的代码。
Listing 1
def insertLeft(root,newBranch):
t= root.pop(1)
iflen(t) >1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root
注意，要插入左孩子，先得到原来左孩子位置的列表（可能是空的），当加入新左孩子的时候，把原来的左孩子作为新节点的孩子。这样，我们可以把新节点放在树中任何位置。
插入右孩子的代码也很相似，见下面listing 2.
Listing 2
def insertRight(root,newBranch):
t= root.pop(2)
iflen(t) >1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
下面listing 3是获取和赋值的函数，针对根节点和左右子树。
Listing 3
defgetRootVal(root):
return root[0]
defsetRootVal(root,newVal):
root[0] = newVal
defgetLeftChild(root):
return root[1]
defgetRightChild(root):
return root[2]
下面是完整的函数代码。
def BinaryTree(r):
return [r, [], []]
def insertLeft(root,newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root
def insertRight(root,newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
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]
r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)
setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
节点与引用方法
第二种表示方法使用节点和引用。在这种情况下我们定义一个类，它的属性值包括根，和左右子树。因为这种方法更加面向对象，以后的章节中，我们都用这种表示方法。
使用节点和引用，我们认为树形结构类似图2所示。
开始时如linsting 4所示，只是一个节点的定义和两个子树的引用。重要的是，左右子树的引用的，也是这个类的实例。例如，如果要插入一个新的左子树，那么创建一个新的树对象并且修改根节点的self.leftChild指向新树
Listing4
classBinaryTree:
def__init__(self,rootObj):
self.key= rootObj
self.leftChild=None
self.rightChild=None
注意上面代码中，构造函数需要一个对象来保存在根节点。既然列表可以保存任意对象，那么树的根可以是任意对象。在前面的例子中，我们在根节点中保存节点的名字。在图2中那样的树，我们要创建6个BinaryTree的对象。
下面看另外的函数。要在树中增加一个左子树，需要新建一个二叉树对象，并把这个对象赋值给leftChild。下面是实现代码。
Listing5
1
2
3
4
5
6
7
|
definsertLeft(self,newNode): ifself.leftChild==None: self.leftChild= BinaryTree(newNode) else: t = BinaryTree(newNode) t.leftChild=self.leftChild self.leftChild= t |
上面代码中考虑了两种情况。第一种是没有左孩子，只需把节点加到树上。第二种是此节点已经有左孩子，这时要把现存的左孩子下移一级作为插入节点的左孩子。第二种情况是在上面代码中第4行的else语句处理的。
插入右孩子的操作也要对称地考虑，要么没有右孩子，否则把节点插入到根与现存右孩子之间。如下面的listing 6
Listing6
definsertRight(self,newNode):
ifself.rightChild==None:
self.rightChild= BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild=self.rightChild
self.rightChild= t
同样的，下面的函数是用来取值和赋值的。
Listing7
defgetRightChild(self):
returnself.rightChild
defgetLeftChild(self):
returnself.leftChild
defsetRootVal(self,obj):
self.key= obj
defgetRootVal(self):
returnself.key
现在我们完成了创建和操作树所需要的全部程序段，现在用它们来验证一下他们树的结构。我们先创建一个简单的树包含一个根和两个节点，b和c。下面的代码就是创建树，并为键，左孩子和右孩子赋值。注意左孩子和右孩子和根都是同一个类BinaryTree的不同对象，如同前面我们的递归定义一样，这使得我们可以象处理二叉树一样处理它的子树。
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
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())
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
