树及树的使用方法

1. 树的定义

特点： ① 层次化② 叶节点独一性③ 不同节点的子节点相互独立

2. 结构：

1. 节点Node：节点具有名称，也可以存储数据
2. 边Edge： 连接两个节点，具有出入方向，表示节点之间的关系
3. Root根：没有入边的节点
4. Path路径： 由边连接的节点的有序列表
5. 子节点Childern、父节点、叶节点、兄弟节点、子树
6. 层级： 从根节点到达一个节点路径包括的边的数量
7. 高度：所有节点的最大层级，根节点高度从0开始

3. 二叉树

每个节点最多有两个子节点

代码实现：

# ————————树的嵌套列表法————————
def BinaryTree(r):
    return [r, [], []]


def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
        # 若存在左节点，则新插入左节点介于root与左节点中，原先的左节点为现在新插入节点的左节点
    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, new_val):
    root[0] = new_val


def getleftChildren(root):
    return root[1]


def getrightChildren(root):
    return root[2]


# ————————树的节点链表法————————
class BinaryTree:
    def __init__(self,rootObj):
        self.val = rootObj
        self.left = None
        self.right = None

    def insertLeft(self, newNode):
        if self.left is None:
            self.left = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.left
            self.left = t

    def rightRight(self, newNode):
        if self.right is None:
            self.right = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.right
            self.right = t

    def getRight(self):
        return self.right

    def getLeft(self):
        return self.left

    def setRootVal(self, newval):
        self.val = newval

    def getRootVal(self):
        return self.val

附：大家可能都知道二叉树中叶子节点（度为0）与度为2的节点数的关系为

度为2节点数 = 叶子节点数 - 1

但是知道为什么的人却不多，下面就是这个定理的证明

树（不仅仅是二叉树）中每个节点头上都有一个支路，但唯独有一个是例外——根节点

所以我们可以得到树的一个重要结论①：

树支路总数 = 树节点总数 - 1
支路总数怎么计算？

设度为 i 的节点有 xi 个，所以支路总数等于 Σ i * xi

二叉树的度只有0，1，2

带入重要结论①所以有：

0x0 + 1x1 + 2*x2 = x0 + x1 + x2 - 1

两边稍微计算一下得出：

x2 = x0 - 1