#pragma once
#include<iostream>
using namespace std;
enum PointInfo{LINK,THREAD};//保存节点线索信息
template<class T>
struct BinaryTreeNodeThd
{
T _data;
BinaryTreeNodeThd<T>* _pLeft;
BinaryTreeNodeThd<T>* _pRight;
PointInfo _leftThread;
PointInfo _rightThread;
BinaryTreeNodeThd(const T& data)
:_data(data)
,_pLeft(NULL)
,_pRight(NULL)
,_leftThread(LINK)
,_rightThread(LINK)
{}
};
template<class T>
class BinaryTreeThd
{
typedef BinaryTreeNodeThd<T> Node;
public:
BinaryTreeThd()
:_pRoot(NULL)
{}
BinaryTreeThd(T* arr,size_t size,const T& invalid)//创建二叉树
{
size_t index = 0;
_CreateBinaryTreeThd(_pRoot,arr,size,index,invalid);
}
//前序线索化二叉树
void PreThread()
{
Node* prev = NULL;
_PreThread(_pRoot,prev);
}
void InThread()
{
Node* prev = NULL;
_InThread(_pRoot,prev);
}
void PostThread()
{
Node* prev = NULL;
_PostThread(_pRoot,prev);
}
//前序遍历线索二叉树
void PreOrder()
{
Node* pCur = _pRoot;
while(pCur)
{
while(pCur->_leftThread == LINK)//一直访问左子树上的所有节点
{
cout<<pCur->_data;
pCur = pCur->_pLeft;
}
cout<<pCur->_data;//左子树最后一个节点
while(pCur->_rightThread == THREAD)//若右子树不存在，连续访问后继
{
pCur = pCur->_pRight;
cout<<pCur->_data;//输出后继节点
}
if(pCur->_leftThread == LINK)//
pCur = pCur->_pLeft;
else
pCur = pCur->_pRight;
}
cout<<endl;
}
void InOrder()
{
Node* pCur = _pRoot;
while(pCur)
{
while(pCur->_leftThread == LINK)
{
pCur = pCur->_pLeft;
}
cout<<pCur->_data;
while(pCur->_rightThread == THREAD)
{
pCur = pCur->_pRight;
cout<<pCur->_data;
}
pCur = pCur->_pRight;
}
}
private:
void _CreateBinaryTreeThd(Node*& pRoot, T* arr, size_t size, size_t& index, const T& invalid)
{
while(index<size && arr[index]!=invalid)
{
pRoot = new Node(arr[index]);
_CreateBinaryTreeThd(pRoot->_pLeft,arr,size,++index,invalid);
_CreateBinaryTreeThd(pRoot->_pRight,arr,size,++index,invalid);
}
}
void _PreThread(Node* pRoot,Node*& prev)
{
if(pRoot)
{
if(pRoot->_pLeft == NULL)
{
pRoot->_pLeft = prev;
pRoot->_leftThread = THREAD;
}
if(prev && prev->_pRight == NULL)
{
prev->_pRight = pRoot;
prev->_rightThread = THREAD;
}
prev = pRoot;
if(pRoot->_leftThread == LINK)
_PreThread(pRoot->_pLeft,prev);
if(pRoot->_rightThread == LINK)
_PreThread(pRoot->_pRight,prev);
}
}
void _InThread(Node* pRoot,Node*& prev)
{
if(pRoot)
{
_InThread(pRoot->_pLeft,prev);
if(pRoot->_pLeft == NULL)
{
pRoot->_pLeft = prev;
pRoot->_leftThread = THREAD;
}
if(prev && prev->_pRight == NULL)
{
prev->_pRight = pRoot;
prev->_rightThread = THREAD;
}
prev = pRoot;
if(pRoot->_rightThread == LINK)
_InThread(pRoot->_pRight,prev);
}
}
void _PostThread(Node* pRoot,Node*& prev)
{
if(pRoot)
{
_PostThread(pRoot->_pLeft,prev);
_PostThread(pRoot->_pRight,prev);
if(pRoot->_pLeft == NULL)
{
pRoot->_pLeft = prev;
pRoot->_leftThread = THREAD;
}
if(prev && prev->_pRight == NULL)
{
prev->_pRight = pRoot;
prev->_rightThread = THREAD;
}
prev = pRoot;
}
}
Node* _pRoot;
};
#include"test.h"
void FunTest()
{
char* str = "124###35##6";
BinaryTreeThd<char> bt(str,strlen(str),'#');
bt.PreThread();
bt.PreOrder();
}
int main()
{
FunTest();
system("pause");
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-79164.html
