引言：
????????線索二叉樹是一種特殊的二叉樹，它可以通過線索（線索是指在二叉樹中將空指針改為指向前驅或后繼的指針）的方式將二叉樹轉化為一個線性結構，從而方便對二叉樹進行遍歷。本文將介紹如何使用C++實現線索二叉樹。
技術實現：
????????首先，我們需要定義一個結構體來表示線索二叉樹的節點。結構體中包含了節點的數據、左右子節點以及左右線索標記。
template<typename Element>
struct ThrNode
{Element data;ThrNode* lchild;ThrNode* rchild;int lTag;int rTag;
};
????????其中，lTag和rTag分別表示左右線索標記。如果lTag為0，則表示該節點的左子節點為普通子節點；如果lTag為1，則表示該節點的左子節點為前驅節點。rTag同理。
接下來，我們使用一個類來表示線索二叉樹。該類中包含了根節點以及一些方法。
template<typename Element>
class InThrBiTree
{
public:InThrBiTree();~InThrBiTree();void inOrder();
private:ThrNode<Element>* root;void createTree(ThrNode<Element>*& node);void destroyTree(ThrNode<Element>* node);ThrNode<Element>* first(ThrNode<Element>*node);ThrNode<Element>* next(ThrNode<Element>* node);void createInThread(ThrNode<Element>*& node, ThrNode<Element>*& pre);
};
????????其中，createTree方法用于創建線索二叉樹，destroyTree方法用于銷毀線索二叉樹，inOrder方法用于中序遍歷線索二叉樹。first方法用于找到中序遍歷的第一個節點，next方法用于找到中序遍歷中的下一個節點。createInThread方法用于創建中序遍歷的線索。
接下來看怎么實現：
template<typename Element>
InThrBiTree<Element>::InThrBiTree()
{createTree(root);ThrNode<Element>* pre = nullptr;if (root != nullptr){createInThread(root, pre);pre->rTag = 1;}
}template<typename Element>
InThrBiTree<Element>::~InThrBiTree()
{destroyTree(node);
}template<typename Element>
void InThrBiTree<Element>::inOrder()
{ThrNode<Element>* p = first(p);while (p != nullptr) {cout << p->data << " ";p = next(p);}cout << endl;
}template<typename Element>
void InThrBiTree<Element>::createTree(ThrNode<Element>*& node)
{char item;cin >> item;if (item == '#')node = nullptr;else {node = new BiNode<Element>;node->data = item;createTree(node->lchild);createTree(node->rchild);}
}template<typename Element>
void InThrBiTree<Element>::destroyTree(ThrNode<Element>* node)
{if(node!=nullptr){destroyTree(node->lchild);destroyTree(node->rchild);delete node;}
}template<typename Element>
ThrNode<Element>* InThrBiTree<Element>::first(ThrNode<Element>* node)
{ThrNode<Element>* p = node;while (p->lTag == 0)p = p->lchild;return p;
}template<typename Element>
ThrNode<Element>* InThrBiTree<Element>::next(ThrNode<Element>* node)
{ThrNode<Element>* p = node->rchild;if (node->rTag == 1) {return p;}else {return first(p);}
}template<typename Element>
inline void InThrBiTree<Element>::createInThread(ThrNode<Element>*& node, ThrNode<Element>*& pre)
{if (node == nullptr) return;createInThread(node->lchild, pre);if (node->lchild == nullptr){node->lchild = pre;node->lTag = 1;}if (pre != nullptr && pre->rchild == nullptr){pre->rchild = node;pre->rTag = 1;}pre = node;createInThread(node->rchild, pre);
}最后，我們來看一下如何使用該類來創建和遍歷線索二叉樹。
int main()
{InThrBiTree<int> tree;tree.createTree(tree.root);tree.createInThread(tree.root, nullptr);tree.inOrder();tree.destroyTree(tree.root);return 0;
}????????首先創建一個InThrBiTree對象，然后調用createTree方法創建線索二叉樹，接著調用createInThread方法創建中序遍歷的線索，最后調用inOrder方法中序遍歷線索二叉樹。最后，調用destroyTree方法銷毀線索二叉樹。?
結尾：
????????以上就是使用C++實現線索二叉樹的方法。線索二叉樹是一種非常實用的數據結構，它可以方便地對二叉樹進行遍歷。通過本文的介紹，相信讀者已經掌握了如何使用C++實現線索二叉樹的方法。
