二叉线索树是将二叉树按某种遍历顺序将其线索化，线索化的意思就是在某些结点加上指向其前驱或后继的指针。
这样我们就能在树中方便的找到前驱或后继，而不用遍历整棵树。
下面是我完成的代码：
#include < iostream > #include < stack > using namespace std; // the structure of the nodes of the binary tree typedef struct BTNode ... { char cData; int nLeftThread, nRightThread; struct BTNode* pLeftChild; struct BTNode* pRightChild;} BTNode; /**/ /* * Function Name ：CreatBinaryTree * function ：creat binary tree using pre order method * detail ：none * author ：weixiong * time ：2007-1-25 * return ：return the root of the binary tree * function parameters ：BTNode* pHead the root of this tree */ BTNode * CreatBinaryTree(BTNode * pHead) ... { cout << "please enter the element for the node:"; char cTemp; cin >> cTemp; cout << endl; if ('x' == cTemp) ...{ pHead = NULL; } else ...{ pHead = new BTNode; pHead->cData = cTemp; pHead->nLeftThread = 0; pHead->nRightThread = 0; pHead->pLeftChild = CreatBinaryTree(pHead->pLeftChild); pHead->pRightChild = CreatBinaryTree(pHead->pRightChild); } return pHead;} /**/ /* * Function Name ：ThreadBinaryTree * function ：thread the binary tree * detail ：none * author ：weixiong * time ：2007-1-25 * return ：return the head of the binary tree * function parameters ： BTNode* pRoot the root of this tree */ BTNode * ThreadBinaryTree(BTNode * pRoot) ... { //creat a head for the thread binary tree BTNode* pHead = new BTNode; pHead->cData = 0; pHead->nLeftThread = 0; pHead->pLeftChild = pRoot; pHead->nRightThread = 1; pHead->pRightChild = pHead; //push the non-leaf node's left child in a stack and process each node while pop a node from the stack BTNode* pCurrent = pRoot; BTNode* pPreNode = pHead; stack<BTNode*>* pLeftChildStack = new stack<BTNode*>; do ...{ //push the node's left child in stack while (NULL != pCurrent) ...{ pLeftChildStack->push(pCurrent); pCurrent = pCurrent->pLeftChild; } if (1 != pLeftChildStack->top()->nLeftThread) pCurrent = pLeftChildStack->top(); pLeftChildStack->pop(); cout << pCurrent->cData << " "; //if the popped node doesn't have a left child, we can give it a preceding node if (NULL == pCurrent->pLeftChild) ...{ pCurrent->nLeftThread = 1; pCurrent->pLeftChild = pPreNode; } //give the preceding node a successor if (NULL == pPreNode->pRightChild) ...{ pPreNode->nRightThread = 1; pPreNode->pRightChild = pCurrent; } pPreNode = pCurrent; pCurrent = pCurrent->pRightChild; }while( (pLeftChildStack->size() > 0) || (NULL != pCurrent) ); pHead->nRightThread = 1; pPreNode->nRightThread = 1; pPreNode->pRightChild = pHead; pHead->pRightChild = pPreNode; return(pHead);} /**/ /** Function Name ：TraversalInorderBinaryTreeEB* function ：traverse the binary tree from end to begin using inorder method* detail ：none* author ：weixiong* time ：2007-1-25* return ：void* function parameters ：BTNode* pHead head of the binary tree*/ void TraversalInorderBinaryTreeEB(BTNode * pHead) ... { BTNode* pCurrent; if (1 == pHead->nRightThread) ...{ pCurrent = pHead->pRightChild; cout << pCurrent->cData << " "; do ...{ if ( 1 == pCurrent->nLeftThread) ...{ pCurrent = pCurrent->pLeftChild; cout << pCurrent->cData << " "; } else ...{ pCurrent = pCurrent->pLeftChild; while( (NULL != pCurrent->pRightChild) && (0 == pCurrent->nRightThread) ) pCurrent = pCurrent->pRightChild; cout << pCurrent->cData << " "; } } while(0 != pCurrent->cData); }} /**/ /** Function Name ：TraversalInorderBinaryTreeBE* function ：traverse the binary tree from begin to end using inorder method* detail ：none* author ：weixiong* time ：2007-1-25* return ：void* function parameters ：BTNode* pHead head of the binary tree*/ void TraversalInorderBinaryTreeBE(BTNode * pHead) ... { BTNode* pCurrent; pCurrent = pHead; pCurrent = pHead->pLeftChild; while (0 == pCurrent->nLeftThread) pCurrent = pCurrent->pLeftChild; cout << pCurrent->cData << " "; do ...{ if (1 == pCurrent->nRightThread) ...{ pCurrent = pCurrent->pRightChild; cout << pCurrent->cData << " "; } else ...{ pCurrent = pCurrent->pRightChild; while(0 == pCurrent->nLeftThread) pCurrent = pCurrent->pLeftChild; cout << pCurrent->cData << " "; } }while(0 != pCurrent->cData);} int main() ... { BTNode* pMyBinaryTree = new BTNode; pMyBinaryTree = CreatBinaryTree(pMyBinaryTree); BTNode* pThreadHead = ThreadBinaryTree(pMyBinaryTree); cout << endl; TraversalInorderBinaryTreeEB(pThreadHead); TraversalInorderBinaryTreeBE(pThreadHead); getchar(); getchar();}
