之前打算编算法类的程序，但是搞了几次英雄会后，觉得作为一个还在学习阶段的学生，实在是太浪费时间了，并不是没意义，而是我的基础还不牢固啊。所以转变了思路，这个学期打算分别用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);
}