C++数据结构之二叉树

之前打算编算法类的程序，但是搞了几次英雄会后，觉得作为一个还在学习阶段的学生，实在是太浪费时间了，并不是没意义，而是我的基础还不牢固啊。所以转变了思路，这个学期打算分别用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<<" "<<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）;
}相关阅读：二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm