二叉树基本功能的汇集(C++类实现)(一)

二叉树是程序应用得比较多的一种结构。它可以反映物体之间的层次结构，还能通过孩子和双亲反映两物体之间某些特殊关系；排序二叉树还能帮助我们进行排序，并因此而提供快速的查找；二叉树基础上的伸展树能不断地优化我们系统的结构。并查集能很好地让我们进行分类；小根堆能帮助我们快速找到值最小的结点，它是优先队列的雏形。所有的这些都是以二叉树为基础的。

我实现的二叉树的基本功能包括前中后序的递归和非递归访问，求结点个数和叶子结点个数，还有求树高。这些是用C++类实现的。

BTree.h文件(类声明文件)

#ifndef BTREE_H
#define BTREE_H

struct BTreeNode
{
int data;
BTreeNode *lChild,*rChild;
};

class BTree
{public:
void setRoot(BTreeNode* r){ root=r;}
BTreeNode* getRoot(){ return root;}

//中序遍历(递归)
void inOrder();
//中序遍历(非递归)
void NotReInOrder();
BTreeNode* createBTree();

//前序遍历(递归)
void preOrder();
//前序遍历(非递归)
void NotRePreOrder();

//后序遍历(递归)
void postOrder();

//后序遍历(非递归)
void NotRePostOrder();

//求结点个数
int BTreeSize();
//求叶子结点个数
int BTreeLeaves();

//求树高
int BTreeHeight();
//层次法求树高
int layerHeight();

protected:
//中序遍历
void inOrder(BTreeNode*);
//前序遍历
void preOrder(BTreeNode*);
//后序遍历
void postOrder(BTreeNode*);

//结点个数
int BTreeSize(BTreeNode*);
//叶子结点
int BTreeLeaves(BTreeNode*);

//树高
int BTreeHeight(BTreeNode*);
private:
BTreeNode* root;
};

#endif

BTree.cpp(类的实现文件)

#include
#include
#include
#include "BTree.h"
using namespace std;

//建立二叉树的算法
BTreeNode* BTree::createBTree()
{
BTreeNode* current=0;
int val=0;

cin>>val;

//-1的个数比数值的个数多1
if(val==-1)
return NULL;
else
{
current=new BTreeNode;
current->data=val;
current->lChild=createBTree();
current->rChild=createBTree();
return current;
}

}

//利用重载的方法
void BTree::inOrder()
{
inOrder(root);
cout<}

//中序访问二叉树(递归)
void BTree::inOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
inOrder(r->lChild); //递归访问
cout<data<<" ";
inOrder(r->rChild); //递归访问
}
}

//中序遍历(非递归)
void BTree::NotReInOrder()
{
stack s;

BTreeNode* r=getRoot();

while(!s.empty()||r!=0)
{
while(r!=0)
{
s.push(r);
r=r->lChild;
}

if(!s.empty())
{
r=s.top();
s.pop();
cout<data<<" ";
r=r->rChild;
}
}
}

//重载形式
void BTree::preOrder()
{
preOrder(root);
cout<}

//前序递归访问二叉树(递归)
void BTree::preOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
cout<data<<" ";
preOrder(r->lChild); //递归访问
preOrder(r->rChild); //递归访问
}
}


//前序遍历(非递归)
void BTree::NotRePreOrder()
{
stack s;
BTreeNode* r=getRoot();
s.push(r);

while(!s.empty())
{
r=s.top();
s.pop();

cout<data<<" ";

if(r->rChild!=0)
s.push(r->rChild);
if(r->lChild!=0)
s.push(r->lChild);
}
}


//重载形式
void BTree::postOrder()
{
postOrder(root);
cout<}

//后序遍历(递归)
void BTree::postOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
postOrder(r->lChild); //递归访问
postOrder(r->rChild); //递归访问
cout<data<<" ";
}
}


//后序非递归访问要定义新的结构体类型
struct Node
{
BTreeNode* tp;
bool flag;
};

//后序遍历(非递归)
void BTree::NotRePostOrder()
{
Node node; //定义Node结构体的一个结点
stack s;

BTreeNode* r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
node.tp=r;
node.flag=0;
s.push(node);
r=r->lChild;
}

if(!s.empty())
{
node=s.top();
s.pop();