返回信息流#include <cstdlib>
#include <iostream>
using namespace std;
template <class Type>
class LinkedQueue
{
private:
struct node
{
Type data;
struct node *link;
};
struct node *top,*rear;
public:
LinkedQueue()
{
rear=top=NULL;
}
~LinkedQueue()
{
node *temp;
while(top)
{
temp=top;
top=top->link;
delete temp;
}
}
bool Add(Type item);
bool Del(Type &item);
bool QueueEmpty();
};
template <class Type>
bool LinkedQueue<Type>::QueueEmpty()
{
if(top==NULL)
return true;
else
return false;
}
template <class Type>
bool LinkedQueue<Type>::Add(Type item)
{
node *t=new node;
if(t==NULL)
{
cout<<"out of space!"<<endl;
return false;
}
else
{
t->data=item;
t->link=NULL;
if(rear==NULL)
{
top=t;
rear=t;
}
else
{
rear->link=t;
rear=t;
}
return true;
}
}
template <class Type>
bool LinkedQueue<Type>::Del(Type &item)
{
if(QueueEmpty())
{
cout<<"Queue is empty!"<<endl;
return false;
}
else
{
node *t;
t=top;
item=t->data;
if(top==rear)
{
top=NULL;
rear=NULL;
}
else
{
top=top->link;
}
delete t;
return true;
}
}
template <class Type>
class BinTree
{
private:
class BinNode
{
public:
Type data;
BinNode *lchild,*rchild;
};
BinNode *root;
int sumLeaf;
void destroy();
int getDepth(BinNode *r);
int getSumNode(BinNode *r);
void PrePrintTree(BinNode *r);
void PostPrintTree(BinNode *r);
void InPrintTree(BinNode *r);
void getLeafSum(BinNode *r);
public:
BinTree(){root=NULL;sumLeaf=0;}
~BinTree()
{
destroy();
}
void makeTree(Type *t,int len,Type split);
void PrintTree(Type split);
int getDepth();
int getSumNode();
void PrePrintTree();
void PostPrintTree();
void InPrintTree();
int getLeafSum();
};
template <typename Type>
void BinTree<Type>::destroy()
{
if(root==NULL)
return;
LinkedQueue<BinNode*> *lq=new LinkedQueue<BinNode*>();
lq->Add(root);
BinNode *tp;
while(lq->QueueEmpty())
{
lq->Del(tp);
if(tp->lchild!=NULL)
lq->Add(tp->lchild);
if(tp->rchild!=NULL)
lq->Add(tp->rchild);
delete tp;
}
}
template <typename Type>
void BinTree<Type>::makeTree(Type *t,int len,Type split)
{
if(len<=0)
return;
if(t[0]==split)
return;
root=new BinNode();
root->data=t[0];
root->lchild=NULL;
root->rchild=NULL;
LinkedQueue<BinNode*> *lq=new LinkedQueue<BinNode*>();
lq->Add(root);
int i=1;
BinNode *tp;
while(true)
{
if(i>=len)
return;
lq->Del(tp);
if(tp==NULL)
{
if(t[i]!=split||t[i+1]!=split)
{
return;
}
lq->Add(NULL);
lq->Add(NULL);
}
else
{
if(t[i]!=split)
{
BinNode *b=new BinNode();
b->data=t[i];
b->lchild=NULL;
b->rchild=NULL;
tp->lchild=b;
lq->Add(b);
}
else
{
lq->Add(NULL);
}
if(t[i+1]!=split)
{
BinNode *b=new BinNode();
b->data=t[i+1];
b->lchild=NULL;
b->rchild=NULL;
tp->rchild=b;
lq->Add(b);
}
else
{
lq->Add(NULL);
}
}
i+=2;
}
delete lq;
}
template <class Type>
void BinTree<Type>::PrintTree(Type split)
{
LinkedQueue<BinNode*> *lq=new LinkedQueue<BinNode*>();
lq->Add(root);
BinNode *tp;
cout<<"Tree is :";
while(true)
{
if(lq->QueueEmpty())
return;
lq->Del(tp);
if(tp==NULL)
cout<<split<<" ";
else
{
cout<<tp->data<<" ";
lq->Add(tp->lchild);
lq->Add(tp->rchild);
}
}
cout<<endl;
cout<<endl;
delete lq;
}
template <class Type>
int BinTree<Type>::getDepth()
{
cout<<"The depth of tree is :";
return getDepth(root);
}
template <class Type>
int BinTree<Type>::getDepth(BinNode *r)
{
if(r==NULL)
return 0;
int lDepth=getDepth(r->lchild);
int rDepth=getDepth(r->rchild);
return 1+((lDepth>rDepth)?lDepth:rDepth);
}
template <class Type>
int BinTree<Type>::getSumNode()
{
cout<<"The sum of tree's nodes is :";
return getSumNode(root);
}
template <class Type>
int BinTree<Type>::getSumNode(BinNode *r)
{
if(r==NULL)
return 0;
int lSum=getSumNode(r->lchild);
int rSum=getSumNode(r->rchild);
return 1+lSum+rSum;
}
template <class Type>
int BinTree<Type>::getLeafSum()
{
cout<<"The leaf sum of tree's nodes is :";
getLeafSum(root);
return sumLeaf;
}
template <class Type>
void BinTree<Type>::getLeafSum(BinNode *r)
{
if(r->lchild==NULL&&r->rchild==NULL)
sumLeaf++;
else
{
if(r->lchild!=NULL)
getLeafSum(r->lchild);
if(r->rchild!=NULL)
getLeafSum(r->rchild);
}
}
template <class Type>
void BinTree<Type>::PrePrintTree()
{
cout<<"PrePrintTree() is :";
PrePrintTree(root);
cout<<endl;
}
template <class Type>
void BinTree<Type>::PrePrintTree(BinNode *r)
{
if(r==NULL)
return;
else
{
cout<<r->data<<" ";
PrePrintTree(r->lchild);
PrePrintTree(r->rchild);
}
}
template <class Type>
void BinTree<Type>::PostPrintTree()
{
cout<<"PostPrintTree() is :";
PostPrintTree(root);
cout<<endl;
}
template <class Type>
void BinTree<Type>::PostPrintTree(BinNode *r)
{
if(r==NULL)
return;
else
{
PostPrintTree(r->lchild);
PostPrintTree(r->rchild);
cout<<r->data<<" ";
}
}
template <class Type>
void BinTree<Type>::InPrintTree()
{
cout<<"InPrintTree() is :";
InPrintTree(root);
cout<<endl;
}
template <class Type>
void BinTree<Type>::InPrintTree(BinNode *r)
{
if(r==NULL)
return;
else
{
InPrintTree(r->lchild);
cout<<r->data<<" ";
InPrintTree(r->rchild);
}
}
int main(int argc, char *argv[])
{
BinTree<int> *tree=new BinTree<int>();
int d[]={1,2,3,4,-1,-1,-1,5,6};
tree->makeTree(d,9,-1);
tree->PrintTree(-1);
cout<<endl<<tree->getDepth()<<endl;
tree->PrePrintTree();
tree->PostPrintTree();
tree->InPrintTree();
cout<<tree->getSumNode()<<endl;
cout<<tree->getLeafSum()<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #84631同步于 2014/12/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
来个二叉树的实现源码
FromSixToTen
2014/12/5镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
使用代码高亮功能啊
【 在 FromSixToTen 的大作中提到: 】
: #include <cstdlib>
: #include <iostream>
: using namespace std;
: ...................
最好来一个这个系统 http://codepad.org/ 直接编译看看。
【 在 jkfbrant 的大作中提到: 】
: 看来论坛技术版得接入codereview系统了。。。。