?? binarytree1.h
字號:
// BinaryTree1.h: interface for the BinaryTree class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_BINARYTREE1_H__99C2FAA0_E42F_4CB0_8B01_C36F1FA6F1EE__INCLUDED_)
#define AFX_BINARYTREE1_H__99C2FAA0_E42F_4CB0_8B01_C36F1FA6F1EE__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "BinaryTreeNode.h"
#include <stack>
#include <queue>
enum Tags{Left,Right};
template <class T>
class StackElement
{
public:
BinaryTreeNode<T>* pointer;
Tags tag;
};
template <class T>
class BinaryTree
{
protected:
BinaryTreeNode<T>* root; //二叉樹根結點指針
public:
BinaryTree(){root=NULL;}; //構造函數
virtual ~BinaryTree(){DeleteBinaryTree(root);}; //析構函數
bool isEmpty() const{return ((root)?true:false);}; //判定二叉樹是否為空樹
BinaryTreeNode<T>* getRoot(){return root;};
void Initialize(BinaryTreeNode<T>* pointer){root=pointer;};
BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current); //從二叉樹的root結點開始，查找current結點的父結點
BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current); //返回current結點的父結點指針
BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T>* current); //返回current結點的左兄弟
BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>* current); //返回current結點的右兄弟
void CreateTree(const T& elem, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); //以elem作為根結點，leftTree作為樹的左子樹，rightTree作為樹的右子樹，構造一棵新的二叉樹
void DeleteBinaryTree(BinaryTreeNode<T>* root); //刪除二叉樹或其子樹
void PreOrder(BinaryTreeNode<T>* root); //前序遍歷二叉樹或其子樹
void InOrder(BinaryTreeNode<T>* root); //中序遍歷二叉樹或其子樹
void PostOrder(BinaryTreeNode<T>* root); //后序遍歷二叉樹或其子樹
void PreOrderWithoutRecusion(BinaryTreeNode<T>* root); //非遞歸前序遍歷二叉樹或其子樹
void InOrderWithoutRecusion(BinaryTreeNode<T>* root); //非遞歸中序遍歷二叉樹或其子樹
void PostOrderWithoutRecusion(BinaryTreeNode<T>* root); //非遞歸后序遍歷二叉樹或其子樹
void PostOrderWithoutRecusion2(BinaryTreeNode<T>* root);//非遞歸后序遍歷二叉樹或其子樹, 另一個版本
void LevelOrder(BinaryTreeNode<T>* root); //按層次遍歷二叉樹或其子樹
};
//從二叉樹的root結點開始，查找current結點的父結點___________________________________________________________________
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current)
{
BinaryTreeNode<T>* temp;
if(root==NULL)
return NULL;
if((root->leftchild()==current)||(root->rightchild()==current)) //找到父結點
return root;
if((temp=GetParent(root->leftchild(),current))!=NULL) //遞歸尋找父結點
return temp;
else
return GetParent(root->rightchild(),current);
}
//返回current結點的父結點指針_______________________________________________________________________________________
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T>* current)
{
if((current==NULL)||(current==root))
return NULL; //空結點或者current為根結點時，返回NULL
return GetParent(root,current); //調用遞歸函數尋找父結點
}
//返回current結點的左兄弟___________________________________________________________________________________________
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::LeftSibling(BinaryTreeNode<T>* current)
{
if(current){ //current不為空
BinaryTreeNode<T>* temp=Parent(current); //返回current結點的父結點
if((temp==NULL)||current==temp->leftchild())
return NULL; //如果父結點為空，或者current沒有左兄弟
else return temp->leftchild();
}
return NULL;
}
//返回current結點的右兄弟___________________________________________________________________________________________
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::RightSibling(BinaryTreeNode<T>* current)
{
if(current){ //current不為空
BinaryTreeNode<T>* temp=Parent(current); //返回current結點的父結點
if((temp==NULL)||current==temp->rightchild()) //如果父結點為空，或者current沒有右兄弟
return NULL;
else
return temp->rightchild();
}
return NULL;
}
//以elem作為根結點，leftTree作為樹的左子樹，rightTree作為樹的右子樹，構造一棵新的二叉樹_____________________________
template<class T>
void BinaryTree<T>::CreateTree(const T& elem, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree)
{
root=new BinaryTreeNode<T>(elem,leftTree.root,rightTree.root); //創建新樹
leftTree.root=rightTree.root=NULL; //原來兩棵子樹的根結點指空，避免訪問
}
//刪除二叉樹或其子樹________________________________________________________________________________________________
template<class T>
void BinaryTree<T>::DeleteBinaryTree(BinaryTreeNode<T>* root)
{
if(root){
DeleteBinaryTree(root->left);
DeleteBinaryTree(root->right);
delete root;
}
}
//前序遍歷二叉樹或其子樹____________________________________________________________________________________________
template<class T>
void BinaryTree<T>::PreOrder(BinaryTreeNode<T>* root)
{
if(root!=NULL){
AfxMessageBox(root->value()); //訪問當前結點
PreOrder(root->leftchild()); //訪問左子樹
PreOrder(root->rightchild()); //訪問右子樹
}
}
//中序遍歷二叉樹或其子樹____________________________________________________________________________________________
template<class T>
void BinaryTree<T>::InOrder(BinaryTreeNode<T>* root)
{
if(root!=NULL){
InOrder (root->leftchild()); //訪問左子樹
AfxMessageBox(root->value()); //訪問當前結點
InOrder (root->rightchild()); //訪問右子樹
}
}
//后序遍歷二叉樹或其子樹____________________________________________________________________________________________
template<class T>
void BinaryTree<T>::PostOrder(BinaryTreeNode<T>* root)
{
if(root!=NULL){
PostOrder(root->leftchild()); //訪問左子樹
PostOrder (root->rightchild()); //訪問右子樹
AfxMessageBox(root->value()); //訪問當前結點
}
}
//非遞歸前序遍歷二叉樹或其子樹______________________________________________________________________________________
template<class T>
void BinaryTree<T>::PreOrderWithoutRecusion(BinaryTreeNode<T>* root)
{
using std::stack;
stack<BinaryTreeNode<T>* > aStack;
BinaryTreeNode<T>* pointer=root; //保存輸入參數
while(!aStack.empty()||pointer)
{
if(pointer){
AfxMessageBox(pointer->value()); //訪問當前結點
aStack.push(pointer); //當前結點地址入棧
pointer=pointer->leftchild(); //當前鏈接結構指向左孩子
}
else { //左子樹訪問完畢，轉向訪問右子樹
pointer=aStack.top(); //棧頂元素退棧
aStack.pop();
pointer=pointer->rightchild(); //當前鏈接結構指向右孩子
} //else
} //while
}
//非遞歸中序遍歷二叉樹或其子樹______________________________________________________________________________________
template<class T>
void BinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>* root)
{
using std::stack;
stack<BinaryTreeNode<T>* > aStack;
BinaryTreeNode<T>* pointer=root; //保存輸入參數
while(!aStack.empty()||pointer)
{
if(pointer){
aStack.push(pointer); //當前結點地址入棧
pointer=pointer->leftchild(); //當前鏈接結構指向左孩子
}
else { //左子樹訪問完畢，轉向訪問右子樹
pointer=aStack.top();
AfxMessageBox(pointer->value()); //訪問當前結點
pointer=pointer->rightchild(); //當前鏈接結構指向右孩子
aStack.pop(); //棧頂元素退棧
} //else
} //while
}
//非遞歸后序遍歷二叉樹或其子樹______________________________________________________________________________________
template<class T>
void BinaryTree<T>::PostOrderWithoutRecusion(BinaryTreeNode<T>* root)
{
using std::stack;
StackElement<T> element;
stack<StackElement<T > > aStack;
BinaryTreeNode<T>* pointer;
if(NULL==root)
return; //空樹即返回
else
pointer=root;
while(1)
{
while(pointer!=NULL) //進入左子樹
{
element.pointer=pointer;
element.tag=Left;
aStack.push(element);
pointer=pointer->leftchild();
}
element=aStack.top(); //托出棧頂元素
aStack.pop();
pointer=element.pointer;
while(element.tag==Right) //從右子樹回來
{
AfxMessageBox(pointer->value()); //訪問當前結點
if(aStack.empty())
return;
else{
element=aStack.top();
aStack.pop();
pointer=element.pointer;
}
}
element.tag=Right; //從左子樹回來
aStack.push(element);
pointer=pointer->rightchild();
}
}
//非遞歸后序遍歷二叉樹或其子樹, 另一個版本__________________________________________________________________________
template<class T>
void BinaryTree<T>::PostOrderWithoutRecusion2(BinaryTreeNode<T>* root)
{
using std::stack;
stack<BinaryTreeNode<T>* > aStack;
BinaryTreeNode<T> *p, *q;
if(root==NULL)
return;
p=root;
do{
while(p!=NULL){ //沿左路分支下降
aStack.push(p);
p=p->leftchild();
}
q=NULL;
while(!aStack.empty())
{
p=aStack.top();
aStack.pop();
if(p->rightchild()==q){ //右子樹為空或剛剛被訪問過
AfxMessageBox(p->value()); //訪問當前結點
q=p;
}
else{
aStack.push(p);
p=p->rightchild();
break;
}
}
}while(!aStack.empty());
}
//按層次遍歷二叉樹或其子樹__________________________________________________________________________________________
template<class T>
void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>* root)
{
using std::queue;
queue<BinaryTreeNode<T>*> aQueue;
BinaryTreeNode<T>* pointer=root;
if(pointer)
aQueue.push(pointer);
while(!aQueue.empty())
{
pointer=aQueue.front();
AfxMessageBox(pointer->value()); //訪問當前結點
aQueue.pop();
if(pointer->leftchild())
aQueue.push(pointer->leftchild());
if(pointer->rightchild())
aQueue.push(pointer->rightchild());
}
}
#endif // !defined(AFX_BINARYTREE1_H__99C2FAA0_E42F_4CB0_8B01_C36F1FA6F1EE__INCLUDED_)
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -