1用程序实现由先序序列确定该二叉树；2以中序输入方式创建二叉树，3对二叉树进行后序遍历
你查查前序遍历，中序遍历，后序遍历，这三种方式都是递归的方式，代码相似，唯一的不同就是读取当前节点的值的位置是在递归前，还是递归中，或者递归后。可能你现在还没明白，那么你这样想一想，二叉树递归，每个节点往下递归，那么肯定分左节点递归，还是右节点递归。如果你在进入一个节点后，第一件事就是把这个节点的值读出来，然后调用递归，递归左节点，再调用递归，递归右节点。这就是前序遍历。如果你进入一个节点，先调用递归，递归左节点，再去读取当前的节点值，最后递归右节点，那这就是中序遍历。后续遍历就是左右都递归了，再读取当前节点值。其实我在理解递归的时候，脑海里面有个人分开腿站着，然后有个球，如果这个人把球放在左边，就是前序遍历，右边就是后续遍历，如果是两腿之间，就是中序遍历。
#pragma once
#include "MyString.h"
#include "Clist.h"
#include
#define max(x, y) ((x) > (y) ? (x) : (y))
template
class CTreeNode //节点
{
public:
CTreeNode(); //构造函数
CTreeNode(const T& Elme);//默认构造
~CTreeNode(); //析构函数
public:
CTreeNode *m_Parent;//父节点
CTreeNode *m_Rigth; //右孩子
CTreeNode *m_Left; //右孩子
int m_Height; //高度
char Flag; //标记
T m_Data; //数据成
Clist<T1*> m_Object; //对象
Clist<T1*> Data; //挂链表
};
template
CTreeNode::CTreeNode()
{
// Data.m_HeadNode = NULL;
}
template
CTreeNode::CTreeNode(const T& Elme)
:m_Data(Elme)
{
Flag = 1;
m_Left = NULL;
m_Rigth = NULL;
m_Parent = NULL;
m_Height = 0;
}
template
CTreeNode::~CTreeNode()//析构函数
{
}
template
class CTree
{
public:
CTree();//构造函数
~CTree();//析构函数
//增 删 改 查 清空 判断 表是否为空 (递归和非递归)遍历(前序 中序 后序)
void AddTreeNode(const T& Elme);
void AddTreeNode(const T& Elme,T1& obj); //增加节点
void DeleteTreeNode(const T& Elme); //删除节点
void DeleteTreeNode(const T& Elme,T1& obj); //删除节点
void AmendTreeNode(); //修改节点
CTreeNode<T,T1>* FindTreeNode(const T& Elme); //查询节点
void FrontTraverseTree(); //前序遍历树
void MiddleTraverseTree(); //中序遍历树
void BackTraverseTree(); //后序遍历树
void TierTraverseTree(); //层序遍历树
void LitfRotation(CTreeNode <T,T1> *lp1, CTreeNode <T,T1> *lp2); //左旋转
void RightRotation(CTreeNode <T,T1> *lp1, CTreeNode <T,T1> *lp2); //右旋转
//void FrontRecursionTraverseTree(CTreeNode *lpAddress); //前序递归遍历树
//void MiddleRecursionTraverseTree(CTreeNode *lpAddress); //中序递归遍历树
//void BackRecursionTraverseTree(CTreeNode *lpAddress); //后序递归遍历树
bool IsLength(); //判断树是否为空
void ClearTree(); //清空树
CTreeNode<T,T1>* ObtainprootNode(); //获取根节点
int ObtainLength(); //获取数量
int Height(CTreeNode<T,T1>*lpNode); //获取高度
void MaintenanceHeight(CTreeNode <T,T1>*lpNode); //维护高度
private:
CTreeNode *m_lproot;
int m_nCount;
};
template
CTree::CTree()
{
m_nCount = 0;
m_lproot = NULL;
}
template
CTree::~CTree()
{
}
template
CTreeNode * CTree::ObtainprootNode() //获取跟节点
{
return m_lproot;
}
template
int CTree::ObtainLength() //获取数量
{
return m_nCount;
}
template
bool CTree::IsLength() //判断数是否为空
{
return m_nCount == 0;
}
template
int CTree::Height(CTreeNode*lpNode)//获取高度
{
return lpNode == NULL ? -1 : lpNode->m_Height;
}
template
void CTree::MaintenanceHeight(CTreeNode *lpNode) //维护高度 平衡树
{
while (lpNode != NULL)
{
lpNode->m_Height = max(Height(lpNode->m_Left), Height(lpNode->m_Rigth)) + 1;
if (abs(Height(lpNode->m_Left) - Height(lpNode->m_Rigth))>= 2)
{
CTreeNode *lpk1 = lpNode; //获取添加
CTreeNode *lpk2 = NULL;
CTreeNode *lpk3 = NULL;
if (Height(lpk1->m_Left) - Height(lpk1->m_Rigth) > 0) //判断左右节点那边重
{
lpk2 = lpk1->m_Left;
}
else
{
lpk2 = lpk1->m_Rigth;
}
if (Height(lpk2->m_Left) - Height(lpk2->m_Rigth) > 0) //判断左右节点那边重
{
lpk3 = lpk2->m_Left;
}
else
{
lpk3 = lpk2->m_Rigth;
}
/*
k1
k2
k3
*/
if (lpk2 == lpk1->m_Left && lpk3 == lpk2->m_Left)
{
RightRotation(lpk1, lpk2);
}
/*
k1
k2
k3
*/
else if (lpk2 == lpk1->m_Rigth && lpk3 == lpk2->m_Rigth)
{
LitfRotation(lpk1, lpk2);
}
/*
k1 k1
k2 k3 k3
k3 k2 k2 k1
*/
else if(lpk2 == lpk1->m_Left && lpk3 == lpk2->m_Rigth)
{
LitfRotation(lpk2,lpk3);
RightRotation(lpk1,lpk3);
}
/*
k1 k1
k2 k3
k3 k2
*/
else
{
RightRotation(lpk2, lpk3);
LitfRotation(lpk1,lpk3);
}
}
lpNode = lpNode->m_Parent;
}
}
/* D D
k1 K2
A k2 K1 C
B C A B
*/
template
void CTree::LitfRotation(CTreeNode *lp1, CTreeNode *lp2) //左旋转
{
CTreeNode *lpA = lp1->m_Left;
CTreeNode *lpB = lp2->m_Left;
CTreeNode *lpC = lp2->m_Rigth;
CTreeNode *lpD = lp1->m_Parent;
//修改D
if (lpD == NULL)
{
m_lproot = lp2;
}
else if (lpD->m_Left == lp1)
{
lpD->m_Left = lp2;
}
else
{
lpD->m_Rigth = lp2;
}
//修改B
if (lpB != NULL)
{
lpB->m_Parent = lp1;
}
//修改K1
lp1->m_Parent = lp2;
lp1->m_Rigth = lpB;
//修改K2
lp2->m_Parent = lpD;
lp2->m_Left = lp1;
//调整高度
lp1->m_Height = max(Height(lpA),Height(lpB)) +1;
lp2->m_Height = max(Height(lp1), Height(lpC)) + 1;
}
/*
D D
k1 K2
k2 C A K1
A B B C
*/
template
void CTree::RightRotation(CTreeNode *lp1, CTreeNode *lp2) //右旋转
{
CTreeNode *lpA = lp2->m_Left;
CTreeNode *lpB = lp2->m_Rigth;
CTreeNode *lpC = lp1->m_Rigth;
CTreeNode *lpD = lp1->m_Parent;
//修改D
if (lpD == NULL)
{
m_lproot = lp2;
}
else if (lpD->m_Left == lp1)
{
lpD->m_Left = lp2;
}
else
{
lpD->m_Rigth = lp2;
}
//修改B
if (lpB != NULL)
{
lpB->m_Parent = lp1;
}
//修改lp1
lp1->m_Left = lpB;
lp1->m_Parent = lp2;
//修改lp2
lp2->m_Parent = lpD;
lp2->m_Rigth = lp1;
//调整高度
lp1->m_Height = max(Height(lpB), Height(lpC)) + 1;
lp2->m_Height = max(Height(lpA), Height(lp1)) + 1;
}
template
void CTree::AddTreeNode(const T& Elme)//增加
{
CTreeNode* lpNew = new CTreeNode(Elme); //new节点
if (IsLength())
{
m_lproot = lpNew;
m_nCount++;
return ;
}
CTreeNode* lpTemp = m_lproot;//获取根节点
while (lpTemp != NULL)
{
if (lpTemp->m_Data > lpNew->m_Data) //判断加入数据大小
{
if (lpTemp->m_Left == NULL)
{
lpTemp->m_Left = lpNew;
lpNew->m_Parent = lpTemp;
break;
}
lpTemp = lpTemp->m_Left;
}
else if (lpTemp->m_Data < lpNew->m_Data)
{
if (lpTemp->m_Rigth == NULL)
{
lpTemp->m_Rigth = lpNew;
lpNew->m_Parent = lpTemp;
break;
}
lpTemp = lpTemp->m_Rigth;
}
else
{
return; //等于 不处理
}
}
m_nCount++;
MaintenanceHeight(lpNew->m_Parent);
}
template
void CTree::AddTreeNode(const T& Elme,T1& obj)//增加
{
CTreeNode* lpNew = new CTreeNode(Elme); //new节点
if (IsLength())
{
lpNew->m_Object.HeadAddClistNode(&obj);
m_lproot = lpNew;
m_nCount++;
return ;
}
CTreeNode<T,T1>* lpTemp = m_lproot;//获取根节点
while (lpTemp != NULL)
{
if (lpTemp->m_Data > lpNew->m_Data) //判断加入数据大小
{
if (lpTemp->m_Left == NULL)
{
lpTemp->m_Left = lpNew;
lpNew->m_Parent = lpTemp;
lpNew->m_Object.HeadAddClistNode(&obj);
break;
}
lpTemp = lpTemp->m_Left;
}
else if (lpTemp->m_Data < lpNew->m_Data)
{
if (lpTemp->m_Rigth == NULL)
{
lpTemp->m_Rigth = lpNew;
lpNew->m_Parent = lpTemp;
lpNew->m_Object.HeadAddClistNode(&obj);
break;
}
lpTemp = lpTemp->m_Rigth;
}
else
{
lpTemp->Data.HeadAddClistNode(&obj);
// lpTemp->m_Object = obj;
return; //等于 不处理
}
}
m_nCount++;
MaintenanceHeight(lpNew->m_Parent);
}
template
CTreeNode * CTree::FindTreeNode(const T& Elme)//查询
{
CTreeNode* lpTemp = m_lproot;
if (lpTemp == NULL)
{
return NULL;
}
while (lpTemp != NULL)
{
if (lpTemp->m_Data > Elme)
{
lpTemp = lpTemp->m_Left;
}
else if (lpTemp->m_Data < Elme)
{
lpTemp = lpTemp->m_Rigth;
}
else
{
return lpTemp;
}
}
return NULL;
}
template
void CTree::DeleteTreeNode(const T& Elme)//删除
{
CTreeNode* lpDelete = FindTreeNode(Elme);
if (lpDelete == NULL)
{
return;
}
m_nCount--;
while (true)
{
CTreeNode<T,T1>* lpParent = lpDelete->m_Parent;
//叶子节点
if (lpDelete->m_Left == NULL && lpDelete->m_Rigth == NULL)
{
//根节点
if (lpParent == NULL)
{
m_lproot = NULL;
}
//左节点
else if (lpParent->m_Left == lpDelete)
{
lpParent->m_Left = NULL;
}
//右节点
else
{
lpParent->m_Rigth = NULL;
}
MaintenanceHeight(lpParent);//维护树的高度
delete lpDelete;
lpDelete = NULL;
break;
}
//带两个子节点
else if (lpDelete->m_Left != NULL && lpDelete->m_Rigth != NULL)
{
CTreeNode<T,T1>* lpMaxNode = lpDelete->m_Left;
//找到要删除左边最大值
while (lpMaxNode->m_Rigth != NULL)
{
lpMaxNode = lpMaxNode->m_Rigth;
}
//交换数据
lpDelete->m_Data = lpMaxNode->m_Data;
lpMaxNode->Data.m_HeadNode = lpDelete->Data.m_HeadNode ;
//删除节点
lpDelete = lpMaxNode;
continue; // 删除左边最大值肯定是叶子节点或带一个还子节点的子树
}
//带一个子节点
else
{
CTreeNode<T,T1>* lpChild = NULL;
//左孩子
if (lpDelete->m_Left != NULL)
{
lpChild = lpDelete->m_Left;
}
//右孩子
else
{
lpChild = lpDelete->m_Rigth;
}
//删除根节点
if (lpParent == NULL)
{
m_lproot = lpChild;
lpChild->m_Parent = NULL;
}
else
{
if (lpParent->m_Left == lpDelete)
{
lpParent->m_Left = lpChild;
}
else
{
lpParent->m_Rigth = lpChild;
}
lpChild->m_Parent = lpParent;
}
MaintenanceHeight(lpParent);//维护树的高度
delete lpDelete;
lpDelete = NULL;
break;
}
}
}
template
void CTree::DeleteTreeNode(const T& Elme,T1& obj)//删除
{
CTreeNode* lpDelete = FindTreeNode(Elme);
if (lpDelete == NULL)
{
return;
}
m_nCount--;
while (true)
{
CTreeNode<T,T1>* lpParent = lpDelete->m_Parent;
//叶子节点
if (lpDelete->m_Left == NULL && lpDelete->m_Rigth == NULL)
{
//根节点
if (lpParent == NULL)
{
m_lproot = NULL;
}
//左节点
else if (lpParent->m_Left == lpDelete)
{
lpParent->m_Left = NULL;
}
//右节点
else
{
lpParent->m_Rigth = NULL;
}
MaintenanceHeight(lpParent);//维护树的高度
delete lpDelete;
lpDelete = NULL;
break;
}
//带两个子节点
else if (lpDelete->m_Left != NULL && lpDelete->m_Rigth != NULL)
{
CTreeNode<T,T1>* lpMaxNode = lpDelete->m_Left;
//找到要删除左边最大值
while (lpMaxNode->m_Rigth != NULL)
{
lpMaxNode = lpMaxNode->m_Rigth;
}
//交换数据
lpDelete->m_Data = lpMaxNode->m_Data;
lpMaxNode->Data.m_HeadNode = lpDelete->Data.m_HeadNode ;
//删除节点
lpDelete = lpMaxNode;
continue; // 删除左边最大值肯定是叶子节点或带一个还子节点的子树
}
//带一个子节点
else
{
CTreeNode<T,T1>* lpChild = NULL;
//左孩子
if (lpDelete->m_Left != NULL)
{
lpChild = lpDelete->m_Left;
}
//右孩子
else
{
lpChild = lpDelete->m_Rigth;
}
//删除根节点
if (lpParent == NULL)
{
m_lproot = lpChild;
lpChild->m_Parent = NULL;
}
else
{
if (lpParent->m_Left == lpDelete)
{
lpParent->m_Left = lpChild;
}
else
{
lpParent->m_Rigth = lpChild;
}
lpChild->m_Parent = lpParent;
}
MaintenanceHeight(lpParent);//维护树的高度
delete lpDelete;
lpDelete = NULL;
break;
}
}
}
template
void CTree::FrontTraverseTree() //前序遍历
{
CTreeNode<T,T1> *lpAddress = m_lproot;
CHeap<CTreeNode *> heap;
while (true)
{
while (lpAddress != NULL)
{
printf("%d ", lpAddress->m_Data);
heap.Heappush(lpAddress);
lpAddress = lpAddress->m_Left;
}
if (heap.IsLength())
{
break;
}
CTreeNode<T> *lpPop = heap.back();
heap.Heappop();
lpAddress = lpPop->m_Rigth;
}
}
template
void CTree::MiddleTraverseTree() //中序遍历
{
CTreeNode *lpAddress = m_lproot;
CHeap *> heap;
while (true)
{
while (lpAddress != NULL)
{
heap.Heappush(lpAddress);
lpAddress = lpAddress->m_Left;
}
if (heap.IsLength())
{
break;
}
CTreeNode<T,T1> *lpPop = heap.back();
printf("%d ", lpPop->m_Data);
heap.Heappop();
lpAddress = lpPop->m_Rigth;
}
}
template
void CTree::BackTraverseTree() //后序遍历
{
CTreeNode *lpAddress = m_lproot;
CHeap *> heap;
CTreeNode *lpOldNode = NULL;
while (true)
{
while (lpAddress != NULL)
{
heap.Heappush(lpAddress);
lpAddress = lpAddress->m_Left;
}
if (heap.IsLength())
{
break;
}
CTreeNode *lpPop = heap.back();
heap.Heappop();
if (lpPop->m_Rigth == NULL)
{
printf("%d ", lpPop->m_Data);
lpOldNode = lpPop;
}
else if (lpPop->m_Rigth == lpOldNode)
{
printf("%d ", lpPop->m_Data);
lpAddress = NULL;
lpOldNode = lpPop;
continue;
}
else
{
heap.Heappush(lpPop);
}
lpAddress = lpPop->m_Rigth;
}
}
template //层序遍历模板
void CTree::TierTraverseTree()
{
CTreeNodelpAddress = m_lproot;
if (lpAddress == NULL)
{
return;
}
CQueue> queue;
while (true)
{
printf("%d[%d] ", lpAddress->m_Data,lpAddress->m_Height);
if (lpAddress->m_Left != NULL)
{
queue.Queuepush(lpAddress->m_Left);
}
if (lpAddress->m_Rigth != NULL)
{
queue.Queuepush(lpAddress->m_Rigth);
}
if (queue.IsLength())
{
break;
}
lpAddress = queue.front();
queue.Queuepop();
}
printf("\r\n");
}