含义
树广泛用于计算机科学的多个领域，从操作系统、图形学、数据库到计算机网络。
属性：
????????层次性，按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。可以将树的某个
????????????????部分（子树）整体移到另一个位置，而不影响下面的层。
? ? ? ? 一个节点的所有子节点都与另一个节点的所有子节点无关。
? ? ? ? 叶子节点都是独一无二的。
节点：
? ? ? ? 树的基础部分。可以有自己的名字，“键”。可以带有附加信息，称作“有效荷载”。不是重
????????点，但在树的应用中很重要。
边：
? ? ? ? 树的基础部分。两个节点通过一条边相连，表示它们之间存在关系。除了根节点外，
????????其他每个节点都仅有一条入边，可能多条出边。
根节点：
? ? ? ? 唯一没有入边的节点。
路径：
? ? ? ? 由边连接的有序节点列表。
子节点：
? ? ? ? 一个节点通过出边与子节点相连。
父节点：
? ? ? ? 一个节点是其所有子节点的父节点。
兄弟节点：
? ? ? ? 具有同一个父节点的节点互称为兄弟节点。
子树：
? ? ? ? 一个父节点及其所有后代的节点和边构成一棵子树。
叶子节点：
? ? ? ? 没有子节点。
层数：
? ? ? ? 节点n的层数是从根节点到n的唯一路径长度。
高度：
? ? ? ? 其中节点层数的最大值。
?实现
"""
二叉树
BinaryTree() 创建一个二叉树实例。
getLeftChild() 返回当前节点的左子节点所对应的二叉树。
getRightChild() 右子节点所对应的二叉树。
setRootVal(val) 在当前节点中存储参数val中的对象。
getRootVal() 返回当前节点存储的对象。
insertLeft(val) 新建一棵二叉树，并将其作为当前节点的左子节点。
insertRight(val) 新建一棵二叉树，并将其作为当前节点的左子节点。
实现树的关键在于选择一个好的内部存储技巧。
Python：
列表之列表：
表示子树的列表结构符合树的定义，这样的结构是递归的！由一个根节点和两个空列表
构成的子树是一个叶子节点。还有一个很好的性质，那就是这种表示法可以推广到有很
多子树的情况。如果不是二叉树，则多一棵子树只是多一个列表。
"""
# 创建可用于标准列表的函数，将列表作为树使用，正式定义树数据结构。
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)
print(r)
insertLeft(r, 4)
print(r)
insertLeft(r, 5)
print(r)
insertRight(r, 6)
print(r)
insertRight(r, 7)
print(r)
l = getLeftChild(r)
print(l)
setRootVal(l, 9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
树的第二种表示法是利用节点和引用。
"""
这种表示法遵循面向对象编程范式。
如果存在则原来的节点降一级。
"""
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)
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())
|