?? head.h
字號:
#include <iostream>
#include <strstream>
#include <iomanip>
#include <stack>
using namespace std;
//定義二叉樹節(jié)點類型
template<class T>class BinaryTree;
template<class T>struct BTreeNode
{
private:
BTreeNode<T>*left; //左子樹指針
BTreeNode<T>*right; //右子樹指針
public:
T data; //數據域
//構造函數
BTreeNode():left(NULL),right(NULL){}
BTreeNode(T item,BTreeNode<T>*left1=NULL,BTreeNode<T>*right1=NULL):data(item),left(left1),right(right1){}
BTreeNode<T>*&Left(){return left;}
BTreeNode<T>*&Right(){return right;}
friend class BinaryTree<T>;//二叉樹類為二叉樹結點類的友元類
};
//二叉樹類定義
template<class T>class BinaryTree
{
private:
BTreeNode<T>* root;
public:
//構造函數,初始化二叉樹為空
BinaryTree(){root=NULL;}
//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
void CreateBTree(char* a);
//判斷二叉樹是否為空
bool BTreeEmpty() {return root==NULL;}
//按中序遍歷輸出二叉樹中的所有結點
void TraverseBTree();
//用于遍歷的遞歸函數
void Traverse(BTreeNode<T>*&BT);
//用于中序遍歷的非遞歸函數
//void InOrder(BTreeNode<T>*&p);
void InOrder();
};
//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
template<class T>
void BinaryTree<T>::CreateBTree(char *a)
{
BTreeNode<T> *s[80]; //S數組作為存儲二叉樹中根結點指針的棧
int top=-1; //top作為s棧的棧頂指針
root=NULL; //給樹根指針置空
BTreeNode<T> *p=NULL;//定義P為指向二叉樹結點的指針
//用K作為處理結點的左子樹和右子樹的標記,K=1處理左子樹,K=2處理右子樹
int k;
istrstream ins(a);//把字符串a定義為輸入字符串流對象ins
char ch;
ins>>ch;//從ins流對象順序讀入一個字符
while (ch!='@')
{ //每循環(huán)一次處理一個讀入的字符,直到掃描到'@'字符為止
switch(ch)
{
case'(':top++; s[top]=p;k=1;break;
case')':top--;break;
//case',':top++;k=2;break;
case ',':k=2;break;
default:p=new BTreeNode<T>;
//default:p=new BTreeNode<char> (ch);
p->data=ch;
p->left=p->right=NULL;
cout<<setw(2)<<p->data;
if (root==NULL) root=p;
else
{
if(k==1)
s[top]->left=p;
else
s[top]->right=p;
}
}
ins>>ch;
}
}
//按中序遍歷輸出二叉樹中的所有結點
template<class T>
void BinaryTree<T>::TraverseBTree()
{
Traverse(root);
}
//用于中序遍歷的遞歸函數
template<class T>
void BinaryTree<T>::Traverse(BTreeNode<T> *&BT)
{
if (BT!=NULL)
{
//cout<<BT->data<<' ';
Traverse(BT->left);
cout<<BT->data<<" ";
Traverse(BT->right);
}
};
//中序遍歷的非遞歸函數
template<class T>
//void BinaryTree<T>::InOrder(BTreeNode<T> *&p)
void BinaryTree<T>::InOrder()
{
stack<BTreeNode<T>*> s;
BTreeNode<T> *p=root;
do{
while (p!=NULL){
s.push(p);
p=p->left;
}
if(!s.empty()){
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->right;
}
}while(p!=NULL||!s.empty());
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -