c++学习之前序递归遍历二叉树和中序循环遍历二叉树
c++学习之前序递归遍历二叉树和中序循环遍历二叉树

c++学习之前序递归遍历二叉树和中序循环遍历二叉树
• 发表于 1年前
• 阅读 0
• 收藏 0
• 评论 0

#include<iostream.h>
#include<memory.h>

template <class Type>
class CBinaryTree
{
private:
int m_nNodeCount;
Type* m_pRootNode;//根节点
public:
CBinaryTree()
{
m_pRootNode = new Type();
m_nNodeCount = 1;
InitBinaryTree();
}

Type* GetRootNode() const
{
return m_pRootNode;
}
//初始化
void InitBinaryTree()
{
Type* pTmpNode = m_pRootNode;
for(int i=1;i<11;i++)
{
Type* pNode = new Type;
pNode->m_nData = i;
if(!bRet)//左节点添加失败则添加右节点
{
}
if(!bRet)
{
pTmpNode = pTmpNode->m_pLeftNode;
goto label;
}
}
}
//递归遍历二叉树
void IterateBinaryTree(Type *pNode)
{
if(pNode!=NULL)
{
cout<<"节点数据："<<pNode->m_nData<<endl;
}
if(pNode->m_pLeftNode!=NULL)
{
IterateBinaryTree(pNode->m_pLeftNode);
}
if(pNode->m_pRightNode!=NULL)
{
IterateBinaryTree(pNode->m_pRightNode);
}
}
//添加节点
bool AddNode(Type *pDestation,Type *pNode,int nFlag = 0)
{
if(pDestation!=NULL&&pNode!=NULL)
{
if(nFlag)
{
if(!pDestation->m_pRightNode)
{
pDestation->m_pRightNode = pNode;
}
else
{
return false;
}
}
else
{
if(!pDestation->m_pLeftNode)
{
pDestation->m_pLeftNode = pNode;
}
else
{
return false;
}
}
m_nNodeCount++;
return true;
}
return false;
}
//销毁节点
void DestroyBinaryTree(Type *pNode)
{
Type *pLeftNode,*pRightNode;
if(pNode!=NULL)
{
pLeftNode = pNode->m_pLeftNode;
pRightNode = pNode->m_pRightNode;
delete pNode;
pNode =NULL;
}
if(pLeftNode!=NULL)
{
DestroyBinaryTree(pLeftNode);
}
if(pRightNode!=NULL)
{
DestroyBinaryTree(pRightNode);
}
}
//析构函数
virtual ~CBinaryTree()
{
DestroyBinaryTree(m_pRootNode);
}
};

class CNode
{
private:
CNode *m_pLeftNode;
CNode *m_pRightNode;
int m_nData;
public:
CNode()
{
m_pLeftNode = NULL;
m_pRightNode = NULL;
m_nData = 0;
}

friend class CBinaryTree<CNode>;

virtual ~CNode()
{
m_pLeftNode = NULL;
m_pRightNode = NULL;
m_nData = 0;
}
};

int main(int argc,char* argv[])
{
CBinaryTree<CNode> BinaryTree;
BinaryTree.IterateBinaryTree(BinaryTree.GetRootNode());
return 0;
}

#include<iostream.h>
#include<memory.h>

template<class Type>
class CStact
{
private:
Type *m_pBottom;
Type *m_pTop;
int m_nStackSize;//栈大小
public:
CStact()
{
m_pBottom = NULL;
m_pTop = NULL;
m_nStackSize = 30;
}
~CStact()
{
if(m_pBottom!=NULL)
{
m_pBottom++;
delete [] m_pBottom;
}
}
bool InitStack(int nStackSize)
{
m_nStackSize = nStackSize;
try
{
m_pBottom = new Type[m_nStackSize];
m_pBottom--;//落入栈底
m_pTop = m_pBottom;//空栈
}
catch(...)
{
return false;
}
return true;
}

bool Push(Type *pNode)//入栈
{
if(m_pTop-m_pBottom>=m_nStackSize||pNode==NULL)
{
return false;
}
m_pTop++;//移动栈顶指针
memcpy(m_pTop,pNode,sizeof(Type));
return true;
}

bool Pop(Type *pNode)//出栈
{
if(m_pTop == m_pBottom)//空栈
{
return false;
}
memcpy(pNode,m_pTop,sizeof(Type));
m_pTop--;
return true;
}

bool GetTop(Type *pNode)
{
if(m_pTop == m_pBottom)//空栈
{
return false;
}
memcpy(pNode,m_pTop,sizeof(Type));
return true;
}

bool IsEmpty()
{
return (m_pTop == m_pBottom);
}
};

template <class Type>
class CBinaryTree
{
private:
int m_nNodeCount;
Type* m_pRootNode;//根节点
public:
CBinaryTree()
{
m_pRootNode = new Type();
m_nNodeCount = 1;
InitBinaryTree();
}

Type* GetRootNode() const
{
return m_pRootNode;
}
//初始化
void InitBinaryTree()
{
Type* pTmpNode = m_pRootNode;
for(int i=1;i<11;i++)
{
Type* pNode = new Type;
pNode->m_nData = i;
if(!bRet)//左节点添加失败则添加右节点
{
}
if(!bRet)
{
pTmpNode = pTmpNode->m_pLeftNode;
goto label;
}
}
}

void LoopBinaryTree()
{
CStact<CNode> Stack;
Stack.InitStack(m_nNodeCount);
Stack.Push(m_pRootNode);
Type *pNode = m_pRootNode;
while(!Stack.IsEmpty())
{
if(pNode)
{
while(pNode)//遍历左子节点，直到尽头
{
Stack.Push(pNode->m_pLeftNode);//入栈
pNode = pNode->m_pLeftNode;
}
}
else
{
Type Node;
bool bRet = Stack.Pop(&Node);//回退指针
if(bRet)
{
cout<<"节点数据 ： "<<Node.m_nData<<endl;
}
bRet = Stack.Pop(&Node);
if(bRet)
{
cout<<"节点数据 ： "<<Node.m_nData<<endl;
}
if(bRet&&Node.m_pRightNode!=NULL)
{
Stack.Push(Node.m_pRightNode);
pNode = Node.m_pRightNode;
}
}
}
}

//添加节点
bool AddNode(Type *pDestation,Type *pNode,int nFlag = 0)
{
if(pDestation!=NULL&&pNode!=NULL)
{
if(nFlag)
{
if(!pDestation->m_pRightNode)
{
pDestation->m_pRightNode = pNode;
}
else
{
return false;
}
}
else
{
if(!pDestation->m_pLeftNode)
{
pDestation->m_pLeftNode = pNode;
}
else
{
return false;
}
}
m_nNodeCount++;
return true;
}
return false;
}

//销毁节点
void DestroyBinaryTree(Type *pNode)
{
Type *pLeftNode,*pRightNode;
if(pNode!=NULL)
{
pLeftNode = pNode->m_pLeftNode;
pRightNode = pNode->m_pRightNode;
delete pNode;
pNode = NULL;
}
if(pLeftNode!=NULL)
{
DestroyBinaryTree(pLeftNode);
}
if(pRightNode!=NULL)
{
DestroyBinaryTree(pRightNode);
}
}
//析构函数
virtual ~CBinaryTree()
{
DestroyBinaryTree(m_pRootNode);
}

};

class CNode
{
private:
CNode *m_pLeftNode;
CNode *m_pRightNode;
int m_nData;
public:
CNode()
{
m_pLeftNode = NULL;
m_pRightNode = NULL;
m_nData = 0;
}

friend class CBinaryTree<CNode>;

virtual ~CNode()
{
m_pLeftNode = NULL;
m_pRightNode = NULL;
m_nData = 0;
}
};

int main(int argc,char* argv[])
{
CBinaryTree<CNode> BinaryTree;
BinaryTree.LoopBinaryTree();
return 0;
}

×