二叉树类的实现
学习数据结构,我的体会到它有三个基础内容:链表,二叉树,排序查找算法前些天写了一个链表类,开始数据结构学习之路，到现在终于写了二叉树类。个人感觉学习数据结构常常会觉得理解了，却无法用语言来实现，幸好借了本好书，它基本上帮我做了。通过整理，我把它们合成一个类，希望对有些人有帮助。
这是一个精简的二叉树类
//二叉树的实现(精简版)
#include<iostream>
using namespace std;
typedef char ElemType;//为了简单,定义为char
//定义结构体
typedef struct node
{
ElemType data;
struct node*lchild;
struct node*rchild;
}BTNode;
//类定义
class BinaryTree
{
private:
BTNode*root; //根
void preOrder(BTNode*b);
void clearTree(BTNode*b);
public:
BinaryTree(char str[]);//输入如"A(B(D(,G)),C(E,F))"构造
~BinaryTree();
void display();
};
BinaryTree::BinaryTree(char* str)
{
const int MaxSize=100;
root=NULL; //初始化为NULL
BTNode *St,*p=NULL;//St指针数组作栈用
int top=-1; //栈顶
int i=0; //str的下标
int j; //j=1表示左子树,j=2表示右子树
char ch=str;
while (ch!='\0')
{
switch (ch)
{
case '(':top++;St=p;j=1;break;//遇'('入栈
case ',':j=2;break; //遇','j=2右子树
case ')':top--;break; //遇')'出栈
default:
p=new BTNode;
p->data=ch;
p->lchild=p->rchild=NULL;
if(root==NULL)root=p;//只调用一次,使root指向树根
else
{
switch(j)
{
case 1:St->lchild=p;break;
case 2:St->rchild=p;break;
}
}
}
i++;
ch=str;
}
}
BinaryTree::~BinaryTree()
{
if(root!=NULL)clearTree(root);
}
//删除树,由析构函数调用
void BinaryTree::clearTree(BTNode*b)
{
if (b!=NULL)
{
clearTree(b->lchild);
clearTree(b->rchild);
delete b;
}
}
//先序遍历
void BinaryTree::preOrder(BTNode*b)
{
if (b!=NULL)
{
cout<<b->data;
preOrder(b->lchild);
preOrder(b->rchild);
}
}
//打印树
void BinaryTree::display()
{
preOrder(root);
}
//测试一下
int main()
{
BinaryTree bt("A(B(D(,G)),C(E,F))");
bt.display();
}
这个也很简，只是用到的方法不同。
//二叉树的实现
#include<iostream>
using namespace std;
typedef char ElemType;//为了简单,定义为char
//定义结构体
typedef struct node
{
ElemType data;
struct node*lchild;
struct node*rchild;
}BTNode;
//类定义
class BinaryTree
{
private:
BTNode*root; //根
void printTree(BTNode*b); //递归输出
int treeDepth(BTNode*b);
BTNode*PreInCreate(char* pre,char*in,int n);//由先序和中序序列构造树的递归
void clearTree(BTNode*b);
public:
BinaryTree(char *pre,char*in,int n);//由先序和中序序列构造
BinaryTree(BTNode*b);
~BinaryTree();
BTNode* getRoot(); //取得根元素
void display(); //以A(B(D(,G)),C(E,F))格式输出
};
BinaryTree::BinaryTree(BTNode*b)
{
root=b;
}
//pre为先序字符串,in为中序字符串,n是串长
BinaryTree::BinaryTree(char* pre,char*in,int n)
{
root=PreInCreate(pre,in,n);
}
BTNode* BinaryTree::PreInCreate(char* pre,char*in,int n)
{
BTNode*b;
char*p;
int k;
if(n<=0)return NULL;
b=new BTNode;
b->data=*pre;
for(p=in;p<in+n;p++)
if(*p==*pre)break;
k=p-in;
b->lchild=PreInCreate(pre+1,in,k);
b->rchild=PreInCreate(pre+k+1,p+1,n-k-1);
return b;
}
//析构函数
BinaryTree::~BinaryTree()
{
if(root!=NULL)clearTree(root);
}
//删除树,由析构函数调用
void BinaryTree::clearTree(BTNode*b)
{
if (b!=NULL)
{
clearTree(b->lchild);
clearTree(b->rchild);
delete b;
}
}
inline BTNode* BinaryTree::getRoot()
{
return root;
}
//求树的深度的递归
int BinaryTree::treeDepth(BTNode*b)
{
int l,r;
if(b==NULL)return 0;
else
{
l=treeDepth(b->lchild);
r=treeDepth(b->rchild);
return (l>r)?(l+1):(r+1);
}
}
//打印树的递归
void BinaryTree::printTree(BTNode*b)
{
if (b!=NULL)
{
cout<<b->data;
if (b->lchild!=NULL||b->rchild!=NULL)
{
cout<<"(";
printTree(b->lchild);
if(b->rchild!=NULL)cout<<",";
printTree(b->rchild);
cout<<")";
}
}
}
//打印树
void BinaryTree::display()
{
printTree(root);
}
//测试下
int main()
{
char a[]="ABDGCEF";
char b[]="DGBAECF";
BinaryTree bt(a,b,7);
bt.display();
}
感觉数据结构的学习很多东西是用来理解的，而很难去创新。比如树的构造，书上说到的方法就去看，去理解，很难自己想到新方法来实现。这个帖子就当自己笔记本吧。
你学习数据结构的理解和体会也分享一下，交流交流！ 用栈写的那个不错. 支持一下～
页:
[1]