線索二叉樹的遍歷

n個結點的二叉鏈表中含有空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指針，這種附加的指針稱為"線索"。加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。

二叉樹的遍歷本質上是將一個複雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和後繼，第一個結點無前驅，最後一個結點無後繼。對於二叉樹的一個結點，其前驅後繼只有在遍歷中得到。為了容易找到前驅和後繼，