所谓线索二叉树其实就是利用n+1个空指针所浪费的空间，n+1个指针能形成n条链，来保存节点的前驱后继，而形成一个链状的排列。对于线索二叉树的原理，应该是基于中序遍历而衍生出来的，把3个节点看做一个整体，那么最左边能留出前驱，最右边能留出后继，而这3个节点已经用2个指针连成了一条线，以此类推，足以保证树中所有节点都被连在一条线上。
代码用上一篇二叉树的代码就行修改，node 增添 leftTag、rightTag 用于线索二叉树的遍历访问，最后用非递归的中序遍历来验证线索二叉树
#include<iostream> using namespace std; typedef enum{ Link,Thread }PointerType; template <typename T> struct Node{ T data; PointerType leftTag; PointerType rightTag; Node<T>* left; Node<T>* right; }; Node<int>* pre; template <typename T> void Create(Node<T>*& node,T array[],int& index,int& length){ if(index>=length||array[index]==-1){ node=0; } else{ node=new Node<T>(); node->data=array[index]; Create(node->left,array,++index,length); Create(node->right,array,++index,length); } } template <typename T> void PreOrderTraversal(Node<T>*& node,void(*func)(Node<T>*& arg)){ if(node!=0){ if(func!=0){ func(node); } PreOrderTraversal(node->left,func); PreOrderTraversal(node->right,func); } } template <typename T> void InOrderTraversal(Node<T>*& node,void(*func)(Node<T>*& arg)){ if(node!=0){ InOrderTraversal(node->left,func); if(func!=0){ func(node); } InOrderTraversal(node->right,func); } } template <typename T> void PostOrderTraversal(Node<T>*& node,void(*func)(Node<T>*& arg)){ if(node!=0){ PostOrderTraversal(node->left,func); PostOrderTraversal(node->right,func); if(func!=0){ func(node); } } } template <typename T> void LinearNode(Node<T>*& node){ if(node->left==0){ node->leftTag=Thread; node->left=pre; } else{ node->leftTag=Link; } if(pre->right==0){ pre->rightTag=Thread; pre->right=node; } else{ pre->rightTag=Link; } pre=node; } template <class T> Node<T>* LinearTree(Node<T>*& tree){ void(*Delegate)(Node<T>*& arg); pre=new Node<T>; pre->data=0; pre->leftTag=Link; pre->left=tree; pre->rightTag=Thread; pre->right=0; Node<T>* first=pre; Delegate=LinearNode; InOrderTraversal(tree,Delegate); pre->right=first; pre->rightTag=Thread; first->right=pre; return first; } template <typename T> void Delete(Node<T>*& node){ delete node; } template <typename T> void Show(Node<T>*& node){ cout<<node->data<<endl; } /* 1 2 5 3 4 6 */ int main(){ void(*Delegate)(Node<int>*& arg); Delegate=0; int array[]={ 1,2,3,-1,-1,4,-1,-1,5,6,-1,-1,-1 }; Node<int>* tree; int index=0; int length=sizeof(array)/sizeof(array[0]); Create(tree,array,index,length); //Delegate=Show; //InOrderTraversal(tree,Delegate); Node<int>* first=LinearTree(tree); //InOrderTraversal Node<int>* temp=first->left; while(temp!=first){ while(temp->leftTag==Link){ temp=temp->left; } cout<<temp->data<<endl; while(temp->rightTag==Thread&&temp->right!=first){ temp=temp->right; cout<<temp->data<<endl; } temp=temp->right; } //Delegate=Delete; //PostOrderTraversal(tree,Delegate); return 0; }
