二叉树的线索化（C++实现）

2019-11-14 08:54:17

字体：大中小

来源：转载

供稿：网友

对于一棵二叉树，我们可以通过前序，中序，后序，层序四种遍历方式得到关于二叉树的序列，这样从每个结点出发就很容易找到它在某种次序下前序和后继。

PS：关于四种遍历方式的递归和非递归实现可点击我的github 里面的BInaryTree.h查看。

但是很多时候，我们希望很快找到某的结点的前序或者后继，又不想遍历一遍，这就需要我们记录下每个结点的前驱和后继，因此为了做到这一点，我们引入了二叉树的线索化。

我们观察各种二叉树的结构，发现不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n个结点的指针域共有2n个，非空指针域为n-1个，但其中的空指针域却有n+1个。这是因为，对于二叉树的每个结点都有左右孩子，但是每个结点（除根节点）只有一个父亲，因此n个结点空指针域为**2n - (n - 1) = n + 1个。比如下图，其空指针域个数为 2 * 6 - 5 = 7个

这里写图片描述

因此我们可以利用这些空指针域来标记结点的前驱或者后继，规则如下：

若结点有左子树，则其左指针域指向其左孩子，否则令左指针指向其前驱若结点有右子树，则其右指针域指向其右孩子，否则令右指针指向其后继为了区分指针域是指向它的孩子还是前驱（后继），我们分别加一个标志位（如下图）

我们给出树的结点定义如下：

结点结构

enum PointerTag { LINK,THREAD };//LINK表示指向的是左右孩子，THREAD则表示指向前驱或者后继template<class T>struct BinaryTreeThreadNode{ T _data;//节点数据 BinaryTreeThreadNode<T>* _left;//左孩子 BinaryTreeThreadNode<T>* _right;//右孩子 PointerTag _leftTag;//左孩子线索标志 PointerTag _rightTag;//右孩子线索标志 BinaryTreeThreadNode(const T& x = T()) : _data(x) , _left(nullptr) , _right(nullptr) , _leftTag(LINK) , _rightTag(LINK) {}};

为了实现线索化，我们需要先构建一棵树，为了简单，我们采用前序方式构建树，对于给定的一个数组，如果元素为 ‘#’ 则表明当前结点为空，不然为左子树。例如：

int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };

所构建的树如下图：

这里写图片描述

C++代码如下：

template<class T>class BinaryTreeThread{ typedef BinaryTreeThreadNode<T> Node;public: BinaryTreeThread() : _root(nullptr) {} //前序方式构建二叉树 BinaryTreeThread(T *a, size_t n, const T& invalid = T()) { assert(a); size_t index = 0; _root = _createTree(a, n, index, invalid); }PRivate: //递归建树 //四个参数含义依次为数组名，数组大小，数组元素下标，无效值比如‘#’ Node *_createTree(T *a, size_t n, size_t& index, const T& invalid = T()) { Node *root = nullptr; if (index < n && a[index] != invalid) { root = new Node(a[index]); root->_left = _createTree(a, n, ++index, invalid); root->_right = _createTree(a, n, ++index, invalid); } return root; }private: Node *_root;};

我们以上面的二叉树为例建立线索化：

前序线索化

这里写图片描述

前序线索化的树如上图，下面我们看看如何建立线索化。

实际上线索化的代码和遍历代码结构类似，因为线索化需要在遍历的时候完成指针之间的连接，也是遵循着前序遍历的顺序，先是根节点然后分别是左子树右子树。

以上图为例，对于1，2来说左右不为空按照前序遍历的顺序来即可，但是遍历到了3时，由于3的左右为空，我们需要完成3的前驱是2，3的后继是4这样的指针连接操作。为了完成这样的连接操作，我们在实现代码时候需要记录一个指向前一个结点的指针prev，比如访问到3时候，cur指向3，prev指向2，同时将标志位改成THREAD，比如下面的代码

cur->_left = prev;cur->_leftTag = THREAD;

就完成了3的前驱是4的操作，然而对于3的后继是4，我们不能记录个next指针指向下一个结点，因为我们无法预知下一个结点指向哪儿，那该怎么办？我们知道了前一个结点的指向，因此我们只需要访问下一个结点时候完成后继这一步连接：当访问到4时候，cur指向4，prev指向3，这时候只要

prev->_right = cur;prev->_rightTag = THREAD;

这样就可以玩成3的后继是4这一操作了，最后完成当前结点的线索化一定要改变prev为cur。因此完整的前序线索化代码如下：

void PreOrderThreading(){ Node *prev = nullptr; _preOrderThreading(_root, prev);//_root为根节点}void _preOrderThreading(Node *cur, Node *& prev){ if (cur == nullptr) return; //当前节点的线索化 if (cur->_left == nullptr) { cur->_left = prev; cur->_leftTag = THREAD; } if (prev && prev->_right == nullptr) { prev->_right = cur; prev->_rightTag = THREAD; } prev = cur; //左子树的线索化 if (cur->_leftTag == LINK) _preOrderThreading(cur->_left, prev); //右子树的线索化 if (cur->_rightTag == LINK) _preOrderThreading(cur->_right, prev);}

建立前序线索化，我们可以通过前序遍历看看我们写的是否是对的？下面分别是递归和非递归两种方法的遍历：

//递归遍历void PreOrder(){ _preOrder(_root); cout << endl;}void _preOrder(Node *root){ if (root == NULL) return; cout << root->_data << " "; if (root->_leftTag == LINK) _preOrder(root->_left); if (root->_rightTag == LINK) _preOrder(root->_right);}//非递归遍历void PreOrderNonR(){ Node *cur = _root; while (cur) { while (cur->_leftTag == LINK) { cout << cur->_data << " "; cur = cur->_left; } cout << cur->_data << " "; cur = cur->_right; //下面这种写法也可以 //while (cur && cur->_rightTag == THREAD) //{ // cur = cur->_right; // if (cur) // cout << cur->_data << " "; //} //if (cur->_rightTag == LINK) // cur = cur->_right; } cout << endl;}

中序线索化

这里写图片描述

中序线索化和前序基本没什么区别。。。只是需要改变一下顺序而已，代码如下：

void InOrderThreading(){ Node *prev = nullptr; _inOrderThreading(_root, prev);}void _inOrderThreading(Node *cur, Node *& prev){ if (cur == nullptr) return; //左子树的线索化 if (cur->_leftTag == LINK) _inOrderThreading(cur->_left, prev); //当前结点的线索化 if (cur->_left == nullptr) { cur->_left = prev; cur->_leftTag = THREAD; } if (prev && prev->_right == nullptr) { prev->_right = cur; prev->_rightTag = THREAD; } prev = cur; //右左子树的线索化 if (cur->_rightTag == LINK) _inOrderThreading(cur->_right, prev);}

而他的遍历方式如下：

//递归遍历void InOrder(){ _inOrder(_root); cout << endl;}void _inOrder(Node* root){ if (root == NULL) return; if (root->_leftTag == LINK) _inOrder(root->_left); cout << root->_data << " "; if (root->_rightTag == LINK) _inOrder(root->_right);}//非递归遍历void InOrderNonR(){ Node *cur = _root; while (cur) { while (cur->_leftTag == LINK) cur = cur->_left; cout << cur->_data << " "; while (cur && cur->_rightTag == THREAD) { cur = cur->_right; if (cur) cout << cur->_data << " "; } if (cur->_rightTag == LINK) cur = cur->_right; } cout << endl;}