s.push(p); p=p->l; } if(!s.empty()) { p=s.top(); cout<<p->data<<" "; s.pop(); p=p->r; } } } void BL3(ECS_data *t)//递归后序遍历 { if(NULL!=t) { BL3(t->l); BL3(t->r); cout<<t->data<<","; } } void postOrder3(ECS_data *t) //非递归后序遍历 { stack<ECS_data*> s; ECS_data *cur; //当前结点 ECS_data *pre=NULL; //前一次访问的结点
(pre!=NULL&&(pre==cur->l||pre==cur->r))) {
cout<<cur->data<<" "; //如果当前结点没有孩子结点或者孩 子节点都已被访问过
s.pop(); pre=cur; } else { if(cur->r!=NULL)
s.push(cur->r); if(cur->l!=NULL)
CountLeaf(t->l);//递归统计左子树叶子数目 CountLeaf(t->r);//递归统计右子树叶子数目 } } return LeafNum; }
五、运行结果
附：完整程序源代码：
//二叉树链式存储的实现
#include<iostream> #include<cstring> #include <stack> using namespace std;
}
if((p!=NULL)&&(1==front%2))
{
temp[rear]->r=p;
}
if(1==front%2)rear++;
//就当前的数据找这个数据
的父母
}
}
}
}
~ECS()
//释放内存
{
ii++)
if(temp[i]!=NULL)
delete temp[i];
s.pop(); pre=cur; } else { if(cur->r!=NULL)
s.push(cur->r); if(cur->l!=NULL)
s.push(cur->l); } } } int Height (ECS_data *t) //求树高 { if(t==NULL) return 0; else { int m = Height ( t->l ); int n = Height(t->r); return (m > n) ? (m+1) : (n+1); } } int CountLeaf(ECS_data *t) //求叶子总数 { static int LeafNum=0;//叶子初始数目为 0，使用静态变量 if(t)//树非空 { if(t->l==NULL&&t->r==NULL)//为叶子结点
struct ECS_data //先定义好一个数据的结构 {
char data; ECS_data *l; ECS_data *r; };
class ECS { private:
//int level; int n; int n1; 进行删除判断
//树高 //表示有多少个节点数
//表示的是数组的总长度值，（包括#）,因为后面要
cin.getline(t,1000);
//先把输入的数据输入到一个 t 数组
//cout<<t<<" "<<endl;
int n1=strlen(t);
//测量数据的长度
n=0;
for(i=0;i<n1;i++)
{
if(t[i]!='#')
{
p=NULL;
if(t[i]!=',')
//满足条件并开辟内存
LeafNum++;//叶子数目加 1 else//不为叶子结点 {
CountLeaf(t->l);//递归统计左子树叶子数目 CountLeaf(t->r);//递归统计右子树叶子数目 } }
return LeafNum; } };
int main() {
ECS a; a.JS(); cout<<"递归前序遍历:"; a.BL1(a.root); cout<<endl; cout<<"非递归前序遍历:"; a.preOrder2(a.root); cout<<endl; cout<<"递归中序遍历:"; a.BL2(a.root); cout<<endl; cout<<"非递归中序遍历:"; a.inOrder2(a.root); cout<<endl; cout<<"递归后序遍历:"; a.BL3(a.root); cout<<endl; cout<<"非递归后序遍历:"; a.postOrder3(a.root); cout<<endl; cout<<"树高为:"<<a.Height(a.root)<<endl; cout<<"叶子总数为:"<<a.CountLeaf(a.root)<<endl; return 0; }
ECS_data *temp[1000];
public:
ECS_data *root;
ECS() //初始化
{
ECS_data *p;
char t[1000];int i;
int front=0,rear=1;
//front 表示有多少个节点，rear 表示当前插
入的点的父母
cout<<"请按正确顺序输入二叉树的数据:";
4、非递归前序遍历
void preOrder2(ECS_data *t) {
stack<ECS_data*> s; ECS_data *p=t; while(p!=NULL||!s.empty()) {
while(p!=NULL) {
cout<<p->data<<" "; s.push(p); p=p->l; } if(!s.empty()) { p=s.top(); s.pop(); p=p->r; } } }
while(p!=NULL) {
s.push(p); p=p->l; } if(!s.empty()) { p=s.top(); cout<<p->data<<" "; s.pop(); p=p->r; } } }
7、递归后序遍历
void BL3(ECS_data *t) { if(NULL!=t) { BL3(t->l); BL3(t->r); cout<<t->data<<","; } }
s.push(cur->l); } } }
9、求树高
int Height (ECS_data *t) {
if(t==NULL) return 0; else {
int m = Height ( t->l ); int n = Height(t->r); return (m > n) ? (m+1) : (n+1); } }
cout<<p->data<<" "; s.push(p); p=p->l; } if(!s.empty()) { p=s.top(); s.pop(); p=p->r; } }
} void BL2(ECS_data *t)//递归中序遍历 {
if(NULL!=t) {
BL2(t->l); cout<<t->data<<","; BL2(t->r); } } void inOrder2(ECS_data *t) //非递归中序遍历 { stack<ECS_data*> s; ECS_data *p=t; while(p!=NULL||!s.empty()) { while(p!=NULL) {
s.push(t); while(!s.empty()) {
cur=s.top(); if((cur->l==NULL&&cur->r==NULL)||
(pre!=NULL&&(pre==cur->l||pre==cur->r))) {
cout<<cur->data<<" "; //如果当前结点没有孩子结点或者孩子节 点都已被访问过
10、 求叶子总数
int CountLeaf(ECS_data *t) { static int LeafNum=0;//叶子初始数目为 0，使用静态变量 if(t)//树非空 { if(t->l==NULL&&t->r==NULL)//为叶子结点 LeafNum++;//叶子数目加 1 else//不为叶子结点 {