一、什么是线索二叉树
二、中序二叉树的图形
三、中序线索二叉树的建立
- 3.1 核心程序
- 3.2 完整创建程序
四、其它方法的实现
五、完整代码+测试代码+运行结果
六、说明

线索二叉树作为二叉树的进阶，不仅仅是面试高频，Linux 内核中不少地方使用到这个数据结构（比如：文件管理系统的实现）。

一、什么是线索二叉树

线索化的二叉树就是：在原有的二叉树基础上有些改动，将没有孩子结点的链域声明为线，左孩子指向前驱，右孩子指向后继节点。

有孩子结点的为链，表示指向原先的左右孩子。

线索二叉树的基本存储结构如下：

二、中序二叉树的图形

线索二叉树无需遍历，可以很方便的得到其任一结点的前驱、后继。

三、中序线索二叉树的建立

必须先建立好二叉树(根据先序序列)，在其基础上创建中序线索二叉树；

核心程序：最好画图跟踪一下，才能弄得清楚；

注意：最后一个结点在函数结束时为LINK，没有更改过来！

3.1 核心程序

template<typename Type>
void BinTree<Type>::createInThread(BinTreeNode<Type> *t, BinTreeNode<Type> *&pre){ //创建中序线索二叉树
    if(t == NULL){                        //pre必须引用传递，的保证及时的更改！！！
        return;  //空树直接返回
    }
    createInThread(t->leftChild, pre);  //pre一直为空，一直在往左走；
    if(t->leftChild == NULL){
        t->ltag = THREAD;  //将左孩子设置为线
        t->leftChild = pre;  //因为是第一个，无前驱，所以置空
    }
    if(pre != NULL && pre->rightChild == NULL){ 
        pre->rtag = THREAD;  //将右孩子设置为线；
        pre->rightChild = t;  //此时指向后继结点，t已经回到了上一层
    }
    pre = t;  //将当前结点给pre;
    createInThread(t->rightChild, pre); //往右边递归
}

3.2 完整创建程序

#ifndef _THREAD_BIN_TREE_H_
#define _THREAD_BIN_TREE_H_

#include<iostream>
using namespace std;

typedef enum{LINK, THREAD}TAG;  //定义枚举标记链和线

template<typename Type>
class BinTree;

template<typename Type>  //结点类，多了两个标记链和线的；
class BinTreeNode{
    friend class BinTree<Type>;
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL), ltag(LINK), rtag(LINK){}
    BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *right = NULL) :
    data(value), leftChild(left), rightChild(right), ltag(LINK), rtag(LINK){}
    ~BinTreeNode(){}
private:
    Type data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
    TAG            ltag;          //左标记
    TAG            rtag;         //右标记
};
///////////////////////////////////////////////////////////////////////////////
template<typename Type>
class BinTree{
public:
    BinTree() : root(NULL){}
    BinTree(Type ref) : root(NULL), refval(ref){}
    BinTree(const BinTree &t){}
    ~BinTree(){
    }
public:
    void createBinTree(const char *str);  //的先建立二叉树
    void createInThread();
protected :
    void createBinTree(const char *&str, BinTreeNode<Type> *&t);
    void createInThread(BinTreeNode<Type> *t, BinTreeNode<Type> *&pre);
template<typename Type>
void BinTree<Type>::createBinTree(const char *str){
    createBinTree(str, root);
}
template<typename Type>
void BinTree<Type>::createInThread(){  //在二叉树已经建立起来，创建中序线索二叉树；
    BinTreeNode<Type> *pre = NULL;  //得弄一个前驱节点，做为参数传递过去
    createInThread(root, pre);   //真正的创建中序线索二叉树
    pre->rtag = THREAD;  //最后一个应该为线
}
template<typename Type>
void BinTree<Type>::createInThread(BinTreeNode<Type> *t, BinTreeNode<Type> *&pre){ //创建中序线索二叉树
    if(t == NULL){
        return;
    }
    createInThread(t->leftChild, pre);
    if(t->leftChild == NULL){
        t->ltag = THREAD;
        t->leftChild = pre;
    }
    if(pre != NULL && pre->rightChild == NULL){
        pre->rtag = THREAD;
        pre->rightChild = t;
    }
    pre = t;
    createInThread(t->rightChild, pre);
}
template<typename Type>  //创建二叉树
void BinTree<Type>::createBinTree(const char *&str, BinTreeNode<Type> *&t){
    if(*str == refval){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(*str);
        createBinTree(++str, t->leftChild);
        createBinTree(++str, t->rightChild);
    }
}

#endif

四、其它方法的实现

中序线索二叉树

public:
    BinTreeNode<Type>* first()const;  //查找中序的第一个结点
    BinTreeNode<Type>* last()const;   //查找中序的最后一个结点
    BinTreeNode<Type>* prev(BinTreeNode<Type> *cur)const; //查找当前结点的前驱
    BinTreeNode<Type>* next(BinTreeNode<Type> *cur)const; //查找当前结点的后继
    BinTreeNode<Type>* parent(BinTreeNode<Type> *cur)const; //查找当前结点的父结点
    void inOrder()const;  //中序遍历线索二叉树
    BinTreeNode<Type>* find(const Type &key); //查找某一结点

关于还有些方法: 求树高，求结点个数，这些其实跟前面写的差不多，将结束条件换为：

if(t->ltag == THREAD) {
    return 0;
}

4.1 查找第一个结点

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::first(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return NULL;
    }
    while(t->ltag == LINK){
        t = t->leftChild;
    }
    return t;
}

4.2 查找最后一个结点

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::last(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return NULL;
    }
    while(t->rtag == LINK){
        t = t->rightChild;
    }

    return t;
}

4.3 查找当前结点的前驱

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::prev(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL){
        return NULL;
    }
    if(cur->ltag == THREAD){
        return cur->leftChild;
    }else{
        return last(cur->leftChild);  //当前结点的前驱是：左树的最后一个结点；
    }
}

4.4 查找当前结点的后继

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::next(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL){
        return NULL;
    }
    if(cur->rtag == THREAD){
        return cur->rightChild;
    }else{
        return first(cur->rightChild);  //当前结点的后继是：右树的第一个结点；
    }   
}

4.5 中序遍历线索化二叉树

template<typename Type>
void BinTree<Type>::inOrder(BinTreeNode<Type> *t)const{
    BinTreeNode<Type> *p;

    if(t == NULL){
        return;
    }
    for(p = first(t); p != NULL; p = next(t, p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}

4.6 查找某一结点

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(BinTreeNode<Type> *t, const Type &key){
    if(t == NULL){
        return NULL;
    }
    if(t->data == key){
        return t;
    }

    BinTreeNode<Type> *p;
    for(p = first(t); p != NULL; p = next(t, p)){
        if(p->data == key){
            return p;
        }
    }
    return NULL;
}

4.7 查找当前结点的父结点

为空，或当前为根结点，其父结点 --> NULL;
看看根是否为父结点；
就是图中E、D这种情况，其父 --> 后继结点;
就是图中H、G这种情况，其父 --> 前驱结点;

以上就是针对存在线的求法；

针对没有线的求法：

例如求D：看的是其右的最后一个，因为线，走了一圈，就是确定B是其父；
找当前结点的左树的第一个，在返回其左孩子(此时这个线就是父节点)。

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL || cur == t){
        return NULL;   //父为空
    }
    if(t->ltag == LINK && t->leftChild == cur){  //父为根节点
        return t;
    } 
    if(t->rtag == LINK && t->rightChild == cur){
        return t;
    } 
    
    if(cur->rtag == THREAD && cur->rightChild->leftChild == cur){ //线的找
        return cur->rightChild;
    }
    if(cur->ltag == THREAD && cur->leftChild->rightChild == cur){  //线的找
        return cur->leftChild;
    }

    BinTreeNode<Type> *p = last(cur->rightChild);  //往右找最后一个，
    p = p->rightChild;
    if(p != NULL && p->leftChild->rightChild == cur){
        return p->leftChild;
    }
 
    p = first(cur->leftChild);  //换换思路，往左找第一个。
    return p->leftChild;
}

五、完整代码+测试代码+运行结果

5.1 完整代码

#ifndef _THREAD_BIN_TREE_H_
#define _THREAD_BIN_TREE_H_

#include<iostream>
using namespace std;

typedef enum{LINK, THREAD}TAG;

template<typename Type>
class BinTree;

template<typename Type>
class BinTreeNode{
    friend class BinTree<Type>;
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL), ltag(LINK), rtag(LINK){}
    BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *right = NULL) :
    data(value), leftChild(left), rightChild(right), ltag(LINK), rtag(LINK){}
    ~BinTreeNode(){}
private:
    Type data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
    TAG            ltag;          //左标记
    TAG            rtag;         //右标记
};
///////////////////////////////////////////////////////////////////////////////
template<typename Type>
class BinTree{
public:
    BinTree() : root(NULL){}
    BinTree(Type ref) : root(NULL), refval(ref){}
    BinTree(const BinTree &t){}
    ~BinTree(){
    }
public:
    void createBinTree(const char *str);
    void createInThread();
public:
    BinTreeNode<Type>* first()const;
    BinTreeNode<Type>* last()const;
    BinTreeNode<Type>* prev(BinTreeNode<Type> *cur)const;
    BinTreeNode<Type>* next(BinTreeNode<Type> *cur)const;
    BinTreeNode<Type>* parent(BinTreeNode<Type> *cur)const;
    void inOrder()const;
    BinTreeNode<Type>* find(const Type &key);
protected:
    BinTreeNode<Type>* first(BinTreeNode<Type> *t)const;
    BinTreeNode<Type>* last(BinTreeNode<Type> *t)const;
    BinTreeNode<Type>* prev(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const;
    BinTreeNode<Type>* next(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const;
    BinTreeNode<Type>* parent(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const;
    void inOrder(BinTreeNode<Type> *t)const;
    BinTreeNode<Type>* find(BinTreeNode<Type> *t, const Type &key);
protected :
    void createBinTree(const char *&str, BinTreeNode<Type> *&t);
    void createInThread(BinTreeNode<Type> *t, BinTreeNode<Type> *&pre);
private:
    BinTreeNode<Type> *root;
    Type               refval;  //'#'
};
template<typename Type>
void BinTree<Type>::createBinTree(const char *str){
    createBinTree(str, root);
}
template<typename Type>
void BinTree<Type>::createInThread(){
    BinTreeNode<Type> *pre = NULL;
    createInThread(root, pre);
    pre->rtag = THREAD;  //最后一个应该为线
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::first()const{
    return first(root);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::last()const{
    return last(root);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::prev(BinTreeNode<Type> *cur)const{
    return prev(root, cur);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::next(BinTreeNode<Type> *cur)const{
    return next(root, cur);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type> *cur)const{
    return parent(root, cur);
}
template<typename Type>
void BinTree<Type>::inOrder()const{
    inOrder(root);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(const Type &key){
    return find(root, key);
}
//////////////////////////////////////////////////////////////////////////////////////////
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(BinTreeNode<Type> *t, const Type &key){
    if(t == NULL){
        return NULL;
    }
    if(t->data == key){
        return t;
    }

    BinTreeNode<Type> *p;
    for(p = first(t); p != NULL; p = next(t, p)){
        if(p->data == key){
            return p;
        }
    }
    return NULL;
}
template<typename Type>
void BinTree<Type>::inOrder(BinTreeNode<Type> *t)const{
    BinTreeNode<Type> *p;

    if(t == NULL){
        return;
    }
    for(p = first(t); p != NULL; p = next(t, p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL || cur == t){
        return NULL;
    }
    if(t->ltag == LINK && t->leftChild == cur){
        return t;
    } 
    if(t->rtag == LINK && t->rightChild == cur){
        return t;
    } 
    
    if(cur->rtag == THREAD && cur->rightChild->leftChild == cur){
        return cur->rightChild;
    }
    if(cur->ltag == THREAD && cur->leftChild->rightChild == cur){
        return cur->leftChild;
    }

    BinTreeNode<Type> *p = last(cur->rightChild);
    p = p->rightChild;
    if(p != NULL && p->leftChild->rightChild == cur){
        return p->leftChild;
    }

    p = first(cur->leftChild);
    return p->leftChild;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::next(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL){
        return NULL;
    }
    if(cur->rtag == THREAD){
        return cur->rightChild;
    }else{
        return first(cur->rightChild);
    }
    
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::prev(BinTreeNode<Type> *t, BinTreeNode<Type> *cur)const{
    if(t == NULL || cur == NULL){
        return NULL;
    }
    if(cur->ltag == THREAD){
        return cur->leftChild;
    }else{
        return last(cur->leftChild);
    }
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::last(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return NULL;
    }
    while(t->rtag == LINK){
        t = t->rightChild;
    }

    return t;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::first(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return NULL;
    }
    while(t->ltag == LINK){
        t = t->leftChild;
    }
    return t;
}
template<typename Type>
void BinTree<Type>::createInThread(BinTreeNode<Type> *t, BinTreeNode<Type> *&pre){
    if(t == NULL){
        return;
    }
    createInThread(t->leftChild, pre);
    if(t->leftChild == NULL){
        t->ltag = THREAD;
        t->leftChild = pre;
    }
    if(pre != NULL && pre->rightChild == NULL){
        pre->rtag = THREAD;
        pre->rightChild = t;
    }
    pre = t;
    createInThread(t->rightChild, pre);

}
template<typename Type>
void BinTree<Type>::createBinTree(const char *&str, BinTreeNode<Type> *&t){
    if(*str == refval){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(*str);
        createBinTree(++str, t->leftChild);
        createBinTree(++str, t->rightChild);
    }
}

#endif

5.2 测试代码

#include"threadBinTree.h"

int main(void){
    char *str = "ABC##DE##F##G#H##";
    BinTree<char> bt('#');
    bt.createBinTree(str);
    bt.createInThread();

    bt.inOrder();
    BinTreeNode<char> *k = bt.find('A'); //直接输入字符查找，其方法find(const Type &key)中的const万万不可少
    BinTreeNode<char> *p = bt.first();  //C
    printf("%p\n", k);  //A
    BinTreeNode<char> *m;
    m = bt.parent(p);   
//    printf("%p\n", m);  //B
    BinTreeNode<char> *n;
    n = bt.parent(m);
    printf("%p\n", n);  //A
    return 0;
}

5.3 运行结果

六、说明

原创文章链接：从零开始学习数据结构-->线索二叉树

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

从零开始学习数据结构_线索二叉树.md

从零开始学习数据结构_线索二叉树.md

一、什么是线索二叉树

二、中序二叉树的图形

三、中序线索二叉树的建立

3.1 核心程序

3.2 完整创建程序

四、其它方法的实现

4.1 查找第一个结点

4.2 查找最后一个结点

4.3 查找当前结点的前驱

4.4 查找当前结点的后继

4.5 中序遍历线索化二叉树

4.6 查找某一结点

4.7 查找当前结点的父结点

五、完整代码+测试代码+运行结果

5.1 完整代码

5.2 测试代码

5.3 运行结果

六、说明

Files

从零开始学习数据结构_线索二叉树.md

Latest commit

History

从零开始学习数据结构_线索二叉树.md

File metadata and controls

一、什么是线索二叉树

二、中序二叉树的图形

三、中序线索二叉树的建立

3.1 核心程序

3.2 完整创建程序

四、其它方法的实现

4.1 查找第一个结点

4.2 查找最后一个结点

4.3 查找当前结点的前驱

4.4 查找当前结点的后继

4.5 中序遍历线索化二叉树

4.6 查找某一结点

4.7 查找当前结点的父结点

五、完整代码+测试代码+运行结果

5.1 完整代码

5.2 测试代码

5.3 运行结果

六、说明