【笔记】
用二叉数表示有多个子女的树：left[x]表示最左边的儿子，right[x]右边的兄弟。
【练习】
10.4-1 画出由下列域表示的、根在下标6处的二叉树。
10.4-2 请写出一个O(n)时间的递归过程，在给定含n个结点的二叉树后，它可以将树中的每个结点的关键字输出来。
void dfs(int x){
printf("%d ",key[x]);
if (l[x]) dfs(l[x]);
if (r[x]) dfs(r[x]);
}10.4-3 请写出一个O(n)时间的非递归过程，将给定的n结点二叉树中每个结点的关键字输出来。可以利用栈作为辅助数据结构。
void output(int rt){
stack<int>s;
s.push(rt);
while (!s.empty()) {
int t = s.top();
s.pop();
printf("%d ",key[t]);
if (r[t]) s.push(r[t]);
if (l[t]) s.push(l[t]);
}
}10.4-4 对于任意的用左孩子、右兄弟表示存储的、含n个结点的有根树，写出一个O(n)时间过程来输出每个结点的关键字。
void dfsTree(int rt) {
printf("%d ",key[rt]);
for (int i=l[rt];i!=0;i=r[i]) dfsTree(i);
}*10.4-5 写出一个O(n)时间的非递归过程，输出给定的含n个结点的二叉树中每个结点的关键字。要求只能使用除树本身以外固定量的额外存储空间，而且在过程中不能修改该树，哪怕是暂时的。
*10.4-6 在任意有根树的左孩子，右兄弟表示中，每个结点有三个指针：left-child，right-sibling和parent。从任意结点出发，都可以在常数时间内到达其父结点；可以在与子女数成线性关系的时间内到达其孩子。说明如何在每个结点内用两个指针和一个布尔值，在与子女数成线性关系的时间内到达其父亲或所有孩子。