线索化二叉树-蒲公英云

线索化二叉树

二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。
为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。
这里写图片描述

前序的线索化：也是建立在前序的递归遍历的基础之上的

void _PreThread(Node*cur, Node*&prev)
    {
        if (cur == NULL)
        {
            return;
        }
        if (cur->Lchild == NULL)
        {
            cur->Lchild = prev;
            cur->LeftTag = THREAD;
        }
        if (prev&&prev->Rchild == NULL)
        {
            prev->Rchild = cur;
            prev->RightTag = THREAD;
        }   
        prev = cur;
        if (cur->LeftTag == LINK)
        {
            _PreThread(cur->Lchild,prev);
        }
        if (cur->RightTag == LINK)
        {
            _PreThread(cur->Rchild,prev);
        }
    }

根据前序的线索化我们可以写出非递归也不用借助栈就可以实现前序的遍历操作

void PrevOrderThread()
    {
        Node*cur = _root;
        while (cur->LeftTag == LINK)
        {
            cout << cur->data << " ";
            cur = cur->Lchild;
        }
        cout << cur->data << " ";
        cur = cur->Rchild;
    }

中序线索化：中序的线索化实际上是建立在中序的递归遍历的基础之上

void _InThread(Node*root, Node* &prev)
    {
        if (root)
        {
            _InThread(root->Lchild, prev);
            if (root->Lchild == NULL)
                root->Lchild = prev;
            {
                root->LeftTag = THREAD;
            }
            if (prev!=NULL&&prev->Rchild == NULL)
            {
                prev->Rchild = root;
                prev->RightTag = THREAD;
            }
            prev = root;
            _InThread(root->Rchild,prev);
        }
    }

根据中序的线索化我们可以写出非递归也不用借助栈就可以实现中序的遍历操作

void InOrderThread(Node *root)
    {
        if (root == NULL)
        {
            return;
        }
        Node *cur = root;
        while (cur!=NULL)
        {
            while (cur->LeftTag == LINK)
            {
                cur = cur->Lchild;
            }
            cout << cur->data<<" ";
            while (cur->RightTag == THREAD)
            {
                cur = cur->Rchild;
                if (cur == NULL)
                {
                    return;
                }
                cout << cur->data<<" ";
            }
                cur = cur->Rchild;
            }
        }

二叉树的后序线索化需要使用三叉链

#include<iostream>
#include<stdlib.h>
using namespace std;
enum 
{
    LINK,
    THREAD
};
template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T&x)
    :left(NULL)
    ,right(NULL)
    , parent(NULL)
    , data(x)
    , LeftTag(LINK)
    , RightTag(LINK)
    {
    }
    BinaryTreeNode<T>*left;
    BinaryTreeNode<T>*right;
    BinaryTreeNode<T>*parent;
    size_t LeftTag;
    size_t RightTag;
    T data;
};
template<class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;
public:
    BinaryTree()
    {
        _root = NULL;//空树
    }
    BinaryTree(T*arr, size_t size, size_t invalid)
    {
        size_t index = 0;
        Node*prev = NULL;
        _root = _CreateBinaryTree(arr, size, invalid, index,prev);
    }
    void PostThread()
    {
        Node*prev = NULL;
        Node*par = NULL;
        _PostThread(_root, prev);
    }
 void PostOrder()          //后序遍历 后序线索化二叉树
       {
              if (_root == NULL)
                     return;
              Node* cur = _root;
              while (cur->LeftTag == LINK || cur->RightTag == LINK) 
              {
                  if (cur->LeftTag == LINK)
                           cur = cur->left;
                     else if (cur->RightTag == LINK)
                           cur = cur->right;
              }
              cout << cur->data << " ";
              Node* p = NULL;
              while ((p = cur->parent) != NULL)
              {
                     if (p->right == cur || p->RightTag == THREAD)
                           cur = p;
                     else
                     {
                           cur = p->right;
                           while (cur->LeftTag == LINK || cur->RightTag == LINK)
                           {
                                  if (cur->LeftTag == LINK)
                                         cur = cur->left;
                                  else if (cur->RightTag == LINK)
                                         cur = cur->right;
                           }
                     }
                     cout << cur->data << " ";
              }
              cout << endl;
       }
protected:
    Node*_CreateBinaryTree(T*arr, size_t size, size_t invalid, size_t &index,Node*&prev)
    {
        Node*root = NULL;
        if (index < size&&arr[index] != invalid)
        {
            root = new Node(arr[index]);
            root->parent = prev;
            prev = root;
            root->left = _CreateBinaryTree(arr, size, invalid, ++index,prev);
            prev = root;
            root->right = _CreateBinaryTree(arr, size, invalid,++index,prev);
        }
        return root;
    }
    void _PostThread(Node*cur,Node*&prev)
    {
        if (cur == NULL)
        {
            return;
        }
            _PostThread(cur->left, prev);
            _PostThread(cur->right, prev);
            if (cur->left == NULL)
            {
                cur->left = prev;
                cur->LeftTag = THREAD;
            }
                if (prev&&prev->right == NULL)
                {
                    prev->right = cur;
                    prev->RightTag = THREAD;
                }
                prev = cur;
        }
    Node* _root;
};
void PostFunTest()
{
    int arr[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    int array[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 };
    BinaryTree<int> t1(arr, (sizeof(arr) / sizeof(arr[0])), '#');
    BinaryTree<int> t2(array, (sizeof(array) / sizeof(array[0])), '#');
    t1.PostThread();
    t1.PostOrder();
    cout << endl;
    t2.PostThread();
    t2.PostOrder();
}
int main()
{
    PostFunTest();
    system("pause");
    return 0;
}