?? tree.h
字號:
// Tree.h: interface for the Tree class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_TREE_H__703FFCCE_C340_4198_98E7_00F503CF8261__INCLUDED_)
#define AFX_TREE_H__703FFCCE_C340_4198_98E7_00F503CF8261__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "TreeNode.h"
#include "DualTagTreeNode.h"
#include "LeftLinkTreeNode.h"
#include <queue>
#include <stack>
template <class T>
class Tree
{
private:
TreeNode<T>* root; //樹根結(jié)點
//返回current父節(jié)點,由Parent調(diào)用
TreeNode<T>* getParent(TreeNode<T>* root,TreeNode<T>* current);
void DestroyNodes(TreeNode<T>*root); //刪除root為根的子樹
public:
Tree(); //構(gòu)造函數(shù)
Tree(DualTagTreeNode<T>* nodeArray,int count); //構(gòu)造函數(shù),利用雙標(biāo)記位先根次序構(gòu)造樹
Tree(LeftLinkTreeNode<T>* nodeArray,int count); //構(gòu)造函數(shù),利用左鏈層次順序構(gòu)造樹
virtual ~Tree(); //析構(gòu)函數(shù)
TreeNode<T>* getRoot(); //返回樹中的根結(jié)點
void CreateRoot(const T& rootValue); //創(chuàng)建樹的根結(jié)點，使根結(jié)點元素的值為rootValue
bool isEmpty(); //判斷是否為空樹，若是則返回true
TreeNode<T>* Parent(TreeNode<T>* current); //返回current父節(jié)點
TreeNode<T>* PrevSibling(TreeNode<T>* current); //返回current的前一個鄰居結(jié)點
TreeNode<T>* PrevSibling2(TreeNode<T>* current); //返回current的前一個鄰居結(jié)點
void DeleteSubTree(TreeNode<T>* subroot); //釋放以root為根的子樹的所有結(jié)點
void RootFirstTraverse(TreeNode<T>* root); //先根深度優(yōu)先周游樹
void RootLastTraverse(TreeNode<T>* root); //后根深度優(yōu)先周游樹
void WidthTraverse(TreeNode<T>* root); //寬度優(yōu)先周游樹
void WidthTraverse2(TreeNode<T>* root); //寬度優(yōu)先周游樹:版本2
};
template <class T>
Tree<T>::Tree()
{//構(gòu)造函數(shù)
root=NULL;
}
template <class T>
Tree<T>::Tree(DualTagTreeNode<T>* nodeArray,int count)
{
//使用STL中的stack
using std::stack;
stack<TreeNode<T>* > aStack;
//準(zhǔn)備建立根結(jié)點
TreeNode<T>* pointer=new TreeNode<T>;
root=pointer;
//處理一個結(jié)點
for(int i=0;i<count-1;i++)
{
pointer->setValue(nodeArray[i].info);
if(nodeArray[i].rtag==0)
aStack.push(pointer);
else
pointer->setSibling(NULL);
TreeNode<T>* temppointer=new TreeNode<T>;
if(nodeArray[i].ltag==0)
pointer->setChild(temppointer);
else
{
pointer->setChild(NULL);
pointer=aStack.top();
aStack.pop();
pointer->setSibling(temppointer);
}
pointer=temppointer;
}
//處理最后一個結(jié)點
pointer->setValue(nodeArray[count-1].info);
pointer->setChild(NULL);
pointer->setSibling(NULL);
}
template <class T>
Tree<T>::Tree(LeftLinkTreeNode<T>* nodeArray,int count)
{//構(gòu)造函數(shù),利用左鏈層次順序構(gòu)造樹
using std::queue; //使用STL隊列
queue<TreeNode<T>*> aQueue;
//準(zhǔn)備建立根結(jié)點
TreeNode<T>* pointer=new TreeNode<T>;
root=pointer;
int currentIndex=-1;
while(pointer||!aQueue.empty())
{
if(pointer)
{
currentIndex++;
pointer->setValue(nodeArray[currentIndex].info);
if(nodeArray[currentIndex].llink)
{
TreeNode<T>* leftpointer=new TreeNode<T>;
pointer->setChild(leftpointer);
aQueue.push(leftpointer);
}
else pointer->setChild(NULL);
if(nodeArray[currentIndex].rtag==0)
{
TreeNode<T>* rightpointer=new TreeNode<T>;
pointer->setSibling(rightpointer);
}
else pointer->setSibling(NULL);
pointer=pointer->RightSibling();//訪問pointer的兄弟
}
else
{
pointer=aQueue.front();
aQueue.pop();
}
}
}
template <class T>
Tree<T>::~Tree()
{//析構(gòu)函數(shù)
while(root)
DeleteSubTree(root);
}
template <class T>
TreeNode<T>* Tree<T>::getRoot()
{//返回樹中的根結(jié)點
return root;
}
template <class T>
void Tree<T>::CreateRoot(const T& rootValue)
{//創(chuàng)建樹的根結(jié)點，使根結(jié)點元素的值為rootValue
if(!root)
root=new TreeNode<T>(rootValue);
}
template <class T>
bool Tree<T>::isEmpty()
{//判斷是否為空樹，若是則返回true
if(root)
return false;
return true;
}
template <class T>
void Tree<T>::RootFirstTraverse(TreeNode<T>* root)
{//先根深度優(yōu)先周游樹
while(NULL!=root)
{
AfxMessageBox(root->Value()); //訪問當(dāng)前結(jié)點
RootFirstTraverse(root->LeftMostChild()); //訪問頭一棵樹樹根的子樹
root=root->RightSibling(); //周游其他的樹
}
}
template <class T>
void Tree<T>::RootLastTraverse(TreeNode<T>* root)
{//后根深度優(yōu)先周游樹
while(NULL!=root)
{
RootLastTraverse(root->LeftMostChild()); //訪問頭一棵樹樹根的子樹
AfxMessageBox(root->Value()); //訪問當(dāng)前結(jié)點
root=root->RightSibling(); //周游其他的樹
}
}
template <class T>
void Tree<T>::WidthTraverse(TreeNode<T>* root)
{
using std::queue; //使用STL隊列
queue<TreeNode<T>*> aQueue;
TreeNode<T>* pointer=root;
if(pointer)
{
aQueue.push(pointer);
while(!aQueue.empty())
{
pointer=aQueue.front();
AfxMessageBox(pointer->Value());
while(pointer->RightSibling())
{
if(pointer->LeftMostChild())
aQueue.push(pointer->LeftMostChild());
pointer=pointer->RightSibling();
AfxMessageBox(pointer->Value());
}
if(pointer->LeftMostChild())
aQueue.push(pointer->LeftMostChild());
aQueue.pop();
}
}
}
template <class T>
void Tree<T>::WidthTraverse2(TreeNode<T>* root)
{//寬度優(yōu)先周游樹:版本2
using std::queue; //使用STL隊列
queue<TreeNode<T>*> aQueue;
TreeNode<T>* pointer=root;
if(pointer)
{
while(NULL!=pointer)
{
aQueue.push(pointer);
pointer=pointer->RightSibling();
}
while(!aQueue.empty())
{
pointer=aQueue.front();
aQueue.pop();
AfxMessageBox(pointer->Value());
pointer=pointer->LeftMostChild();
while(pointer)
{
aQueue.push(pointer);
pointer=pointer->RightSibling();
}
}
}
}
template <class T>
TreeNode<T>* Tree<T>::PrevSibling(TreeNode<T>* current)
{//返回current的前一個鄰居結(jié)點
using std::queue; //使用ATL的隊列
queue<TreeNode<T>*> aQueue;
TreeNode<T>* pointer=root;
TreeNode<T>* prev=NULL;
if(pointer)
{
aQueue.push(pointer);
while(!aQueue.empty())
{
pointer=aQueue.front(); //取隊列首結(jié)點
if(pointer==current)
return prev;
while(pointer->RightSibling())
{
prev=pointer;
pointer=pointer->pSibling;
if(pointer==current)
return prev;
else
{
if(prev->LeftMostChild())
aQueue.push(prev->LeftMostChild());
}
}
if(pointer->LeftMostChild())
aQueue.push(pointer->LeftMostChild());
aQueue.pop();
prev=NULL;
}
}
return NULL;
}
template <class T>
TreeNode<T>* Tree<T>::PrevSibling2(TreeNode<T>* current)
{//返回current的前一個鄰居結(jié)點
using std::queue; //使用ATL的隊列
queue<TreeNode<T>*> aQueue;
TreeNode<T>* pointer=root;
TreeNode<T>* prev=NULL;
if((NULL==current)||(NULL==pointer)||(current==pointer))
return NULL;
while(pointer)
{
if(pointer==current)
return prev;
aQueue.push(pointer);
prev=pointer;
pointer=pointer->pSibling;
}
while(!aQueue.empty())
{
prev=NULL;
pointer=aQueue.front(); //取隊列首結(jié)點
aQueue.pop();
pointer=pointer->LeftMostChild();
while(pointer)
{
if(pointer==current)
return prev;
aQueue.push(pointer);
prev=pointer;
pointer=pointer->pSibling;
}
}
return NULL;
}
template <class T>
TreeNode<T>* Tree<T>::getParent(TreeNode<T>* root,TreeNode<T>* current)
{//返回current父節(jié)點,由Parent調(diào)用
TreeNode<T>* temp;
if(root==NULL)
return NULL;
//找到父結(jié)點
if(root->LeftMostChild()==current)
return root;
//遞歸尋找父結(jié)點
if((temp=getParent(root->LeftMostChild(),current))!=NULL)
return temp;
else return getParent(root->RightSibling(),current);
}
template <class T>
TreeNode<T>* Tree<T>::Parent(TreeNode<T>* current)
{//返回current父節(jié)點
TreeNode<T>* pointer=current;
if(NULL!=pointer)
{
TreeNode<T>* leftmostChild=NULL;
while((leftmostChild=PrevSibling(pointer))!=NULL)
pointer=leftmostChild;
leftmostChild=pointer;
pointer=root;
if(leftmostChild==root)
return NULL;
else return getParent(pointer,leftmostChild);
}
}
template <class T>
void Tree<T>::DestroyNodes(TreeNode<T>* root)
{//刪除root為根的子樹的結(jié)點
if(root)
{
DestroyNodes(root->LeftMostChild()); //遞歸刪除root的以左子結(jié)點為根的子樹
DestroyNodes(root->RightSibling()); //遞歸刪除root的以右兄弟結(jié)點為根的子樹
delete root; //刪除根結(jié)點
}
}
template <class T>
void Tree<T>::DeleteSubTree(TreeNode<T>* subroot)
{//釋放以subroot為根的子樹的所有結(jié)點
TreeNode<T>* pointer=PrevSibling(subroot);
if(NULL==pointer)
{
pointer=Parent(subroot);
if(pointer)
{
pointer->pChild=subroot->RightSibling();
subroot->pSibling=NULL;
}
else
{
root=subroot->RightSibling();
subroot->pSibling=NULL;
}
}
else
{
pointer->pSibling=subroot->RightSibling();
subroot->pSibling=NULL;
}
DestroyNodes(subroot);
}
#endif // !defined(AFX_TREE_H__703FFCCE_C340_4198_98E7_00F503CF8261__INCLUDED_)
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -