二叉树的线索化
//本次练习的是 二叉树线索化的 前·中·后序 《 线索化 》 的递归和非递归实现
#include
using namespace std;
enum Type
{
LINK,
THREAD
};
template
struct BinaryTreeNode
{
T _date;
BinaryTreeNode
Type _leftType;
BinaryTreeNode
Type _rightType;
BinaryTreeNode
BinaryTreeNode(const T& date)
:_date(date)
, _left(NULL)
, _leftType(LINK)
, _right(NULL)
, _rightType(LINK)
, _parent(NULL)
{}
};
template
class BinaryTreeThread
{
public:
BinaryTreeThread()
{};
BinaryTreeThread(const T* arr, size_t size)
{
size_t index = 0;
_root = _Create(arr, index, size);
}
// 以下用的是 递归
void InOrderThread() //中序线索化
{
BinaryTreeNode
_InOrderThread(_root,prev);
}
void InOrder() //中序遍历
{
_InOrder(_root);
cout << endl;
}
void PrevOrderThread() //前序线索化
{
BinaryTreeNode
_PrevOrderThread(_root,prev);
}
void PrevOrder() //前序遍历
{
_PrevOrder(_root);
cout << endl;
}
void LastOrderThread() //后序线索化
{
BinaryTreeNode
_LastOrderThread(_root, prev);
}
void LastOrder() //后序遍历
{
_LastOrder(_root);
cout << endl;
}
//以下用的不是递归
void InOrder_Not() //中序线索化
{
_InOrder_Not(_root);
cout << endl;
}
void PrevOrder_Not() //前序线索化
{
_PrevOrder_Not(_root);
cout << endl;
}
void LastOrder_Not() //后序线索化
{
_LastOrder_Not(_root);
}
// 以下用的是 递归
protected:
BinaryTreeNode
{
if (index >= size || arr[index] == '#')
{
return NULL;
}
BinaryTreeNode
root->_left = _Create(arr, ++index, size);
if (root->_left != NULL)
{
root->_left->_parent = root;
}
root->_right = _Create(arr, ++index, size);
if (root->_right != NULL)
{
root->_right->_parent = root;
}
return root;
}
void _InOrderThread(BinaryTreeNode
{
if (root == NULL)
{
return;
}
_InOrderThread(root->_left,prev); //递归左
if (root != NULL && root->_left == NULL) //左链接
{
root->_leftType = THREAD;
root->_left = prev;
}
if (prev != NULL && prev->_right == NULL) //右链接
{
prev->_rightType = THREAD;
prev->_right = root;
}
prev = root;
_InOrderThread(root->_right,prev); //递归右
}
void _InOrder(const BinaryTreeNode
{
if (root == NULL)
{
return;
}
if (root->_leftType == LINK)
{
_InOrder(root->_left);
}
cout << root->_date << " ";
if (root->_rightType == LINK)
{
_InOrder(root->_right);
}
}
void _PrevOrderThread(BinaryTreeNode
{
if (root == NULL)
{
return;
}
if (root != NULL && root->_left == NULL)
{
root->_leftType = THREAD;
root->_left = prev;
}
if (prev != NULL && prev->_right == NULL)
{
prev->_rightType = THREAD;
prev->_right = root;
}
prev = root;
if (root->_leftType == LINK) //这个节点已经线索化 所以要判断为LINK
{
_PrevOrderThread(root->_left, prev);
}
if (root->_rightType == LINK) //这个节点已经线索化
{
_PrevOrderThread(root->_right, prev);
}
}
void _PrevOrder(BinaryTreeNode
{
if (root == NULL)
{
return;
}
cout << root->_date<<" ";
if (root->_leftType == LINK)
{
_PrevOrder(root->_left);
}
if (root->_rightType == LINK)
{
_PrevOrder(root->_right);
}
}
void _LastOrderThread(BinaryTreeNode
{
if (root == NULL)
{
return;
}
_LastOrderThread(root->_left,prev);
_LastOrderThread(root->_right,prev);
if (root != NULL && root->_left == NULL)
{
root->_leftType = THREAD;
root->_left = prev;
}
if (prev != NULL && prev->_right == NULL)
{
prev->_rightType = THREAD;
prev->_right = root;
}
prev = root;
}
void _LastOrder(BinaryTreeNode
{
if (root == NULL)
{
return;
}
if (root->_leftType == LINK)
{
_LastOrder(root->_left);
}
if (root->_rightType == LINK)
{
_LastOrder(root->_right);
}
cout << root->_date << " ";
}
// 以下用的不是递归
protected:
void _InOrder_Not(BinaryTreeNode
{
BinaryTreeNode
while (cur != NULL)
{
while (cur != NULL && cur->_leftType == LINK)
{
cur = cur->_left;
}
cout << cur->_date << " ";
while (cur != NULL && cur->_rightType == THREAD)
{
cur = cur->_right;
cout << cur->_date << " ";
}
cur = cur->_right;
}
}
void _PrevOrder_Not(BinaryTreeNode
{
BinaryTreeNode
while (cur != NULL)
{
cout << cur->_date << " ";
while (cur != NULL && cur->_leftType == LINK)
{
cur = cur->_left;
cout << cur->_date << " ";
}
while (cur != NULL && cur->_rightType == THREAD)
{
cur = cur->_right;
cout << cur->_date << " ";
}
cur = cur->_right;
}
}
void _LastOrder_Not(BinaryTreeNode
{
if (_root == NULL)
{
return;
}
BinaryTreeNode
BinaryTreeNode
while (cur != _root)
{
while (cur != NULL && cur->_leftType == LINK && cur->_left != prev)// 当左子节点已经遍历完成就往右走
{
cur = cur->_left; //跳到最左节点
}
if (cur != NULL && cur->_rightType == THREAD)
{
cout << cur->_date << " ";
prev = cur;
cur = cur->_right;
}
if (cur == _root) //如果跳到了_root 就表示已经遍历完成
{
cout << cur->_date << " ";
break;
}
//此时 右树已经遍历完成
if (cur != NULL && cur->_rightType == LINK && cur->_right == prev)//如果根节点的右子树已经遍历完成 则跳到根节点的父亲节点
{
cout << cur->_date << " ";
prev = cur;
cur = cur->_parent;
}
/*if (cur != NULL && cur->_leftType == LINK && cur->_left == prev)
{
cout << cur->_date << " ";
prev = cur;
cur = cur->_right;
}*/
if (cur != NULL && cur->_rightType == LINK)
{
cur = cur->_right;
}
}
}
protected:
BinaryTreeNode
};
void Test1()
{
int arr[10] = { 1, 2, 3, '#','#', 4, '#', '#', 5, 6 };
BinaryTreeThread
t1.InOrderThread();
t1.InOrder();
t1.InOrder_Not();
cout << endl;
BinaryTreeThread
t2.PrevOrderThread();
t2.PrevOrder();
t2.PrevOrder_Not();
cout << endl;
BinaryTreeThread
t3.LastOrderThread();
t3.LastOrder();
t3.LastOrder_Not();
}
int main()
{
Test1();
return 0;
}
成都创新互联公司是一家集网站建设,琼中黎族企业网站建设,琼中黎族品牌网站建设,网站定制,琼中黎族网站建设报价,网络营销,网络优化,琼中黎族网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
本文名称:二叉树的线索化
文章路径:http://myzitong.com/article/iecjjo.html