[数据结构与算法]数据结构-树(一)

含义

树广泛用于计算机科学的多个领域，从操作系统、图形学、数据库到计算机网络。

属性：

????????层次性，按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。可以将树的某个

????????????????部分（子树）整体移到另一个位置，而不影响下面的层。

? ? ? ? 一个节点的所有子节点都与另一个节点的所有子节点无关。

? ? ? ? 叶子节点都是独一无二的。

节点：

? ? ? ? 树的基础部分。可以有自己的名字，“键”。可以带有附加信息，称作“有效荷载”。不是重

????????点，但在树的应用中很重要。

边：

? ? ? ? 树的基础部分。两个节点通过一条边相连，表示它们之间存在关系。除了根节点外，

????????其他每个节点都仅有一条入边，可能多条出边。

根节点：

? ? ? ? 唯一没有入边的节点。

路径：

? ? ? ? 由边连接的有序节点列表。

子节点：

? ? ? ? 一个节点通过出边与子节点相连。

父节点：

? ? ? ? 一个节点是其所有子节点的父节点。

兄弟节点：

? ? ? ? 具有同一个父节点的节点互称为兄弟节点。

子树：

? ? ? ? 一个父节点及其所有后代的节点和边构成一棵子树。

叶子节点：

? ? ? ? 没有子节点。

层数：

? ? ? ? 节点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())