1. 树的定义
特点： ① 层次化② 叶节点独一性③ 不同节点的子节点相互独立
2. 结构：
- 节点Node：节点具有名称，也可以存储数据
- 边Edge： 连接两个节点，具有出入方向，表示节点之间的关系
- Root根：没有入边的节点
- Path路径： 由边连接的节点的有序列表
- 子节点Childern、父节点、叶节点、兄弟节点、子树
- 层级： 从根节点到达一个节点路径包括的边的数量
- 高度：所有节点的最大层级，根节点高度从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
