C語言數據結構 中序二叉樹
前言：
線索二叉樹主要是為了解決查找結點的線性前驅與后繼不方便的難題。它只增加了兩個標志性域，就可以充分利用沒有左或右孩子的結點的左右孩子的存儲空間來存放該結點的線性前驅結點與線性后繼結點。兩個標志性域所占用的空間是極少的，所有充分利用了二叉鏈表中空閑存的儲空間。
要實現線索二叉樹，就必須定義二叉鏈表結點數據結構如下（定義請看代碼）：
| left | leftTag | data | rightTag | right |
說明：
1. leftTag=false時，表示left指向該結點的左孩子；
2. leftTag=true時，表示left指向該結點的線性前驅結點；
3. rightTag=false時，表示right指向該結點的右孩子；
4. rightTag=true時，表示right指向該結點的線性后繼結點；
以二叉鏈表結點數據結構所構成的二叉鏈表作為二叉樹的存儲結構，叫做線索二叉鏈表；指向結點的線性前驅或者線性后繼結點的指針叫做線索；加上線索的二叉樹稱為線索二叉樹；對二叉樹以某種次序遍歷將其變為線索二叉樹的過程叫做線索化。
中序次序線索化二叉樹算法：
中序次序線索化是指用二叉鏈表結點數據結構建立二叉樹的二叉鏈表，然后按照中序遍歷的方法訪問結點時建立線索；(具體看代碼)
檢索中序二叉樹某結點的線性前驅結點的算法：
1. 如果該結點的leftTag=true,那么left就是它的線性前驅；
2. 如果該結點的leftTag=false，那么該結點左子樹最右邊的尾結點就是它的線性前驅點；
（具體請看代碼）
檢索中序二叉樹某結點的線性后繼結點和算法：
1. 如果該結點的right=true,那么right就是它的線性后繼結點；
2. 如果該結點的right=false,那么該結點右子樹最左邊的尾結點就是它的線性后繼結點
（具體請看代碼）
圖：后繼線索
圖：前驅線索
節點定義：
struct Node { int data; bool leftTag; bool rightTag; Node* left; Node* right; Node(int _data):data(_data),left(0),right(0),leftTag(false),rightTag(false){} }; 類定義：
class BinaryTree { private: Node* root; private: Node* head; Node* pre; void makeThread(Node* node); public: void buildThread(); void traverseBySuccessor(); void traverseByPredecessor(); // helper methods private: static inline bool visit(Node* T) { if (T) { printf("data:%c, left:%c, right:%c/n", (char)T->data, (T->left!=0) ? (char)T->left->data : '#', (T->right!=0) ? (char)T->right->data : '#'); return true; } else return false; } }; 方法定義：
void BinaryTree::makeThread(Node* node) { if (node!=NULL) { makeThread(node->left); if (pre!= NULL) { if (pre->right==NULL) // 如果前驅節點的右子樹為空, 那么把前驅節點的右子樹用作線索 { pre->rightTag = true; pre->right = node; } else pre->rightTag = false; } if (node->left==NULL) // 如果當前結點的左子樹為空, 那么把當前結點的左子樹用作線索 { node->leftTag = true; node->left = pre; } else node->leftTag = false; pre = node; makeThread(node->right); } } void BinaryTree::traverseBySuccessor() { Node* p = head->left; //first find the root node // 親測表明 如果不使用head啞節點 就要設三道卡, 防止p訪問到NULL, // 分別在主while處, 第二個visit處和下面的p=p->right處 while (p!=head) { while (!p->leftTag) p = p->left; visit(p); while (p->rightTag && p->right!=head) { p = p->right; visit(p); } p = p->right; } cout<<endl; } void BinaryTree::traverseByPredecessor() { Node* p = head->left; //first find the root node while (p!=head) { while (!p->rightTag) p = p->right; visit(p); if (p!=NULL) { while (p->leftTag && p->left!=head) { p = p->left; visit(p); } p = p->left; } } cout<<endl; } void BinaryTree::buildThread() { pre = NULL; head = new Node('@'); head->left = root; head->right = head; makeThread(root); // 經過了makeThread過程之后, pre必然指向中序遍歷最晚的結點. // 把pre的右子樹指向head, 就構成了一個雙向循環鏈表 // pre->rightTag = 1; pre->right = head; pre = NULL; Node* p = root; /* * 在建立前驅線索的時候，最左邊的結點沒有和head結點連接。要在這里補上 */ while (p->left!=NULL) p = p->left; p->left = head; } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
