之前打算編算法類的程序，但是搞了幾次英雄會後，覺得作為一個還在學習階段的學生，實在是太浪費時間了，並不是沒意義，而是我的基礎還不牢固啊。所以轉變了思路，這個學期打算分別用C++、Python、Java實現數據結構。下個學期再做算法的打算吧。不過Java沒學過，可能要一點時間了。
小弟喜歡編程，但是學習高級應用覺得時間長了就都忘了，至今在探索大學階段該怎麼規劃，希望大神指教。
用C++實現的二叉樹，有遞歸和非遞歸兩種操作方式，其中非遞歸只實現了中序遍歷，和求樹的高度。用了<queue>和<stack>庫，以前沒有用過STL，現在感覺方便多了。
/********************
Date :2013-9-10
Author :DVD0423
Function:二叉樹
樣例輸入:1-2-4-q-q-5-q-q-3-6-q-q-7-q-q
"q"代表葉子節點的孩子，為先序遍歷輸入
結果為 :
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
q q...
*******************/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef char DataType;
#define END 'q'
struct Node{
DataType val;
Node *leftChild;
Node *rightChild;
Node():leftChild(NULL),rightChild(NULL){}
void Visit()
{
cout<<"\t"<<val<<endl;
}
};
class BiTree{
public:
//member function
BiTree();
void CreateTree(Node * & ); //創建二叉樹
void PreOrder(Node * &); //先序遍歷
void InOrder(Node * &); //中序遍歷
void PostOrder(Node * &); //後序遍歷
int getHeight(Node * &); //求樹的高度，
int getLevel(Node * &); //層序遍歷，並求高度，非遞歸借助queue
void NoRecTraverse(Node * &); //中序非遞歸遍歷,借助stack
void Destroy(Node * &); //銷毀
~BiTree();
//private:
//data member
Node *root; //根節點
int num;
};
BiTree::BiTree()
{
num=0;
CreateTree(root);
cout<<"節點數一共為："<<num<<endl;
}
void BiTree::CreateTree(Node * &root)
{
DataType e;
cin>>e;
if(e == END)
{
root = NULL;
}
else
{
if((root = new Node) == NULL) //new 開辟內存空間
exit(1);
root->val = e;
num++;
CreateTree(root->leftChild);
CreateTree(root->rightChild);
}
}
void BiTree::PreOrder(Node * &root)
{
if(root)
{
root->Visit();
PreOrder(root->leftChild);
PreOrder(root->rightChild);
}
}
void BiTree::InOrder(Node * &root)
{
if(root != NULL)
{
InOrder(root->leftChild);
root->Visit();
InOrder(root->rightChild);
}
}
void BiTree::PostOrder(Node * &root)
{
if(root != NULL)
{
PostOrder(root->leftChild);
PostOrder(root->rightChild);
root->Visit();
}
}
/*
求樹高度
*/
//recursion
int BiTree::getHeight(Node * &root)
{
if(root == NULL)
return 0;
else if(getHeight(root->leftChild)>getHeight(root->rightChild))
return getHeight(root->leftChild)+1;
else
return getHeight(root->rightChild)+1;
}
/*
非遞歸
front為pop的節點，rear為push的節點，last為每層的最右邊節點
*/
int BiTree::getLevel(Node * &root)
{
int level = 0;
int front = 0, rear = 0, last = 0;
queue<Node *> q;
Node * p = root;
Node * t = NULL;
if(p)
{
q.push(p);
++rear;
++last;
}
while(!q.empty())
{
t = q.front();
q.pop();
++front;
t->Visit(); //層序遍歷
if(t->leftChild)
{
q.push(t->leftChild);
++rear;
}
if(t->rightChild)
{
q.push(t->rightChild);
++rear;
}
if(front == last) //訪問到每層的最後節點，此時rear也指向下一層的最後節點
{
++level;
last = rear;
}
}
return level;
}
/*
中序
*/
void BiTree::NoRecTraverse(Node * &root)
{
Node *p=root;
stack<Node *> s;
while(p || !s.empty())
{
if(p)
{
s.push(p);
p = p->leftChild;
}
else
{
p = s.top();
p->Visit();
s.pop();
p = p->rightChild;
}
}
}
void BiTree::Destroy(Node * &root)
{
if(root)
{
Destroy(root->leftChild);
Destroy(root->rightChild);
delete root;
root = NULL; //這一步為規范操作，防止root成為野指針
}
}
BiTree::~BiTree()
{
Destroy(root);
}
