树及其Python的简单实现

二叉树T

维基百科：二叉树

特性

1. 每个树结点x含有一个关键字key
2. 树结点x的属性p, left和right分别存放指向父结点、左孩子和右孩子的指针
3. 如果x.p = NIL,则x是根结点
4. 若结点x没有左孩子，则x.left = NIL；若结点x没有右孩子，则x.right = NIL
5. 属性T.root指向整棵树T的根结点。若T.root = NIL，则该树为空。

分支无限制的有根树T

对于每个结点的孩子数至多为常数k的任意类型的树，使用左孩子有兄弟表示法(left-child, right-sibling representation)： 1. 每个结点x都包含一个父结点指针p，T.root指向树T的根结点 2. 每个结点x只有两个指针： * x.left-child指向结点x最左边的孩子结点 * x.right-sibling指向x右侧相邻的兄弟结点 * 若结点x没有孩子结点，则x.left-child = NIL；若结点x是其父结点的最右孩子，则x.right-sibling = NIL。