给出层次遍历的结果求建立二叉树的过程

答案:1 悬赏:0 手机版

解决时间 2021-11-19 09:41

提问者网友：像風在裏
2021-11-18 21:13

给出层次遍历的结果求建立二叉树的过程

最佳答案

五星知识达人网友：杯酒困英雄
2021-11-18 21:35

#include

struct bnode
{
char data;
struct bnode *lchild;
struct bnode *rchild;
int ltag,rtag;//左右线索标志
};

class btree
{
public:
btree();
~btree();
void create(bnode *&p);//先序创建二叉树
void create(char s[],bnode *&p,int i);//从数组建立二叉树
const btree&operator = (const btree&);//重载=
bool isEmpty();//判断非空
void preorderTraversal();//前序遍历
void postorderTraversal();//后序
void inorderTraversal();//中序
void inTravAndShow(bnode *p);//中序遍历并输出，显示层数
int treeHeight();//树的高度
int theNodeCount();//结点数目
int treeLeavesCount();//叶子结点数目
void destroyTree();//删除树
void changeLR(bnode *&p);//交换每个节点间的左右孩子结点
//protected:
bnode *root;
private:

void destroy(bnode *p);//?
void inorder(bnode *p);
void preorder(bnode *p);
void postorder(bnode *p);
int height(bnode *p);
int max (int x,int y);
int nodeCount(bnode *p);
int leavesCount(bnode *p);
};

int layer=0;//层数
bnode *pre=NULL;//全局指针
int maxlength=26;//数组最大长度
char s[]={'a','b','c','d',' ',' ',' ',' ',' '};

void btree::create(bnode *&p)
{

char x;
cin>>x;
if(x=='.') p=NULL;
else
{
p=new bnode;
p->data=x;
create(p->lchild);
create(p->rchild);
}
}

void btree::create(char s[],bnode *&p,int i)//调用时i=1
{
if(s[i-1]==' '||i>maxlength+1) p=NULL;
else
{
p=new bnode;
p->data=s[i-1];
create(s,p->lchild,2*i);
create(s,p->rchild,2*i+1);
}
}

bool btree::isEmpty()
{
return (root==NULL);
}
void btree::preorderTraversal()
{
preorder(root);
}

void btree::inorderTraversal()
{
inorder(root);
}

void btree::postorderTraversal()
{
postorder(root);
}

int btree::treeHeight()
{
return height(root);
}

int btree::treeLeavesCount()
{
return leavesCount(root);
}

int btree::theNodeCount()
{
return nodeCount(root);
}
void btree::destroyTree()
{
destroy(root);
}
//
void btree::preorder(bnode *p)
{
if(p!=NULL)
{
cout<data<<" ";
preorder(p->lchild);
preorder(p->rchild);
}
}

void btree::inorder(bnode *p)
{
if(p!=NULL)
{
inorder(p->lchild);
cout<data<<" ";
inorder(p->rchild);
}
}

void btree::postorder(bnode *p)
{
if(p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
cout<data<<" ";
}
}

void btree::inTravAndShow(bnode *p)
{
if(p!=NULL)
{
layer++;
inTravAndShow(p->lchild);
cout<<"层数:"< cout<data<<" ";
inTravAndShow(p->rchild);
layer--;

}
}

int btree::height(bnode *p)
{
if(p==NULL) return 0;
return max(height(p->lchild),height(p->rchild))+1;
}
int btree::max(int x,int y)
{
if(x>y) return x;
else return y;
}
int btree::nodeCount(bnode *p)
{
int num1,num2;
if(p==NULL) return 0;
else
if(p->lchild==NULL&&p->rchild==NULL) return 1;
else
{
num1=nodeCount(p->lchild);
num2=nodeCount(p->rchild);
return (num1+num2)+1;
}

}
int btree::leavesCount(bnode *p)
{
int num=0;
if(p!=NULL)
if(p->lchild!=NULL||p->rchild!=NULL)
{
return leavesCount(p->lchild)+leavesCount(p->rchild);
}
else
num++;
return num;
}

void btree::destroy(bnode *p)
{
}
btree::btree()
{
root=NULL;
}
btree::~btree()
{
destroy(root);
}
void btree::changeLR(bnode *&p)
{
if (p!=NULL)
{
bnode *tem=p->lchild;
p->lchild=p->rchild;
p->rchild=tem;
changeLR(p->lchild);
changeLR(p->rchild);
}
}追问复制黏贴也看清楚题目呀。。你这明显是先序建立的二叉树。。

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

给出层次遍历的结果 求建立二叉树的过程

给出层次遍历的结果求建立二叉树的过程