?? tree.h
字號:
template<typename T>class Tree;
/*定義樹結點類*/
template<typename T>class TreeNode
{
public:
TreeNode(T value);
virtual~TreeNode(){};
T value();
friend class Tree<T>;
private:
T m_Value;
TreeNode<T> * pChild;
TreeNode<T> *pSibling;
};
template<typename T>TreeNode<T>::TreeNode(T value)
{
m_Value = value;
pChild = NULL;
pSibling = NULL;
}
/*定義樹類,用動態左孩子/右孩子表示法來建立樹*/
template<typename T>class Tree
{
public:
Tree(){ root=current=NULL; }
~Tree(){ MakeEmpty(root);}
int Root();
int FirstChild();
int NextSibling();
void InsertChild(T value);
void DeleteSubTree(TreeNode<T> *&t);
void DisplayTree();
void MakeEmpty(TreeNode<T> *&t);
private:
TreeNode<T> *root, *current; //定義根結點根當前指針
TreeNode<T> * GetParent(TreeNode<T> *t,TreeNode<T> *c);
TreeNode<T> * PrevSibling1(TreeNode<T> *t,TreeNode <T> *current);
TreeNode<T> * PrevSibling2(TreeNode<T> *t,TreeNode <T> *current);
int Current(TreeNode<T> *&t);
void RootFistTraverse(TreeNode<T> *t);
void RootLastTraverse(TreeNode<T> *t);
void WidthTraverse(TreeNode<T> *t);
void PrintVTree(TreeNode<T> *t);
};
/*清空已t為跟結點的樹*/
template<typename T>void Tree<T>::MakeEmpty(TreeNode<T> *&t)
{
if(t!=NULL)
{
MakeEmpty(t->pChild);
MakeEmpty(t->pSibling);
delete t;
}
}
/*確定當前結點*/
template<typename T>int Tree<T>::Current(TreeNode<T> *&t)
{
if(t == NULL)
{
current = NULL;
return 0;
}
else
{
current = t;
return 1;
}
}
/*定位根結點*/
template<typename T>int Tree<T>::Root()
{
if(root == NULL)
{
current = NULL;
return 0;
}
return Current(root);
}
/*查找父母結點*/
template<typename T>TreeNode<T>* Tree<T>::GetParent(TreeNode<T> *t,TreeNode<T> *c)
{
if(t == NULL || t->pChild == NULL && t->pSibling == NULL)
return NULL;
if(t->pChild == c || t->pSibling == c)
return root;
TreeNode<T> *p;
p = GetParent(t->pChild, c);
if(p != NULL)
return p;
p = GetParent(t->pSibling, c);
if(p != NULL)
return p;
}
/*定位于最左孩子*/
template<typename T>int Tree<T>::FirstChild()
{
if(current == NULL || current->pChild == NULL)
return 0;
else
{
current = current->pChild;
return Current(current);
}
}
/*定位于右兄弟*/
template<typename T>int Tree<T>::NextSibling()
{
if(current == NULL || current->pSibling == NULL)
return 0;
else
{
current = current->pSibling;
return Current(current);
}
}
template<typename T>void Tree<T>::InsertChild(T value)
{
TreeNode<T> *newNode;
newNode = new TreeNode<T>(value);
if(root == NULL)
root = current = newNode;
else{
if(current->pChild == NULL)
current->pChild = newNode;
else{
TreeNode<T> *p;
p = current->pChild;
while(p->pSibling != NULL)
p = p->pSibling;
p->pSibling = newNode;
}
}
Current(newNode);
}
/*遍歷的時候雖然是遍歷轉換后二叉樹，但是結果仍然是樹的遍歷*/
template<typename T>void Tree<T>::RootFistTraverse(TreeNode<T> *t)
{
stack<TreeNode<T>*> s;
TreeNode<T> *p = t;
s.Push(NULL);
while(p != NULL)
{
cout<<p->m_Value<<'\t';
if(p->pSibling != NULL)
s.Push(p);
if(p->pChild != NULL)
p = p->pChild;
else
{
p = s.Pop();
if(p != NULL)
p = p->pSibling;
}
}
}
/*遍歷的時候雖然是遍歷轉換后二叉樹，但是結果仍然是樹的遍歷，
不要看成是二叉樹的中序遍歷*/
template<typename T>void Tree<T>::RootLastTraverse(TreeNode<T> *t)
{
stack<TreeNode<T>*> s;
TreeNode<T> *p = t;
while(p!=NULL || !s.IsEmpty())
{
while(p!=NULL)
{
s.Push(p);
p=p->pChild;
}
p = s.Pop();
cout<<p->m_Value<<'\t';
p = p->pSibling;
}
}
/*層次遍歷樹*/
template<typename T>void Tree<T>::WidthTraverse(TreeNode<T> *t)
{
queue<TreeNode<T> *> Q;
TreeNode<T> *p = root;
if(p != NULL)
{
Q.EnQue(p);
while(!Q.IsEmpty())
{
p=Q.DeQue();
cout<<p->m_Value<<'\t';
while(p->pSibling != NULL)
{
if(p->pChild!=NULL)
Q.EnQue(p->pChild);
p = p->pSibling;
cout<<p->m_Value<<'\t';
}
if(p->pChild != NULL)
Q.EnQue(p->pChild);
}
}
}
/*查找當前結點前一個鄰居結點的第一種方法*/
template<typename T>TreeNode<T> * Tree<T>::PrevSibling1(TreeNode<T> *t,TreeNode<T> *current)
{
queue<TreeNode<T> *> Q;
TreeNode<T> *p = root,*prev = NULL;
if((t == NULL) || (current == p) || (current == NULL)) //當前結點是根結點或者是最左孩子時，沒有鄰居結點
return NULL;
if(p != NULL)
{
Q.EnQue(p);
while(!Q.IsEmpty())
{
prev=NULL;
p=Q.DeQue();
while(p->pSibling != NULL)
{
if(p->pChild!=NULL)
Q.EnQue(p->pChild);
prev = p;
p = p->pSibling;
if(p == current)
return prev;
}
if(p->pChild != NULL)
Q.EnQue(p->pChild);
}
}
}
/*查找當前結點前一個鄰居結點的第二種方法*/
template<typename T>TreeNode<T>* Tree<T>::PrevSibling2(TreeNode<T> *t,TreeNode <T> *current)
{
TreeNode<T> *p = root, *Prev = NULL ;
queue<TreeNode<T> *> Q;
if((t == NULL) || (current == p) || (current == NULL))
return NULL;
while(p != NULL)
{
if(p == current)
return Prev;
Q.EnQue(p);
Prev = p;
p = p->pSibling;
}
while(!Q.IsEmpty())
{
Prev = NULL;
p = Q.DeQue();
p = p->pChild;
while(p != NULL)
{
if(p == current)
return Prev;
Q.EnQue(p);
Prev = p;
p = p->pSibling;
}//end while
}//end while
}
/*刪除以current為根結點的子樹*/
template<typename T>void Tree<T>::DeleteSubTree(TreeNode<T> *&t)
{
TreeNode<T> *p = PrevSibling1(root,t);
if(p == NULL)
{
p = GetParent(root,t);
if(p!=NULL)
{
p->pChild = t->pSibling;
t->pSibling = NULL;
}
else
{
root= t->pChild;
t->pChild = NULL;
}
}
else{
p->pSibling = t->pSibling;
t->pSibling = NULL;
}
MakeEmpty(t);
}
/*用圖形顯示樹*/
template<typename T>void Tree<T>::PrintVTree(TreeNode<T> *t){
int screenWidth=64;
int dataWidth=2;
queue<TreeNode<T> *> Q;
queue<Level> QI;
TreeNode<T> *p;
Level s,s1,s2;
double offset,level=-1,i;
Q.EnQue(t);
s.xIndent=screenWidth/dataWidth;
s.yLevel=0;
QI.EnQue(s);
while(!Q.IsEmpty()&&!QI.IsEmpty())
{
s2=s;
p=Q.DeQue();
s=QI.DeQue();
if(s.yLevel!=level)
{
cout<<"\n\n第"<<s.yLevel<<"層";
level=s.yLevel;
for(i=0;i<s.xIndent-1;i++) cout<<" ";
}
else
for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" ";
cout<<p->m_Value;
if(p->pChild!=NULL)
{
Q.EnQue(p->pChild);
s1.yLevel=s.yLevel+1;
offset=screenWidth/pow(dataWidth,s1.yLevel+1);
s1.xIndent=s.xIndent-offset;
QI.EnQue(s1);
}
if(p->pSibling!=NULL)
{
Q.EnQue(p->pSibling);
s1.yLevel=s.yLevel+1;
offset=screenWidth/pow(dataWidth,s1.yLevel+1);
s1.xIndent=s.xIndent+offset;
QI.EnQue(s1);
}
}
}
template<typename T>void Tree<T>::DisplayTree()
{
cout<<"打印樹:"<<endl;
PrintVTree(root);
cout<<endl<<endl;
cout<<"按先根遍歷樹顯示的結點次序為:"<<endl<<endl;
RootFistTraverse(root);
cout<<endl<<endl;
cout<<"按后根遍歷樹顯示的結點次序為:"<<endl<<endl;
RootLastTraverse(root);
cout<<endl;
cout<<"按層次遍歷樹顯示的結點次序為:"<<endl<<endl;
WidthTraverse(root);
cout<<endl;
Root();
FirstChild();
NextSibling();
NextSibling();
cout<<"顯示當前結點的前一個鄰居結點:"<<endl<<endl;
cout<<"當前結點是:"<<current->m_Value<<endl<<endl;
TreeNode<T> *p;
p = PrevSibling1(root,current);
cout<<"前一個鄰居結點是:"<<endl;
cout<<p->m_Value<<endl;
cout<<"刪除當前結點為根結點的子樹:"<<endl<<endl;
Root();
FirstChild();
NextSibling();
cout<<"要刪除以這個結點為根的子樹的結點是:"<<endl;
cout<<current->m_Value<<endl;
DeleteSubTree(current);
PrintVTree(root);
cout<<endl<<endl;
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -