二叉樹的線索化（C++實現）

2019-11-14 08:54:17

字體：大中小

來源：轉載

供稿：網友

對于一棵二叉樹，我們可以通過前序，中序，后序，層序四種遍歷方式得到關于二叉樹的序列，這樣從每個結點出發就很容易找到它在某種次序下前序和后繼。

PS：關于四種遍歷方式的遞歸和非遞歸實現可點擊我的github 里面的BInaryTree.h查看。

但是很多時候，我們希望很快找到某的結點的前序或者后繼，又不想遍歷一遍，這就需要我們記錄下每個結點的前驅和后繼，因此為了做到這一點，我們引入了二叉樹的線索化。

我們觀察各種二叉樹的結構，發現不管兒叉樹的形態如何，空鏈域的個數總是多過非空鏈域的個數。準確的說，n個結點的指針域共有2n個，非空指針域為n-1個，但其中的空指針域卻有n+1個。這是因為，對于二叉樹的每個結點都有左右孩子，但是每個結點（除根節點）只有一個父親，因此n個結點空指針域為**2n - (n - 1) = n + 1個。比如下圖，其空指針域個數為 2 * 6 - 5 = 7個

這里寫圖片描述

因此我們可以利用這些空指針域來標記結點的前驅或者后繼，規則如下：

若結點有左子樹，則其左指針域指向其左孩子，否則令左指針指向其前驅若結點有右子樹，則其右指針域指向其右孩子，否則令右指針指向其后繼為了區分指針域是指向它的孩子還是前驅（后繼），我們分別加一個標志位（如下圖）

我們給出樹的結點定義如下：

結點結構

enum PointerTag { LINK,THREAD };//LINK表示指向的是左右孩子，THREAD則表示指向前驅或者后繼template<class T>struct BinaryTreeThreadNode{ T _data;//節點數據 BinaryTreeThreadNode<T>* _left;//左孩子 BinaryTreeThreadNode<T>* _right;//右孩子 PointerTag _leftTag;//左孩子線索標志 PointerTag _rightTag;//右孩子線索標志 BinaryTreeThreadNode(const T& x = T()) : _data(x) , _left(nullptr) , _right(nullptr) , _leftTag(LINK) , _rightTag(LINK) {}};

為了實現線索化，我們需要先構建一棵樹，為了簡單，我們采用前序方式構建樹，對于給定的一個數組，如果元素為 ‘#’ 則表明當前結點為空，不然為左子樹。例如：

int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };

所構建的樹如下圖：

這里寫圖片描述

C++代碼如下：

template<class T>class BinaryTreeThread{ typedef BinaryTreeThreadNode<T> Node;public: BinaryTreeThread() : _root(nullptr) {} //前序方式構建二叉樹 BinaryTreeThread(T *a, size_t n, const T& invalid = T()) { assert(a); size_t index = 0; _root = _createTree(a, n, index, invalid); }PRivate: //遞歸建樹 //四個參數含義依次為數組名，數組大小，數組元素下標，無效值比如‘#’ Node *_createTree(T *a, size_t n, size_t& index, const T& invalid = T()) { Node *root = nullptr; if (index < n && a[index] != invalid) { root = new Node(a[index]); root->_left = _createTree(a, n, ++index, invalid); root->_right = _createTree(a, n, ++index, invalid); } return root; }private: Node *_root;};

我們以上面的二叉樹為例建立線索化：

前序線索化

這里寫圖片描述

前序線索化的樹如上圖，下面我們看看如何建立線索化。

實際上線索化的代碼和遍歷代碼結構類似，因為線索化需要在遍歷的時候完成指針之間的連接，也是遵循著前序遍歷的順序，先是根節點然后分別是左子樹右子樹。

以上圖為例，對于1，2來說左右不為空按照前序遍歷的順序來即可，但是遍歷到了3時，由于3的左右為空，我們需要完成3的前驅是2，3的后繼是4這樣的指針連接操作。為了完成這樣的連接操作，我們在實現代碼時候需要記錄一個指向前一個結點的指針prev，比如訪問到3時候，cur指向3，prev指向2，同時將標志位改成THREAD，比如下面的代碼

cur->_left = prev;cur->_leftTag = THREAD;

就完成了3的前驅是4的操作，然而對于3的后繼是4，我們不能記錄個next指針指向下一個結點，因為我們無法預知下一個結點指向哪兒，那該怎么辦？我們知道了前一個結點的指向，因此我們只需要訪問下一個結點時候完成后繼這一步連接：當訪問到4時候，cur指向4，prev指向3，這時候只要

prev->_right = cur;prev->_rightTag = THREAD;

這樣就可以玩成3的后繼是4這一操作了，最后完成當前結點的線索化一定要改變prev為cur。因此完整的前序線索化代碼如下：

void PreOrderThreading(){ Node *prev = nullptr; _preOrderThreading(_root, prev);//_root為根節點}void _preOrderThreading(Node *cur, Node *& prev){ if (cur == nullptr) return; //當前節點的線索化 if (cur->_left == nullptr) { cur->_left = prev; cur->_leftTag = THREAD; } if (prev && prev->_right == nullptr) { prev->_right = cur; prev->_rightTag = THREAD; } prev = cur; //左子樹的線索化 if (cur->_leftTag == LINK) _preOrderThreading(cur->_left, prev); //右子樹的線索化 if (cur->_rightTag == LINK) _preOrderThreading(cur->_right, prev);}

建立前序線索化，我們可以通過前序遍歷看看我們寫的是否是對的？下面分別是遞歸和非遞歸兩種方法的遍歷：

//遞歸遍歷void PreOrder(){ _preOrder(_root); cout << endl;}void _preOrder(Node *root){ if (root == NULL) return; cout << root->_data << " "; if (root->_leftTag == LINK) _preOrder(root->_left); if (root->_rightTag == LINK) _preOrder(root->_right);}//非遞歸遍歷void PreOrderNonR(){ Node *cur = _root; while (cur) { while (cur->_leftTag == LINK) { cout << cur->_data << " "; cur = cur->_left; } cout << cur->_data << " "; cur = cur->_right; //下面這種寫法也可以 //while (cur && cur->_rightTag == THREAD) //{ // cur = cur->_right; // if (cur) // cout << cur->_data << " "; //} //if (cur->_rightTag == LINK) // cur = cur->_right; } cout << endl;}

中序線索化

這里寫圖片描述

中序線索化和前序基本沒什么區別。。。只是需要改變一下順序而已，代碼如下：

void InOrderThreading(){ Node *prev = nullptr; _inOrderThreading(_root, prev);}void _inOrderThreading(Node *cur, Node *& prev){ if (cur == nullptr) return; //左子樹的線索化 if (cur->_leftTag == LINK) _inOrderThreading(cur->_left, prev); //當前結點的線索化 if (cur->_left == nullptr) { cur->_left = prev; cur->_leftTag = THREAD; } if (prev && prev->_right == nullptr) { prev->_right = cur; prev->_rightTag = THREAD; } prev = cur; //右左子樹的線索化 if (cur->_rightTag == LINK) _inOrderThreading(cur->_right, prev);}

而他的遍歷方式如下：

//遞歸遍歷void InOrder(){ _inOrder(_root); cout << endl;}void _inOrder(Node* root){ if (root == NULL) return; if (root->_leftTag == LINK) _inOrder(root->_left); cout << root->_data << " "; if (root->_rightTag == LINK) _inOrder(root->_right);}//非遞歸遍歷void InOrderNonR(){ Node *cur = _root; while (cur) { while (cur->_leftTag == LINK) cur = cur->_left; cout << cur->_data << " "; while (cur && cur->_rightTag == THREAD) { cur = cur->_right; if (cur) cout << cur->_data << " "; } if (cur->_rightTag == LINK) cur = cur->_right; } cout << endl;}