本文共 11101 字，大约阅读时间需要 37 分钟。

二叉树线索化：

实验环境： Windows 8、Visual Studio 2013

实验语言： C++ 思想： 当二叉树使用链表表示时，用左右两个孩子指针可以找到左右孩子信息。我们可以用先序、中序、后序遍历二叉树，不同的遍历得到不同排列顺序的结点信息。只有在遍历的过程中才能得到某一结点的前驱与后继结点。 在n个结点的二叉树中，有2n个指针域，根节点不用指针域，其他(n-1)个结点只用了(n-1)个指针域，还有(n+1)个指针域空着没用，我们可以利用者空着的指针域来记录某种遍历下结点的前驱与后继。为了区分某个结点的指针域是指向孩子还是指向前驱/后继，要给结点添加的两个指针域添加标志， 当leftTag=false时，left指向左孩子；当leftTag=true时，left指向其前驱 当rightTag=false是，right指向其右孩子；当rightTag=true时，right指向其后继。 将一颗二叉树n+1个空指针域添加前驱或后继的过程就是线索话二叉树的过程。显然结点的前驱与后继只有在遍历的过程中才能得到，线索话二叉树的过程也就是遍历二叉树的过程。二叉树线索后，就可以通过左右孩子指针直接找到其前驱与后继，以中序线索话为例，当二叉树中序线索话后， 1、找某结点的前驱： 如果该结点的leftTag=true,那么left指向的结点就是其前驱结点 如果该结点的leftTag=false,那么该结点左子树最右边的结点就是其前驱结点。 2、找某结点后继 如果该结点的rightTag=true，那么right指向的结点就是其后继结点 如果该结点的rightTag=false,那个该结点的右子树的最左边的结点就是其后继结点。 二叉树线索话过程就是遍历过程，递归线索话时，需要一个全局变量来指向上一次遍历的结点（前驱结点）

//前序线索化//注意prev参数传参为引用，因为在递归中需要用到prev再上一层的值void _PrevOrderThreading(Node* cur, Node*& prev)    {        if (cur)        {            // 1.线索化当前节点的前驱              if (cur->_left == NULL)            {                cur->_leftTag = THREAD;                cur->_left = prev;            }            // 2.线索化前一个节点的后继为当前节点              if (prev && prev->_right == NULL)            {                prev->_rightTag = THREAD;                prev->_right = cur;            }            prev = cur;            // 只有LINK的节点才需要递归，否则前序遍历的节点已线索化。              if (cur->_leftTag == LINK)                _PrevOrderThreading(cur->_left, prev);            if (cur->_rightTag == LINK)                _PrevOrderThreading(cur->_right, prev);        }    }

//中序线索化void _InOrderThreading(Node* cur, Node*& prev)    {        if (cur == NULL)            return;        _InOrderThreading(cur->_left, prev);        // 线索化左        if (cur->_left == NULL)        {            cur->_leftTag = THREAD;            cur->_left = prev;        }        // 访问到下一个节点以后，线索化上一个节点右        if (prev && prev->_right == NULL)        {            prev->_right = cur;            prev->_rightTag = THREAD;        }        prev = cur;        _InOrderThreading(cur->_right, prev);    }

//后续线索化void _PostOrderThreading(Node* cur, Node*& prev)    {        if (cur)        {            // 只有LINK的节点才需要递归，否则前序遍历的节点已线索化。              if (cur->_leftTag == LINK)                _PostOrderThreading(cur->_left, prev);            if (cur->_rightTag == LINK)                _PostOrderThreading(cur->_right, prev);            // 1.线索化当前节点的前驱              if (cur->_left == NULL)            {                cur->_leftTag = THREAD;                cur->_left = prev;            }            // 2.线索化前一个节点的后继为当前节点              if (prev && prev->_right == NULL)            {                prev->_rightTag = THREAD;                prev->_right = cur;            }            prev = cur;        }    }

迭代器思想：（链化后的二叉树）

template
   
    struct BinaryTreeNodeIterator{    typedef BinaryTreeNodeThd
    
      Node;    Node* _node;    typedef BinaryTreeNodeIterator
     
       Self;    BinaryTreeNodeIterator(Node* node)        :_node(node)    {}    Ref operator*()    {        return _node->_data;    }    Ptr operator->()    {        return &_node->_data;    }    Self& operator++()    {        if (_node->_rightTag == THREAD)        {            _node = _node->_right;        }        else        {            Node* left = _node->_right;            while (left && left->_leftTag == LINK)            {                left = left->_left;            }            _node = left;        }        return *this;    }    bool operator != (const Self& s) const    {        return _node != s._node;    }    Self operator--()    {        if (_node->_leftTag == THREAD)        {            _node = _node->_left;        }        else        {            Node* right = _node->_left;            while (right && right->_rightTag == LINK)            {                right = right->_right;            }            _node = right;        }    }};
     
    
   

//部分接口Iterator Begin()    {        Node* left = _root;        while (left->_leftTag == LINK)        {            left = left->_left;        }        return Iterator(left);    }    Iterator End()    {        return Iterator(NULL);    }    ConstIterator Begin() const    {        Node* left = _root;        while (left->_leftTag == LINK)        {            left = left->_left;        }        return ConstIterator(left);    }    ConstIterator End() const    {        return ConstIterator(NULL);    }

//线索化后的析构void _Destroy(Node* _root)    {        if (_root == NULL)            return;        if (_root ->_leftTag == false)            _Destroy(_root->_left);        if (_root->_rightTag == false)            _Destroy(_root->_right);        delete _root;        _root = NULL;    }

完整代码：

BinaryTreeThread.h

#pragma once#include
   
    #include
    
     using namespace std;enum PointerTag { THREAD, LINK };template
     
      struct BinaryTreeNodeThd{    T _data;    BinaryTreeNodeThd
      
       * _right;    BinaryTreeNodeThd
       
        * _left;    BinaryTreeNodeThd
        
         * _parent; PointerTag _leftTag; PointerTag _rightTag; BinaryTreeNodeThd(const T& x=0) :_data(x) , _left(NULL) , _right(NULL) , _parent(NULL) , _leftTag(LINK) , _rightTag(LINK) {}};template
         
          struct BinaryTreeNodeIterator{ typedef BinaryTreeNodeThd
          
            Node; Node* _node; typedef BinaryTreeNodeIterator
           
             Self; BinaryTreeNodeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { if (_node->_rightTag == THREAD) { _node = _node->_right; } else { Node* left = _node->_right; while (left && left->_leftTag == LINK) { left = left->_left; } _node = left; } return *this; } bool operator != (const Self& s) const { return _node != s._node; } Self operator--() { if (_node->_leftTag == THREAD) { _node = _node->_left; } else { Node* right = _node->_left; while (right && right->_rightTag == LINK) { right = right->_right; } _node = right; } }};template
            
             class BinaryTreeThread{ typedef BinaryTreeNodeThd
             
               Node;public: typedef BinaryTreeNodeIterator
              
                Iterator; typedef BinaryTreeNodeIterator
               
                 ConstIterator; Iterator Begin() { Node* left = _root; while (left->_leftTag == LINK) { left = left->_left; } return Iterator(left); } Iterator End() { return Iterator(NULL); } ConstIterator Begin() const { Node* left = _root; while (left->_leftTag == LINK) { left = left->_left; } return ConstIterator(left); } ConstIterator End() const { return ConstIterator(NULL); } BinaryTreeThread() :_root(NULL) {} BinaryTreeThread(T* arr, size_t n, const T invalid = T()) { size_t index = 0; _root = _CreateTree(arr, n, invalid, index); } ~BinaryTreeThread() { _Destroy(_root); } //中序线索化 void InOrderThreading() { Node* prev = NULL; _InOrderThreading(_root, prev); } //中序线索化遍历 void InOrderThd() { cout << "InOrderThd: "; _InOrderThd(_root); cout << endl; } //前序线索化 void PrevOrderThreading() { Node* prev = NULL; _PrevOrderThreading(_root, prev); } //前序线索化遍历 void PrevOrderThd() { cout << "PrevOrderThd: "; _PrevOrderThd(_root); cout << endl; } //后续线索化 void PostOrderThreading() { Node* prev = NULL; _PostOrderThreading(_root, prev); } //后续线索化遍历 void PostOrderThd() { cout << "PostOrderThd: "; _PostOrderThd(_root); cout << endl; }protected: Node* _CreateTree(T* a, size_t n, const T& invalid, size_t& index) { Node* root = NULL; if (index < n && a[index] != invalid) { root = new Node(a[index]); root->_left = _CreateTree(a, n, invalid, ++index); root->_right = _CreateTree(a, n, invalid, ++index); if (root->_left) { root->_left->_parent = root; } if (root->_right) { root->_right->_parent = root; } } return root; } void _InOrderThreading(Node* cur, Node*& prev) { if (cur == NULL) return; _InOrderThreading(cur->_left, prev); // 线索化左 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } // 访问到下一个节点以后，线索化上一个节点右 if (prev && prev->_right == NULL) { prev->_right = cur; prev->_rightTag = THREAD; } prev = cur; _InOrderThreading(cur->_right, prev); } void _InOrderThd(Node* cur) { while (cur) { // 走左子树，找到第一个要访问的前驱节点 while (cur && cur->_leftTag != THREAD) { cur = cur->_left; } // 访问当前节点 cout << cur->_data << " "; // 访问连接在一起的后继节点 while (cur->_rightTag !=LINK) { cur = cur->_right; cout << cur->_data << " "; } cur = cur->_right; } } void _PrevOrderThreading(Node* cur, Node*& prev) { if (cur) { // 1.线索化当前节点的前驱 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } // 2.线索化前一个节点的后继为当前节点 if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; // 只有LINK的节点才需要递归，否则前序遍历的节点已线索化。 if (cur->_leftTag == LINK) _PrevOrderThreading(cur->_left, prev); if (cur->_rightTag == LINK) _PrevOrderThreading(cur->_right, prev); } } void _PrevOrderThd(Node* cur) { while (cur) { // 前序遍历路径上的所经节点 while (cur->_leftTag!=THREAD) { // 访问当前节点 cout << cur->_data << " "; cur = cur->_left; } cout << cur->_data<<" "; cur = cur->_right; } } void _PostOrderThreading(Node* cur, Node*& prev) { if (cur) { // 只有LINK的节点才需要递归，否则前序遍历的节点已线索化。 if (cur->_leftTag == LINK) _PostOrderThreading(cur->_left, prev); if (cur->_rightTag == LINK) _PostOrderThreading(cur->_right, prev); // 1.线索化当前节点的前驱 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } // 2.线索化前一个节点的后继为当前节点 if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; } } void _PostOrderThd(Node* root) { BinaryTreeNodeThd
                
                 * cur = root; BinaryTreeNodeThd
                 
                  * prev = NULL; while (cur) { // 走左子树，先找到最左节点 while (cur && cur->_leftTag == LINK) { cur = cur->_left; } // 访问后继节点 while (cur->_rightTag == THREAD) { cout << cur->_data << " "; prev = cur; cur = cur->_right; } if (cur == root) { cout << cur->_data << " "; break; } // 如果当前节点的右节点已访问，则访问当前节点并跳到父节点 while (cur->_right == prev) { cout << cur->_data << " "; prev = cur; if (cur == root) return; cur = cur->_parent; } // 跳转到当前节点的右树，当做子树访问 if (cur->_rightTag == LINK) cur = cur->_right; } } void _Destroy(Node* _root) { if (_root == NULL) return; if (_root ->_leftTag == false) _Destroy(_root->_left); if (_root->_rightTag == false) _Destroy(_root->_right); delete _root; _root = NULL; }private: Node* _root;};void PrintTree(BinaryTreeThread
                  
                   & t){ BinaryTreeThread
                   
                    ::Iterator it = t.Begin(); while (it != t.End()) { cout << *it << " "; ++it; } cout << endl;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

测试用例：

BinaryTreeThread.cpp

#include"BinaryTreeThread.h"void TestBinaryTreeThd(){    int array1[20] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };    BinaryTreeThread
   
     t1(array1, 10,'#');    t1.InOrderThreading();    t1.InOrderThd();    BinaryTreeThread
    
      t2(array1, 10,'#');    t2.PrevOrderThreading();    t2.PrevOrderThd();    BinaryTreeThread
     
       t3(array1, 10,'#');    t3.PostOrderThreading();    t3.PostOrderThd();    int array2[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 };    BinaryTreeThread
      
        t4(array2, 15,'#');    t4.InOrderThreading();    t4.InOrderThd();    BinaryTreeThread
       
         t5(array2, 15,'#');    t5.PostOrderThreading();    t5.PostOrderThd();    BinaryTreeThread
        
          t6(array2, 15,'#'); t6.PrevOrderThreading(); t6.PrevOrderThd(); PrintTree(t1);}int main(){ TestBinaryTreeThd(); system("pause"); return 0;}
        
       
      
     
    
   

实验结果：