第10章 10.4 有根树的表示

# 一、概念 ### 1.二叉树 （1）用域p、left、right来存放指向二叉树T中的父亲、左儿子、右儿子。没有则为NULL。 （2）结点结构 ~~~ struct node { node *p; node *left; node *right; int key; }; ~~~ （3）树的结构 ~~~ struct Bin_Tree { node *head; }; ~~~ ### 2.分支数无限的有根树 （1）左孩子右兄弟表示法 （2）结点结构 ~~~ struct node { node *p; node *left_child; node *right_sibling; int key; }; ~~~ （3）树的结构 ~~~ struct Tree { node *head; }; ~~~ # 二、练习 10.4-2 [算法导论 10.4-2 O(n)时间 递归遍历二叉树](http://blog.csdn.net/mishifangxiangdefeng/article/details/39010925) ~~~ TREE-PRINT(T) 1 print key[T] 2 if left[T] != NIL 3 TREE-PRINT(left[T]) 4 if right[T] != NIL 5 TREE-PRINT(right[T]) ~~~ 10.4-3 [算法导论 10.4-3 O(n) 二叉树 非递归遍历](http://blog.csdn.net/mishifangxiangdefeng/article/details/39012249) ~~~ TREE-PRINT(T, S) 1 print key[T] 2 PUSH(S, T) 3 while true 4 if left[T] != NIL 5 then T <- left[T] 6 else 7 do 8 T = POP(S) 9 if T = NIL 10 then return 11 while left[T] = NIL 12 T <- right[T] ~~~ 10.4-4 与二叉树的遍历过程相同 10.4-5 见[算法导论-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490) 采用类似中序遍历的处理方法，对一个结点，可以分为以下几种情况 1.从父结点进入子结点进行处理 （1）如果有左孩子，就处理左孩子 （2）返回到自己 （3）访问自己 （4）如果有右孩子，就处理右孩子 （5）返回到自己的父结点 2.从左孩子返回，说明左孩子已经处理过，自己还没访问，自己的右孩子也没有处理过，就进行1-（2） 3.从右孩子返回，说明左右孩子都已经处理，自己也访问过，就返回到更上层 4.返回到根结点时，遍历结束 10.4-6 去掉parent指针，当布尔值为1时，rightchild指向父结点，当布尔值为0值，rightchild指向右兄弟，其余用法保持不变