线索二叉树的前、中、后序创建和遍历

#pragma once #include <iostream> #include <string> using namespace std; enum NodeFlag { LINK, THREAD }; template <typename T> struct BinaryTreeNodeThd { BinaryTreeNodeThd(const T& data) : _data(data) , _parents(NULL) , _pLeftChild(NULL) , _LeftFlag(LINK) , _pRightChild(NULL) , _RightFlag(LINK) {} T _data;//数据域 BinaryTreeNodeThd<T>* _parents;//双亲指针 BinaryTreeNodeThd<T>* _pLeftChild;//左孩子指针 NodeFlag _LeftFlag;//左孩子指针的标记 BinaryTreeNodeThd<T>* _pRightChild;//右孩子指针 NodeFlag _RightFlag;//右孩子指针的标记 }; template <typename T> class BinaryTreeThd { typedef BinaryTreeNodeThd<T> Node; protected: Node* _pRoot; public: BinaryTreeThd()//无参构造函数 {} BinaryTreeThd(const T* arr, size_t size, const T& invalid)//使用数组内的数据构造二叉树 { size_t index = 0;// 数组下标，因为要传引用，所以用一个表量表示 _CreateTree(_pRoot, arr, size, index, invalid);//创建树 } void PreThread() { Node* pPre = NULL; _PreThread(_pRoot, pPre); cout << "BinaryTree PreThread done" << endl << endl; } void PreOrderThd() { cout << "BinaryThreadTree PreOrder: "; Node* pCur = _pRoot; while (pCur) { while (pCur && pCur->_LeftFlag == LINK)//查找最左节点，并访问路径上的节点 { cout << pCur->_data << " "; pCur = pCur->_pLeftChild; } cout << pCur->_data << " ";//访问最左节点 pCur = pCur->_pRightChild;//将最左节点的右孩子当做一个新的子树处理 } cout << endl << endl; } void InThread() { Node* pPre = NULL; _InThread(_pRoot, pPre); cout << "BinaryTree InThread done" << endl << endl; } void InOrderThd() { if (NULL == _pRoot) return; cout << "BinaryThreadTree InOrder: "; Node* pCur = _pRoot; while (pCur) { while (LINK == pCur->_LeftFlag)//当前节点的左孩子没有被线索化 pCur = pCur->_pLeftChild; cout << pCur->_data << " "; while (pCur->_RightFlag == THREAD)/*节点已经取到最左的几点并访问过了， 此时判断右节点标记是否为THREAD，有则证明原二叉树的此结点的右节点不存在， 被线索成后继，所以访问他的后继，并且可能存在左单支树，使用while循环*/ { pCur = pCur->_pRightChild; cout << pCur->_data << " "; } pCur = pCur->_pRightChild;/*上述while判断的当前节点的右标记不是THREAD，即没有被线索化， 所以将其右子树当做新子树重新开始访问*/ } cout << endl << endl; } void PostThread() { Node* pPre = NULL; _PostThread(_pRoot, pPre); cout << "BinaryTree PostThread done" << endl << endl; } void PostOrderThd() { cout << "BinaryThreadTree PostOrder: "; if (NULL == _pRoot) return; Node* pCur = _pRoot; Node* pPre = NULL; while (pCur) { while (pPre != pCur->_pLeftChild && LINK == pCur->_LeftFlag)//查找最左节点 pCur = pCur->_pLeftChild; while (pCur && THREAD == pCur->_RightFlag)//持续访问后继节点 { cout << pCur->_data << " ";//访问当前节点（第一次进来为最左节点） pPre = pCur;//更新pPre pCur = pCur->_pRightChild;//继续访问后继节点 } if (pCur == _pRoot)//判断是否根节点，放置左、右单支子树 { cout << pCur->_data << " " << endl << endl; return; } while(pCur && pPre == pCur->_pRightChild)/*当前节点的孩子节点已访问过 （因为线索化后右孩子指向孩子，未线索化右孩子指向右孩子） 即是判断上一节点是否访问过，访问过则寻找双亲节点*/ { cout << pCur->_data << " ";//前一模块未访问，所以先访问该节点 pPre = pCur;//更新pPre pCur = pCur->_parents;//查找双亲节点 } if (pCur && LINK == pCur->_RightFlag)//经过以上，已将子树的左子树访问完毕，开始访问子树的右子树 pCur = pCur->_pRightChild; } cout << endl << endl; } private: void _CreateTree(Node*& pRoot, const T* arr, size_t size, size_t& index, const T& invalid)// 创建树 { if (index < size && arr[index] != invalid)//若下标索引小于元素个数且当前元素不为无效值，才使用数据创建此节点 { pRoot = new Node(arr[index]); _CreateTree(pRoot->_pLeftChild, arr, size, ++index, invalid); if (pRoot->_pLeftChild)//若该节点的右孩子存在，则将此节点赋给右孩子的双亲，防止叶子节点无左右孩子 pRoot->_pLeftChild->_parents = pRoot; _CreateTree(pRoot->_pRightChild, arr, size, ++index, invalid); if (pRoot->_pRightChild) pRoot->_pRightChild->_parents = pRoot; } } void _PreThread(Node*& pRoot, Node*& pPre) { if (NULL == pRoot) return; if (NULL == pRoot->_pLeftChild)//若左孩子不存在，则将左孩子线索化，指向双亲 { pRoot->_pLeftChild = pPre; pRoot->_LeftFlag = THREAD;//改变标记 } if (pPre && NULL == pPre->_pRightChild)//若pPre存在，且pPre的右孩子不存在，将pPre的右孩子线索化，指向孩子节点 {/*因为线索化后，右孩子节点指向孩子节点，在当前节点时，并不明确它的孩子是谁，所以只能将保存的上一节点的右孩子线索化 且最后一个节点的右孩子不用线索化，因为无孩子*/ pPre->_pRightChild = pRoot; pPre->_RightFlag = THREAD;//改变标记 } pPre = pRoot;//更新pPre节点 if (pRoot->_LeftFlag == LINK)//若当前节点的左孩子的左标记为没有线索化，才递归 _PreThread(pRoot->_pLeftChild, pPre); if(pRoot->_RightFlag == LINK)//若当前节点的右孩子的右标记为没有线索化，才递归 _PreThread(pRoot->_pRightChild, pPre); } void _InThread(Node*& pRoot, Node*& pPre) { if (NULL == pRoot) return; if (pRoot->_LeftFlag == LINK)//若当前节点的左孩子的左标记为没有线索化，才递归 _InThread(pRoot->_pLeftChild, pPre); //_LeftFlag if (NULL == pRoot->_pLeftChild)//若左孩子不存在，则将左孩子线索化，指向双亲 { pRoot->_pLeftChild = pPre; pRoot->_LeftFlag = THREAD;//改变标记 } if (pPre && NULL == pPre->_pRightChild)//若pPre存在，且pPre的右孩子不存在，将pPre的右孩子线索化，指向孩子节点 {/*因为线索化后，右孩子节点指向孩子节点，在当前节点时，并不明确它的孩子是谁，所以只能将保存的上一节点的右孩子线索化 且最后一个节点的右孩子不用线索化，因为无孩子*/ pPre->_pRightChild = pRoot; pPre->_RightFlag = THREAD;//改变标记 } pPre = pRoot;//更新pPre节点 if (pRoot->_RightFlag == LINK)//若当前节点的右孩子的右标记为没有线索化，才递归 _InThread(pRoot->_pRightChild, pPre); } void _PostThread(Node*& pRoot, Node*& pPre) { if (NULL == pRoot) return; if (pRoot->_LeftFlag == LINK)//若当前节点的左孩子的左标记为没有线索化，才递归 _PostThread(pRoot->_pLeftChild, pPre); if (pRoot->_RightFlag == LINK)//若当前节点的右孩子的右标记为没有线索化，才递归 _PostThread(pRoot->_pRightChild, pPre); if (NULL == pRoot->_pLeftChild)//若左孩子不存在，则将左孩子线索化，指向双亲 { pRoot->_pLeftChild = pPre; pRoot->_LeftFlag = THREAD;//改变标记 } if (pPre && NULL == pPre->_pRightChild)//若pPre存在，且pPre的右孩子不存在，将pPre的右孩子线索化，指向孩子节点 {/*因为线索化后，右孩子节点指向孩子节点，在当前节点时，并不明确它的孩子是谁，所以只能将保存的上一节点的右孩子线索化 且最后一个节点的右孩子不用线索化，因为无孩子*/ pPre->_pRightChild = pRoot; pPre->_RightFlag = THREAD;//改变标记 } pPre = pRoot;//更新pPre节点 } }; void FunTest() { //char arr[] = "124##5##36##7"; //char* arr = "124###35##6"; char* arr = "12#3##45#6#7##8"; BinaryTreeThd<char> bt(arr, strlen(arr), '#'); BinaryTreeThd<char> bt1(arr, strlen(arr), '#'); BinaryTreeThd<char> bt2(arr, strlen(arr), '#'); bt.PreThread(); bt.PreOrderThd(); bt1.InThread(); bt1.InOrderThd(); bt2.PostThread(); bt2.PostOrderThd(); }