MENU

线索二叉树

April 7, 2018 • 技术

一:背景

线索二叉树的定义为:一个二叉树通过如下的方法“穿起来”:所有应该为空的右孩子指针指向该结点在中序序列中的后继,所有应该为空的左孩子指针指向该结点的中序序列的前驱。

那么在有N个结点的二叉树中共有N+1个空指针,这些空指针就叫做“线索”。(提示:在一个有N个结点的二叉树中,每个结点有2个指针,所以一共有2N个指针,将这N个结点连接起来需要N-1条线,即使用了N-1个指针。所以剩下2N-(N-1)=N+1个空指针。)

那线索二叉树有何用处呢?由于巧妙地利用了空指针,所以它可以快速地查找到二叉树中某结点的前驱和后继。接下来具体介绍这个数据结构。

在进行下文之前,约定如下:

struct Node
{
    bool left_thread;
    bool right_thread;
    char data;
    Node * left;
    Node * right;

    Node()
    {
        left_thread = right_thread = false;
        data = 0;
        left = right = nullptr;
    }
};

class ThreadedBinaryTree
{
public:
    ThreadedBinaryTree();
    Node * create();
    void threaded(Node * cur, Node *& pre);  // 线索化
    void formLoop();                         // 构环
    Node * get_successor(Node * node);       // 返回后继结点
    Node * get_precursor(Node * node);       // 返回前驱结点
    void in_order_print();                   // 中序遍历
private:
    Node * header;  // 头结点
    Node * root;    // 二叉树根结点
};

请注意,在决定left是指向左孩子还是前驱,right是指向右孩子还是后继,我们是需要一个区分标志的。因此我们在Node结构体中增设两个布尔变量left_thread和right_thread,其中:
(1):left_thread为true时指向前驱,为false时指向该结点的左子树;
(2):right_thread为true时指向后继,为false时指向该结点的右子树。

二:具体实现与代码分析

2.1 构造二叉树

ThreadedBinaryTree::ThreadedBinaryTree()
{
    root = create();
}

Node * ThreadedBinaryTree::create()
{
    Node * p = nullptr;
    char ch;
    cin >> ch;
  
    if (ch == '.')  // 结束输入
        p = nullptr;
    else
    {
        p = new Node;
        p->data = ch;
        p->left = create();
        p->right = create();
    }
  
    return p;
}

2.2 线索化及二叉树构环

void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
    if (cur == nullptr)
        return;
    else
    {
        // 按照中序遍历方向,先处理左子树
        threaded(cur->left, pre);

        // 再处理当前结点
        if (cur->left == nullptr)
        {
            cur->left_thread = true;
            cur->left = pre;
        }
        if (cur->right == nullptr)
            cur->right_thread = true;
        if (pre->right_thread)
            pre->right = cur;
        pre = cur;

        // 最后处理右子树
        threaded(cur->right, pre);
    }
}

void ThreadedBinaryTree::formLoop()
{
    header = new Node;  // 创建头结点,并完成初始化
    header->left_thread = true;
    header->right_thread = true;
    header->left = header->right = header;

    Node * pre = header;  // 记录中序遍历的前一个结点
    threaded(root, pre);  // 进行线索化

    pre->right_thread = true;  // 线索化完后,把中序遍历的最后一个结点即 pre,指向 header
    pre->right = header;
    header->left = pre;  // 注意,header 的左指针指向中序遍历的最后一个
}

header结点的作用就是把线索化后的二叉树串起来,形成一个环。header的左孩子指向中序遍历序列的最后一个结点,右孩子指向中序遍历序列的第一个结点,如下图:

2.3 后继和前驱

Node * ThreadedBinaryTree::get_successor(Node * node)
{
    if (node->right_thread)
        return node->right;
  
    Node * p = node->right;
    while (p->left_thread == false)  // 已线索化,故此处只能用 left_thread 来判断左子树的情况
        p = p->left;
  
    return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
    if (node->left_thread)
        return node->left;
  
    Node * p = node->left;
    while (p->right_thread == false)  // 已线索化,故此处只能用 right_thread 来判断右子树的情况
        p = p->right;
  
    return p;
}

2.4 中序遍历

void ThreadedBinaryTree::in_order_print()
{
    cout << "中序遍历为:";
    Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点
  
    while (p != header)
    {
        cout << p->data << " ";
        p = get_successor(p);
    }
  
    cout << endl;
}

三:完整代码

#include <iostream>

using namespace std;

struct Node
{
    bool left_thread;
    bool right_thread;
    char data;
    Node * left;
    Node * right;

    Node()
    {
        left_thread = right_thread = false;
        data = 0;
        left = right = nullptr;
    }
};

class ThreadedBinaryTree
{
public:
    ThreadedBinaryTree();
    Node * create();
    void threaded(Node * cur, Node *& pre);  // 线索化
    void formLoop();                         // 构环
    Node * get_successor(Node * node);       // 返回后继结点
    Node * get_precursor(Node * node);       // 返回前驱结点
    void in_order_print();                   // 中序遍历
private:
    Node * header;  // 头结点
    Node * root;    // 二叉树根结点
};

int main()
{

    ThreadedBinaryTree my_tree;
    my_tree.formLoop();
    my_tree.in_order_print();

    return 0;
}

ThreadedBinaryTree::ThreadedBinaryTree()
{
    root = create();
}

Node * ThreadedBinaryTree::create()
{
    Node * p = nullptr;
    char ch;
    cin >> ch;
  
    if (ch == '.')  // 结束输入
        p = nullptr;
    else
    {
        p = new Node;
        p->data = ch;
        p->left = create();
        p->right = create();
    }
  
    return p;
}

void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
    if (cur == nullptr)
        return;
    else
    {
        // 按照中序遍历方向,先处理左子树
        threaded(cur->left, pre);

        // 再处理当前结点
        if (cur->left == nullptr)
        {
            cur->left_thread = true;
            cur->left = pre;
        }
        if (cur->right == nullptr)
            cur->right_thread = true;
        if (pre->right_thread)
            pre->right = cur;
        pre = cur;

        // 最后处理右子树
        threaded(cur->right, pre);
    }
}

void ThreadedBinaryTree::formLoop()
{
    header = new Node;  // 创建头结点,并完成初始化
    header->left_thread = true;
    header->right_thread = true;
    header->left = header->right = header;

    Node * pre = _header;  // 记录中序遍历的前一个结点
    threaded(root, pre);   // 进行线索化

    pre->right_thread = true;  // 线索化完后,把中序遍历的最后一个结点即 pre,指向 header
    pre->right = header;
    header->left = pre;  // 注意,header 的左指针指向中序遍历的最后一个
}

Node * ThreadedBinaryTree::get_successor(Node * node)
{
    if (node->right_thread)
        return node->right;
  
    Node * p = node->right;
    while (p->left_thread == false)  // 已线索化,故此处只能用 left_thread 来判断左子树的情况
        p = p->left;
  
    return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
    if (node->left_thread)
        return node->left;
  
    Node * p = node->left;
    while (p->right_thread == false)  // 已线索化,故此处只能用 right_thread 来判断右子树的情况
        p = p->right;
  
    return p;
}

void ThreadedBinaryTree::in_order_print()
{
    cout << "中序遍历为:";
    Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点
  
    while (p != header)
    {
        cout << p->data << " ";
        p = get_successor(p);
    }
  
    cout << endl;
}

以(2.2)中的图为例,输入数据及测试结果为:

Archives QR Code Tip
QR Code for this page
Tipping QR Code