c語言二叉樹(留存版)

　　

【正文】 parent。 //指向下一孩子結點 }JD。 struct node *lchild, *rchild, *parent。 struct node *fch, *nsib。雙親域：指示本結點的雙親結點在數組中位置 –特點： 找雙親容易，找孩子難 typedef struct node { datatype data。 表頭結點： typedef struct tnode { datatype data。 }JD。破壞了樹的層次 typedef struct node { datatype data。數據域：存放結點本身信息 187。 //數據域 struct node *fc。 lchild data parent rchild A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ 二叉樹的存儲結構 –樹的遍歷 ? 遍歷 ——按 一定規律 走遍樹的各個頂點，且使每一頂點僅 被訪問一次 ，即找一個完整而有規律的走法，以得到樹中所有結點的一個線性排列 ? 常用方法 –先根 （序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹 –后根 （序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點 –按 層次 遍歷：先訪問第一層上的結點，然后依次遍歷第二層， ……第 n層的結點 樹的遍歷 A B C D E F G H I J K L M N O 先序遍歷： 后序遍歷： 層次遍歷： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O 樹的遍歷 ? 方法 –先 序遍歷：先訪問根結點 ,然后分別先序遍歷左子樹、右子樹 –中 序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹 –后 序遍歷：先后序遍歷左、右子樹，然后訪問根結點 –按 層次 遍歷：從上到下、從左到右訪問各結點 D L R LDR、 LRD、 DLR 二叉樹的遍歷 D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C A D B C 先序遍歷 : 二叉樹的遍歷 L D R B L D