# 一、概念 ### 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指向右兄弟，其余用法保持不變