_23Threaded BinaryTree

可編譯運(yùn)行代碼見(jiàn)：GIithub::Data-Structures-Algorithms-and-Applications/_24Threaded_BinaryTree

線索二叉樹(shù)定義

在普通二叉樹(shù)中，有很多nullptr指針被浪費(fèi)了，可以將其利用起來(lái)。

首先我們要來(lái)看看這空指針有多少個(gè)呢？對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉鏈表，每個(gè)結(jié)點(diǎn)有指向左右孩子的兩個(gè)指針域，所以一共是2n個(gè)指針域。而n個(gè)結(jié)點(diǎn)的二叉樹(shù)一共有n-1條分支線數(shù)，也就是說(shuō)，其實(shí)是存在2n-（n-1）=n+1個(gè)空指針域。

對(duì)上圖**(參考：《大話數(shù)據(jù)結(jié)構(gòu) 溢彩加強(qiáng)版 程杰》160頁(yè)圖)**做中序遍歷，得到了HDIBJEAFCG這樣的字符序列，遍歷過(guò)后，我們可以知道，結(jié)點(diǎn)I的前驅(qū)是D，后繼是B，結(jié)點(diǎn)F的前驅(qū)是A，后繼是C。也就是說(shuō)，我們可以很清楚地知道任意一個(gè)結(jié)點(diǎn)，它的前驅(qū)和后繼是哪一個(gè)結(jié)點(diǎn)。

可是這是建立在已經(jīng)遍歷過(guò)的基礎(chǔ)之上的。在二叉鏈表上，我們只能知道每個(gè)結(jié)點(diǎn)指向其左右孩子結(jié)點(diǎn)的地址，而不知道某個(gè)結(jié)點(diǎn)的前驅(qū)是誰(shuí)，后繼是誰(shuí)。要想知道，必須遍歷一次。以后每次需要知道時(shí)，都必須先遍歷一次。這樣比較浪費(fèi)時(shí)間。

我們可以考慮利用那些空地址，存放指向結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的地址。我們把這種指向前驅(qū)和后繼的指針?lè)Q為線索，加上線索的二叉鏈表稱(chēng)為線索鏈表，相應(yīng)的二叉樹(shù)就稱(chēng)為線索二叉樹(shù)（Threaded Binary Tree）。

我們把二叉樹(shù)進(jìn)行中序遍歷后，將所有的空指針域中的rchild，改為指向它的后繼結(jié)點(diǎn)。將所有空指針域中的lchild，改為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)。由此得出，經(jīng)過(guò)線索化的二叉樹(shù)變成了一個(gè)雙向鏈表。雙向鏈表相比于二叉樹(shù)更容易找到某節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)。因此，如果所用的二叉樹(shù)需經(jīng)常遍歷或查找結(jié)點(diǎn)時(shí)需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲(chǔ)結(jié)構(gòu)就是非常不錯(cuò)的選擇。

但是還有一個(gè)問(wèn)題，如果將這些空指針作為線索后無(wú)法區(qū)分該指針是線索還是指向孩子節(jié)點(diǎn)，因此需要標(biāo)志位LTag為T(mén)rue表示該節(jié)點(diǎn)的左指針是索引，RLag為true表示該節(jié)點(diǎn)的右指針是索引，反之不是索引。

代碼

main.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹(shù)
*/
#include "inThreadedBinaryTreeChains.h"
int main() {inThreadedBinaryTreeChainsTest();return 0;
}

inThreadedBinaryTreeChains.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹(shù)鏈表表示
*/#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#include <iostream>
#include "binaryTree.h"
#include "inThreadedBinaryTreeNode.h"
using namespace std;
/*二叉樹(shù)基礎(chǔ)測(cè)試函數(shù)*/
void inThreadedBinaryTreeChainsTest();
template<class E>
class inThreadedBinaryTreeChains : public binaryTree<inThreadedBinaryTreeNode<E>>
{
public:/*二叉樹(shù)的基礎(chǔ)成員函數(shù)*//*構(gòu)造函數(shù)函數(shù)*/inThreadedBinaryTreeChains() {root = nullptr; treeSize = 0;}/*析構(gòu)函數(shù)*/~inThreadedBinaryTreeChains() { erase(); }/*當(dāng)樹(shù)為空時(shí)，返回true；否則，返回false*/bool empty() const { return treeSize == 0; }/*返回元素個(gè)數(shù)*/int size() const { return treeSize; }void inOrderThreaded()  // 中序遍歷索引，就是中序遍歷的時(shí)候添加索引{pre = nullptr;inOrderThreaded(root);}/*中序遍歷二叉樹(shù)，使用函數(shù)指針的目的是是的本函數(shù)可以實(shí)現(xiàn)多種目的*/void inOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*)){visit = theVisit;/*是因?yàn)檫f歸，所以才要這樣的*/inOrder(root);/*這里調(diào)用的是靜態(tài)成員函數(shù)inOrder()*/}/*中序遍歷---輸出endl*/void inOrderOutput() { inOrder(output); cout << endl; }/*后續(xù)遍歷二叉樹(shù)，使用函數(shù)指針的目的是是的本函數(shù)可以實(shí)現(xiàn)多種目的*/void postOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*)){visit = theVisit;/*是因?yàn)檫f歸，所以才要這樣的*/postOrder(root);/*這里調(diào)用的是靜態(tài)成員函數(shù)inOrder()*/}/*后序遍歷---輸出endl*/void postOrderOutput() { postOrder(output); cout << endl; }/*清空二叉樹(shù) 這里必須使用后序遍歷 不然會(huì)出錯(cuò)*/void erase(){postOrder(dispose);root = nullptr;treeSize = 0;}/*輸入時(shí)為了將root根節(jié)點(diǎn)傳遞給createBiTree()函數(shù)*/void input(void){createBiTree(root);}
private:
/*二叉樹(shù)基礎(chǔ)私有成員*/inThreadedBinaryTreeNode<E>* root;//指向根的指針int treeSize;//樹(shù)的結(jié)點(diǎn)個(gè)數(shù)static inThreadedBinaryTreeNode<E>* pre;// 在線索化時(shí)使用的前驅(qū)tempstatic void (*visit)(inThreadedBinaryTreeNode<E>*);//是一個(gè)函數(shù)指針,返回值為void 函數(shù)參數(shù)為binaryTreeNode<E>*static void inOrder(inThreadedBinaryTreeNode<E>* t);static void inOrderThreaded(inThreadedBinaryTreeNode<E>* t);// 中序遍歷索引，就是中序遍歷的時(shí)候添加索引static void postOrder(inThreadedBinaryTreeNode<E>* t);static void dispose(inThreadedBinaryTreeNode<E>* t) { delete t; }static void output(inThreadedBinaryTreeNode<E>* t) { cout << t->element << " "; }/*創(chuàng)建二叉樹(shù)---遞歸---作為私有成員只能被成員函數(shù)調(diào)用*/void createBiTree(inThreadedBinaryTreeNode<E>*& tree);
};
/*私有靜態(tài)成員初始化*/
/*這里是靜態(tài)函數(shù)指針成員的初始化，不初始化會(huì)引發(fā)LINK錯(cuò)誤*/
template<class E>
void (*inThreadedBinaryTreeChains<E>::visit)(inThreadedBinaryTreeNode<E>*) = 0;      // visit function
// 這個(gè)地方需要做一個(gè)初始化，不做的話就會(huì)bug
template<class E>
inThreadedBinaryTreeNode<E>* inThreadedBinaryTreeChains<E>:: pre = nullptr;
/*中序遍歷 遞歸*/
/*不受索引影響的中序遍歷*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrder(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){// 在其左孩子不是索引時(shí)遍歷if(!t->LTag)inOrder(t->leftChild);/*中序遍歷左子樹(shù)*/visit(t);/*訪問(wèn)樹(shù)根*/// 在其右孩子不是索引時(shí)遍歷if(!t->RTag)inOrder(t->rightChild);/*中序遍歷右子樹(shù)*/}
}
/*中序遍歷索引 遞歸*/
/*本文寫(xiě)法可以保證在多次調(diào)用此函數(shù)下依然能正常執(zhí)行，當(dāng)插入新元素后再執(zhí)行本函數(shù)可更新節(jié)點(diǎn)的索引*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrderThreaded(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){if(!t->LTag)inOrderThreaded(t->leftChild);/*中序遍歷左子樹(shù)*/if(!t->leftChild || t->LTag) // 沒(méi)有左孩子，或者是第二次遍歷即左孩子指向了他的前驅(qū){t->LTag = true;t->leftChild = pre;}if(pre){if(!pre->rightChild || t->RTag)  // 如果前驅(qū)沒(méi)有右孩子，或者是第二次遍歷即右孩子指向了它的后繼{pre->RTag = true;pre->rightChild = t;}}pre = t;if(!t->RTag)inOrderThreaded(t->rightChild);/*中序遍歷右子樹(shù)*/}
}
/*后序遍歷 遞歸*/
/*不受索引影響的后序遍歷*/
template<class E>
void inThreadedBinaryTreeChains<E>::postOrder(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){// 在其左孩子不是索引時(shí)遍歷if(!t->LTag)postOrder(t->leftChild);/*后序遍歷左子樹(shù)*/// 在其右孩子不是索引時(shí)遍歷if(!t->LTag)postOrder(t->rightChild);/*后序遍歷右子樹(shù)*/visit(t);/*訪問(wèn)樹(shù)根*/}
}/*創(chuàng)建二叉樹(shù)---遞歸---模板的實(shí)現(xiàn)*/
template<class E>
void inThreadedBinaryTreeChains<E>::createBiTree(inThreadedBinaryTreeNode<E>*& tree)
{E data;cout << "Please enter the tree element:";while (!(cin >> data)){cin.clear();//清空標(biāo)志位while (cin.get() != '\n')//刪除無(wú)效的輸入continue;cout << "Please enter the tree element:";}cin.get();/*針對(duì)char類(lèi)型的特例*/if (typeid(data) == typeid(char)) {if (data == '#')tree = nullptr;else {treeSize++;tree = new inThreadedBinaryTreeNode<E>(data);createBiTree(tree->leftChild);createBiTree(tree->rightChild);}}else/*針對(duì)其他類(lèi)型*/{if (data == 999)tree = nullptr;//當(dāng)遇到999時(shí)，令樹(shù)的根節(jié)點(diǎn)為nullptr,從而結(jié)束該分支的遞歸else{treeSize++;tree = new inThreadedBinaryTreeNode<E>(data);createBiTree(tree->leftChild);createBiTree(tree->rightChild);}}
}
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H

inThreadedBinaryTreeChains.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹(shù)測(cè)試函數(shù)
*/
#include "inThreadedBinaryTreeChains.h"
void inThreadedBinaryTreeChainsTest(){cout << endl << "******************************inThreadedBinaryTreeChains()函數(shù)開(kāi)始**********************************" << endl;cout << endl << "測(cè)試成員函數(shù)*******************************************" << endl;cout << "輸入****************************" << endl;cout << "默認(rèn)構(gòu)造函數(shù)********************" << endl;inThreadedBinaryTreeChains<int> a;a.input();cout << "輸出****************************" << endl;cout << "中序輸出************************" << endl;//遞歸遍歷a.inOrderThreaded();cout << "a.inOrderOutput() = ";a.inOrderOutput();cout << "后序輸出************************" << endl;a.inOrderThreaded();cout << "a.postOrderOutput() = ";a.postOrderOutput();cout << "empty()*************************" << endl;cout << "a.empty() = " << a.empty() << endl;cout << "size()**************************" << endl;cout << "a.size() = " << a.size() << endl;cout << "erase()**************************" << endl;a.erase();cout << "a.inOrderOutput() = ";a.inOrderOutput();cout << "******************************inThreadedBinaryTreeChains()函數(shù)結(jié)束**********************************" << endl;
}

binaryTree.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月27日09點(diǎn)43分
Last Version:			V1.0
Descriptions:			二叉樹(shù)的抽象類(lèi)
*/#ifndef _24THREADED_BINARYTREE_BINARYTREE_H
#define _24THREADED_BINARYTREE_BINARYTREE_H
template<class T>
class binaryTree
{
public:virtual ~binaryTree() {}virtual bool empty() const = 0;virtual int size() const = 0;
//    virtual void preOrder(void (*)(T*)) = 0;virtual void inOrder(void (*)(T*)) = 0;virtual void postOrder(void (*)(T*)) = 0;
//    virtual void levelOrder(void (*)(T*)) = 0;
};
#endif //_24THREADED_BINARYTREE_BINARYTREE_H

inThreadedBinaryTreeNode.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體
*/#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
template<class T>
struct inThreadedBinaryTreeNode
{T element;inThreadedBinaryTreeNode<T>* leftChild,//左子樹(shù)*rightChild;//右子樹(shù)bool LTag, RTag;// 左右子樹(shù)指針是否為索引，為T(mén)rue則是索引，否則不是索引/*默認(rèn)構(gòu)造函數(shù)*/inThreadedBinaryTreeNode() { leftChild = rightChild = nullptr; LTag = RTag = false;}/*只初始化element*/inThreadedBinaryTreeNode(T melement){element = melement;leftChild = rightChild = nullptr;LTag = RTag = false;}/*三個(gè)元素都初始化*/inThreadedBinaryTreeNode(T melement, inThreadedBinaryTreeNode<T>* mleftChild, inThreadedBinaryTreeNode<T>* mrightChild){element = melement;leftChild = mleftChild;rightChild = mrightChild;LTag = RTag = false;}
};
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H

測(cè)試

"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_24Threaded BinaryTree\cmake-build-debug\_24Threaded_BinaryTree.exe"******************************inThreadedBinaryTreeChains()函數(shù)開(kāi)始**********************************測(cè)試成員函數(shù)*******************************************
輸入****************************
默認(rèn)構(gòu)造函數(shù)********************
Please enter the tree element:1
Please enter the tree element:2
Please enter the tree element:999
Please enter the tree element:999
Please enter the tree element:3
Please enter the tree element:999
Please enter the tree element:999
輸出****************************
中序輸出************************
a.inOrderOutput() = 2 1 3
后序輸出************************
a.postOrderOutput() = 2 3 1
empty()*************************
a.empty() = 0
size()**************************
a.size() = 3
erase()**************************
a.inOrderOutput() =
******************************inThreadedBinaryTreeChains()函數(shù)結(jié)束**********************************Process finished with exit code 0