二叉树 -- 线索二叉树

一、概念

对于一棵结点数目为n的二叉树，采用二叉链表的形式存储，每个结点均有指向左右孩子的两个指针域。假设结点为n的二叉树一共有n-1条有效分支路径，那么二叉链表中存在2n-(n-1)=n+1个空指针域，这些空指针造成了空间浪费。

此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列，然后可以知道任意一个结点的前驱结点和后继结点，但是这种关系的获得是建立在完成遍历后得到的，如果在建立二叉树时就记录下前驱和后继的关系，在后续寻找前驱结点和后继结点时将大大提升效率。

线索化：
将一棵普通二叉树以某种次序遍历，并添加线索的过程称为线索化。通过线索化，既解决了空间浪费问题，又解决了前驱后继的记录问题。

规则：

• 若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
• 若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

线索二叉树

二、数据结构

struct ThreadTreeNode {
    int id;
    ThreadTreeNode *leftChild, *rightChild; //左右孩子指针
    bool isLeftThread, isRightThread; //左右孩子是否为线索标志
};

三、相关操作

• 中序遍历建立线索二叉树
• 遍历线索二叉树（非递归算法并且不使用栈数据结构）

四、实现

#include<stdio.h>
#include<malloc.h>

struct ThreadTreeNode {  
    int id;  
    ThreadTreeNode *leftChild, *rightChild;//左右孩子指针  
    bool isLeftThread, isRightThread;//左右孩子是否为线索标志  
};

ThreadTreeNode *pre = NULL; //线索化时保存前驱

ThreadTreeNode* mallocThreadTreeNode() {
    ThreadTreeNode* node = (ThreadTreeNode*)malloc(sizeof(ThreadTreeNode));
    return node;
}

void initTree(ThreadTreeNode* root) {
    root->id = 1;
    ThreadTreeNode* node2 = mallocThreadTreeNode();
    node2->id = 2;
    ThreadTreeNode* node3 = mallocThreadTreeNode();
    node3->id = 3;
    ThreadTreeNode* node4 = mallocThreadTreeNode();
    node4->id = 4;
    ThreadTreeNode* node5 = mallocThreadTreeNode();
    node5->id = 5;
    ThreadTreeNode* node6 = mallocThreadTreeNode();
    node6->id = 6;
    ThreadTreeNode* node7 = mallocThreadTreeNode();
    node7->id = 7;

    root->leftChild = node2;
    root->isLeftThread = false;
    root->rightChild = node3;
    root->isRightThread = false;
    node2->leftChild = node4;
    node2->isLeftThread = false;
    node2->rightChild = node5;
    node2->isRightThread = false;
    node3->leftChild = node6;
    node3->isLeftThread = false;
    node3->rightChild = node7;
    node3->isRightThread = false;
    node4->leftChild = NULL;
    node4->isLeftThread = false;
    node4->rightChild = NULL;
    node4->isRightThread = false;
    node5->leftChild = NULL;
    node5->isLeftThread = false;
    node5->rightChild = NULL;
    node5->isRightThread = false;
    node6->leftChild = NULL;
    node6->isLeftThread = false;
    node6->rightChild = NULL;
    node6->isRightThread = false;
    node7->leftChild = NULL;
    node7->isLeftThread = false;
    node7->rightChild = NULL;
    node7->isRightThread = false;
}

void inOrderCreateThread(ThreadTreeNode *node){ //中序遍历建立线索二叉树
    if(node == NULL) { 
        return;
    }  

    inOrderCreateThread(node->leftChild);//左子树线索化  
    printf("%d ", node->id);
    if(node->leftChild == NULL) {//当前结点的左孩子为空  
        node->isLeftThread = true; 
        node->leftChild = pre;  
    }
    if(pre != NULL && pre->rightChild == NULL) {//前驱结点的右孩子为空  
        pre->isRightThread = true; 
        pre->rightChild = node;  
    }
    pre = node;  
    inOrderCreateThread(node->rightChild);//右子树线索化  
}  

void visitThread(ThreadTreeNode *root){ //遍历线索二叉树（非递归算法并且不使用栈数据结构）
    if(root == NULL) {
        return;
    }

    ThreadTreeNode *p = root;
    while(p != NULL && p->isLeftThread == false) { //当前结点的左子树结点不是线索结点
        p = p->leftChild;
    }
    while(p != NULL) {
        printf("%d ", p->id);
        if(p->isRightThread == true) { //当前结点的右子树结点是线索结点
            p = p->rightChild;
        } else { //当前结点的右子树结点不是线索结点
            p = p->rightChild;
            while(p != NULL && p->isLeftThread == false) { //当前结点的左子树结点不是线索结点
                p = p->leftChild;
            }
        }
    }  
}  

void main() {
    ThreadTreeNode root;
    initTree(&root);
    inOrderCreateThread(&root);
    printf("\n");
    visitThread(&root);
    printf("\n");
}