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

答案:2 悬赏:0

解决时间 2021-02-20 00:14

提问者网友：故事与他
2021-02-19 18:51

例如给出的序列是abc*de***fgh***（*代表空节点）
树的形状为(不会作图。。。)
a
b c
* d e *
f g h *

要c语言写的程序。。我不要先序建立二叉树的程序

最佳答案

二级知识专家网友：我们只是兮以城空
2021-02-19 19:06

#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);
}
}

全部回答

1楼网友：晨与橙与城
2021-02-19 20:02

二叉树具有以下重要性质：性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。证明：用数学归纳法证明：归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。归纳假设：假设对所有的j(1≤j2k-1-1。另一方面，由性质2可得： n≤2k-1，即：2k-1-l

我要举报

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

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

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