C++数据结构之二叉树

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<<"\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);
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针