树的例子

属性

无论我们在分类树中有多深，都属于根节点
一个节点的所有子节点独立于另一个节点的子节点
每个叶节点是唯一的

词汇和定义

层数

节点 n 的层数为从根结点到该结点所经过的分支数目。

高度

树的高度等于树中任何节点的最大层数。

定义一：树由一组节点和一组连接节点的边组成。树具有以下属性：

从根路径遍历到每个节点路径唯一。
如果树中的每个节点最多有两个子节点，我们说该树是一个二叉树。

定义二（递归定义）：树是空的，或者由一个根节点和零个或多个子树组成，每个子树也是一棵树。

列表表示

在列表树的列表中，我们将根节点的值存储为列表的第一个元素。列表的第二个元素本身将是一个表示左子树的列表。列表的第三个元素将是表示右子树的另一个列表。

 1 myTree = ['a',       #root
 2       ['b',                #left subtree
 3        ['d', [], []],
 4        ['e', [], []] 
 5       ],
 6 
 7       ['c',                #right subtree
 8        ['f', [], []],
 9        [] ]
10       ]