A：什么是線索二叉樹？
B：先別著急，你知道二叉樹的定義的存盤結構是什么嗎？
A：當然知道，就是包含一個值域和兩個指標域的結構體，下圖所示
typedef struct node
{
char data;
struct node *left,*right;
}TreeB：是的，是這樣的，我們可以從代碼中看出，我們可以通過left和right指標來找到一個結點的左右孩子，對嗎？那如果我們想要找到一個結點的前驅和后繼該怎么辦呢？
A：很容易找到左右孩子，嗯？前序和后繼？這個是什么意思？
B：我們知道一個樹有三種遍歷，前后中，比如一個樹的前序遍歷是ABC，我們很容易看出B的前驅結點時A，B的后繼結點是C，當我們遍歷整個二叉樹時，很容易找出某個結點的前驅和后繼，那么如果我需要直接讓你用代碼找出一個結點的前驅和后繼，你該怎么辦呢？
A：添加新的指標嗎？
B：不用不用，你想想我們建立一棵有n個結點的樹時，創建了多少指標？
A：一個結點兩個指標，當然是2n個指標
B：我們一共用了多少個指標呢？
A：n個結點的二叉樹的一共有n-1條分支，那么我們就用了n-1個指標，還有2n-(n-1)個指標沒有使用
B：對了，我們就可以利用著n+1個指標來指向一個結點的前驅和后繼，而且還利用了空間
A：我有點糊涂了，那應該怎么做呢？
B：因為我們的結點本生就具有兩個指標，我們如何知道它的左右孩子是指向前驅還是后繼呢？我們在原有的基礎上，加上ltga和rtag來判斷左右指標的指向
ltag==0時代表該結點的left指標指向的是左孩子
ltag==1時代表該結點的left指標指向的是前驅結點
同理可知rtag
A：我明白了！那我們該如何實作呢
B：我們在遍歷二叉樹的時候就會知道結點的前驅，那時候我們就可以給ltag和rtag進行賦值
A：我通過中序遍歷來給ltag和rtag賦值
#include <iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
char data;
struct node *left,*right;
int ltag,rlag;
}ThreadTree;//線索二叉樹
ThreadTree *create()//遞回創建二叉樹
{
ThreadTree *t=(ThreadTree *)malloc(sizeof(ThreadTree));
char a;
cin>>a;
if(a=='#')
t=NULL;
else{
t->data=https://www.cnblogs.com/mlqq/p/a;
t->left=t->right=NULL;
t->left=create();
t->right=create();
}
return t;
}
void Zhongxu(ThreadTree *t)//中序線索二叉樹
{
ThreadTree *pre;//代表后繼
if(t)
{
Zhongxu(t->left);
if(t->left==NULL)//左是前驅
{
t->ltag=1;
t->left=pre;
}
if(pre->right==NULL)//右是后繼
{
pre->rlag=1;
pre->right=t;
}
pre=t;
cout<data;
Zhongxu(t->right);
}
}
int main()
{
ThreadTree *t;
t=create();//創建二叉樹
Zhongxu(t);//中序遍歷二叉樹
}
A：這就是線索二叉樹的程序，現在你明白什么是線索二叉樹了嘛
B：明白了！線索二叉樹就是利用二叉樹空閑的指標，將它指向結點的前驅后者后繼，這樣就很快可以找到一個結點的前驅和后繼
A：Yes，就是這樣，不要忘記了，線索二叉樹有三種結構哦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/373792.html
標籤：其他
上一篇：二分查找（Java實作）
下一篇：LSM-Tree：原理與介紹