C言語 數據構造之中序二叉樹實例詳解。本站提示廣大學習愛好者：（C言語 數據構造之中序二叉樹實例詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C言語 數據構造之中序二叉樹實例詳解正文
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;
}
感激閱讀，希望能協助到大家，謝謝大家對本站的支持！
