如何在数据结构中，以二叉链表为存储结构，建立一棵二叉树，输出其先序，中序，后序遍历序列，统计其叶子
#include
#include
#include
#include"c6_2.h"
#include#define TRUE 1
#define NULL 0
#define FALSE 0
#define ERROR 0
#define WRONG 0
#define OK 1
#define OVERFLOW 0typedef int TElemType;
typedef int Status;//二叉树结构体
typedef struct BiTNode
{ TElemType data;//结点的值
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//队列结构体
typedef BiTree QElemType;
typedef struct QNode
{ QElemType data;
QNode *next;
}*QueuePtr;struct LinkQueue
{ QueuePtr front,rear;//队头，队尾指针
};#define ClearBiTree DestoryBiTree//清空二叉树的操作和销毁二叉树的操作一样
void InitBiTree(BiTree &T)
{ T=NULL;
}
void DestroyBiTree(BiTree &T)
{ //销毁二叉树
if(T)
{ DestroyBiTree(T->lchild);//销毁左子树
DestroyBiTree(T->rchild);//销毁右子树
free(T);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*visit)(TElemType))
{//先序遍历二叉树
if(T)
{ visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
}
void InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍历二叉树
if(T)
{ InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
}
}
void PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //后序遍历二叉树
if(T)
{ PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
}
}
Status BiTreeEmpty(BiTree T)
{ //判断二叉树是否为空
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)//返回T的深度
{ int i,j;
if(!T)
return 0;
i=BiTreeDepth(T->lchild);//i为左孩子的深度
j=BiTreeDepth(T->rchild);//j为右孩子的深度
return i>j?i+1:j+1;
}
TElemType Root(BiTree T)
{ //返回二叉树的根结点
if(BiTreeEmpty(T))
return NULL;
else
return T->data;
}
TElemType Value(BiTree p)
{//返回P所指结点的值
return p->data;
}
void Assign(BiTree p,TElemType value)
{ //给P的结点赋新值
p->data=value;
}BiTree Point(BiTree T,TElemType s)//返回二叉树T中指向元素值为S的结点指针
{ LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))//队不空
{ DeQueue(q,a);//出队，队列元素赋给e
if(a->data==s)//a所指结点为的值为s
return a;
if(a->lchild)//有左孩子
EnQueue(q,a->lchild);//入队左孩子
if(a->rchild)//有右孩子
EnQueue(q,a->rchild);//入队右孩子
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{ a=Point(T,e);//a是指向结点e的指针
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e)
{ BiTree a;
if(T)
{ a=Point(T,e);//a是指向结点e的指针
if(a&&a->rchild)//T中存在结点e并且e存在右孩子
return a->rchild->data;
}
return NULL;
}
Status DeleteChild(BiTree p,int LR)
{ if(p)
{ if(LR==0)
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return OK;
}
return ERROR;
}void visit(TElemType e)
{ printf("%d",e);
}
void LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//层序遍历
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))
{ DeQueue(q,a);//出队元素，赋给a
visit(a->data);//访问a所指结点
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
}
}
void CreateBiTree(BiTree &T)
{ TElemType ch;scanf("%d",&ch);//输入结点的值
if(ch==0)//结点为空
T=NULL;
else
{T=(BiTree)malloc(sizeof(BiTNode));//生成根结点if(!T)exit(OVERFLOW);T->data=ch;//将值赋给T所指结点
CreateBiTree(T->lchild);//递归构造左子树CreateBiTree(T->rchild);} } TElemType Parent(BiTree T,TElemType e)
{//返回双亲
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);
EnQueue(q,T);//树根入队列
while(!QueueEmpty(q))//队不空
{DeQueue(q,a);//出队，队列元素赋给a if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)//找到e return a->data; else { if(a->lchild) EnQueue(q,a->lchild);//入队列左孩子 if(a->rchild) EnQueue(q,a->rchild);//入队列右孩子 }
}
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{ p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右孩子
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{ p=Point(T,a);//p为指向结点的a的指针
if(p->lchild&&p->rchild&&p->lchild->data==e)
return p->lchild->data;
}
}
return NULL;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{ //根据LR为0或1，插入C为T中P所指结点的左或右子树，P所结点的原有左或右子树则成为C的右子树
if(p)
{ if(LR==0)//把二叉树C插入P所指结点的子树
{ c->rchild=p->lchild;//p所结点的原有左子树成为C的右子树
p->lchild=c;//二叉树成为P的左子树
}
else{ c->rchild=p->rchild;//p指结点的原有右子树成为C的右子树
p->rchild=c;
}
return OK;
}
return ERROR;
}
//队列操作
void InitQueue(LinkQueue &Q)
{//初始化一个队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)//生成头结点失败
exit(OVERFLOW);
Q.front->next=NULL;
}
Status QueueEmpty(LinkQueue Q)
{ //判断队列是否为空
if(Q.front->next==NULL)
return TRUE;
else return FALSE;
}void EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e为队列Q的新的队尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
//动态生成新结点
if(!p)
exit(OVERFLOW);
p->data=e;//将e的值赋给新结点
p->next=NULL;//新结点的指针为空
Q.rear->next=p;//原队尾结点的指针域为指向新结点
Q.rear=p;//尾指针指向新结点
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ //若队列不为空，删除Q的队头元素，用e返回其值
QueuePtr p;
if(Q.front==Q.rear)//队列为空
return ERROR;
p=Q.front->next;//p指向队头结点
e=p->data;//队头元素赋给e
Q.front->next=p->next;//头结点指向下一个结点
if(Q.rear==p)//如果删除的队尾结点
Q.rear=Q.front;//修改队尾指针指向头结点
free(p);
return OK;
}
//主函数文件
#include
#include"c6_2.h"main()
{ int i,j;
BiTree T,p,c;
TElemType e0,e1,e2,e3,e4;
InitBiTree(T);//初始化二叉树
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.
",BiTreeEmpty(T),BiTreeDepth(T));CreateBiTree(T);//建立二叉树T
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.
",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);//e1为二叉树T的根结点的值
if(e1!=NULL)
printf("二叉树的根为%d",e1);
else
printf("树空，无根");e2=LeftChild(T,e1);
printf("左孩子:%d",e2);
e3=RightChild(T,e1);
printf("右孩子:%d",e3);
printf("
");printf("先序递归遍历:
");
PreOrderTraverse(T,visit);
printf("
");printf("后序递归遍历:
");
PostOrderTraverse(T,visit);
printf("
");printf("中序递归遍历:
");
InOrderTraverse(T,visit);
printf("
");printf("输入一个结点的值:");
scanf("%d",&e1);
p=Point(T,e1);//p指向为e的指针
printf("结点的值为%d
",Value(p));
e0=Parent(T,e1);//返回e1的双亲
printf("结点%d的双亲为%d",e1,e0);
printf("
");e0=LeftChild(T,e1);//返回e1的左孩子
if(e0==NULL)
printf("没有孩子");
else
printf("左孩子为%d",e0);
printf("
");e0=RightChild(T,e1);//返回e1的右孩子
if(e0==NULL)
printf("没有右孩子");
else
printf("右孩子为%d",e0);
printf("
");
e0=RightSibling(T,e1);//返回e1的右兄弟
if(e0!=NULL)
printf("右兄弟为%d",e0);
else
printf("没有右兄弟");
printf("
");e0=LeftSibling(T,e1);//返回e1的左兄弟
if(e0!=NULL)
printf("左兄弟为%d",e0);
else
printf("没有左兄弟");
printf("
");
printf("要改变结点%d的值，请输入新值:",e1);
scanf("%d",&e2);
Assign(p,e2);//将e2的值赋给p所指结点，代替e1
printf("层序遍历二叉树:
");
LevelOrderTraverse(T,visit);
printf("
");
printf("创建一棵根结点右子树为空的新树:");
CreateBiTree(c);//创建二叉树
printf("先序递归遍历二叉树c:
");
PreOrderTraverse(c,visit);
printf("将树C插入树T中，请输入树T中树C的双亲结点C为左（0）或右（1）子树:");
scanf("%d,%d",&e1,&i);
p=Point(T,e1);//p指向二叉树T中将T中作为二叉树C的双亲结点的e1
InsertChild(p,i,c);//将树C插入到二叉树T中作为结点的左或右子树
printf("构造二叉树后，树空否?%d(1,是,0否).树的深度=%d.
",BiTreeEmpty(T),BiTreeDepth(T));
printf("先序递归遍历二叉树:
");
PreOrderTraverse(T,visit);
}
#include
#include
typedef char ElemType;
struct BTreeNode
{
ElemType data;
BTreeNode*left;
BTreeNode*right;
};
void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
const int MaxSize=1000;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i])
{
case ' ':
break;
case'(':
if(top==MaxSize-1)
{
cout<<"栈空间太少，请增加MaxSize的值！"<<endl;
exit(1);
}
top++; s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
cout<<"二叉树的广义表出错!"<<endl; exit(1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT==NULL) BT=p;
else
{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree (BTreeNode*BT)
{
return BT==NULL;
}
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
coutdata<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
}
void InOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
coutdata<<' ';
InOrder(BT->right);
}
}
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
coutdata<<' ';
}
}
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while (front!=rear)
{
front=(front+1)%MaxSize;
p=q[front];
coutdata<<' ';
if(p->left!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
void PrintBTree(BTreeNode*BT)
{
if(BT!=NULL)
{
coutdata;
if(BT->left!=NULL || BT->right!=NULL )
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
void ClearBTree(BTreeNode*&BT)
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}
void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"输入二叉树的广义表字符串"<<endl;
cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt); cout<<endl;
cout<<"前序："; PreOrder(bt);cout<<endl;
cout<<"中序："; InOrder(bt); cout<<endl;
cout<<"后序: "; PostOrder(bt); cout<<endl;
cout<<"按层："; LevelOrder(bt); cout<<endl;
}
下面我写的代码：
/* Note:Your choice is C IDE */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct lbtree
{
char data;
struct lbtree *lchild,*rchild;
};
struct lbtree *createbtree();
void preorder(struct lbtree *root);
void inorder(struct lbtree *root);
void postorder(struct lbtree *root);
treedepth(struct lbtree *root);
numberofleaf(struct lbtree *root);
main()
{
struct lbtree *root;
int i;
printf("create a tree
");
printf("please input nodes of tree
");
root=NULL;
root=createbtree();
if(root==NULL)printf("This is an empty tree!
");
else
{
printf("
");
printf("1.The preorder traverse
");
printf("2.The inorder traverse
");
printf("3.The postorder traverse
");
printf(" Please choose a kind of order
");
scanf("%d",&i);
switch(i)
{
case 1:preorder(root);break;
case 2:inorder(root);break;
case 3:postorder(root);break;
default:printf("error!
");
}
}
printf("
The depth of the btree is %d",treedepth(root));
printf("
The leafnumber of the btree is %d",numberofleaf(root));
}
struct lbtree *createbtree()
{
char ch,t;
struct lbtree *root;
printf("please input the data,'$' is the end.
");
scanf("%c",&ch);
scanf("%c",&t);
if(ch=='$')
return(NULL);
else
{
root=(struct lbtree *)malloc(sizeof(struct lbtree));
root->data=ch;
root->lchild=createbtree();
root->rchild=createbtree();
return(root);
}
printf("ok!");
}
void preorder(struct lbtree *root)
{
if(root)
{
printf(" %c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void inorder(struct lbtree *root)
{
if(root){inorder(root->lchild);
printf(" %c",root->data);
inorder(root->rchild);
}
}
void postorder(struct lbtree *root)
{
if(root)
{
postorder(root->lchild);
postorder(root->rchild);
printf(" %c",root->data);
}
}
treedepth(struct lbtree *root)
{
int depth,dl,dr;
if(!root)depth=0;
else
{
dl=treedepth(root->lchild);
dr=treedepth(root->rchild);
if(dl>dr)depth=dl+1;
else depth=dr+1;
}
return(depth);
}
numberofleaf(struct lbtree *root)
{
int num=0,num1,num2;
if(root)
{
if((root->lchild==NULL)&&(root->rchild==NULL))num=1;
else
{ num1=numberofleaf(root->lchild);
num2=numberofleaf(root->rchild);
num=num1+num2;
}
}
return(num);
}
运行结果如图：
#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode
{ ELEMTYPE data;
struct BiTNode *lchild,*rchild;
} BiTNode;
BiTNode *bulid() /*建树*/
{ BiTNode *q;
BiTNode *s[20];
int i,j;
char x;
printf("请按顺序输入二叉树的结点以输入0和*号结束\n");
printf("请输入你要输入的为第几个结点i=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数为x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
s[i]=q;
if(i!=1)
{ j=i/2;
if(i%2==0)
s[j]->lchild=q;
else
s[j]->rchild=q;
}
printf("请输入你要输入的为第几个结点x=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数x=");
getchar();
scanf("%c",&x);
}
return s[1];
}
void preoder(BiTNode *bt) /*先序遍历*/
{ if(bt!=NULL)
{
printf("%c\n",(bt->data));
preoder(bt->lchild);
preoder(bt->rchild);
}
}
void InOrder(BiTNode *bt) /*中序遍历*/
{ if(bt!=NULL)
{ InOrder(bt->lchild);
printf("%c\n",bt->data);
InOrder(bt->rchild);
}
}
void postOrder(BiTNode *bt) /*后序遍历*/
{ if(bt!=NULL)
{ postOrder(bt->lchild);
postOrder(bt->rchild);
printf("%c\n",bt->data);
}
}
main()
{ int a;
BiTNode *bt;
bt=bulid();
k1: printf("需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:");
scanf("%d",&a);
switch(a)
{
case(1): preoder(bt); goto k1;
case(2): InOrder(bt); goto k1;
case(3): postOrder(bt); goto k1;
case(0): break;
}
}
3
随便一本数据结构的入门书上都有
如何在数据结构中,以二叉链表为存储结构,建立一棵二叉树,输出其先序...
答：下面我写的代码：/* Note:Your choice is C IDE */ include <stdio.h> include <stdlib.h> include <malloc.h> struct lbtree { char data;struct lbtree *lchild,*rchild;};struct lbtree *createbtree();void preorder(struct lbtree *root);void inorder(struct lbtree *root);void pos...
数据结构中,怎样以二叉链表为存储结构,分别写出求二叉树结点总数及叶...
答：cout<<"请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式："<<endl;cout<<"n= ";cin>>n;p=(inform* )malloc( n*sizeof(inform) ); /*开辟的一个叶子结构体型的指针数组*/ inform *p1; p1=p;for(int i=0; i<n; i++){ cin>>(p+i)->data>>(p+i)->...
数据结构 c语言版二叉树(1) 建立一棵含有n个结点的二叉树,采用二叉链 ...
答：printf("构建一个二叉树（结点数为n)：\n");root=create(root);printf("前序遍历二叉树：\n");preorder(root);printf("\n");printf("中序遍历二叉树：\n");inorder(root);printf("\n");printf("后序遍历二叉树：\n");postorder(root);printf("\n");} ...
数据结构二叉树的基本操作~~~
答：1．以二叉链表表示二叉树，建立一棵二叉树；2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果；4．输出二叉树的后序遍历结果；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；7．计算二叉树的深度。8．交换二叉树每个结点的左孩子和右孩子；include <malloc.h> include <stdio.h...
以二叉链表为存储结构,写出求二叉树高度和宽度的算法
答：以二叉链表为存储结构,分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上,具有结点数最多的那一层上的结点总数。标准答案:①求树的高度思想:对非空二叉树,其深度等于左子树的最大深度加1。Int Depth(BinTree *T){int dep1,dep2;if(T==Null) return(0);else{dep1=Depth(T->lchild);...
以二叉链表为存储结构,分别写出求二叉树结点总数及叶总数的算法。(数据...
答：int CountNode (BTNode *t) //节点总数 { int num;if (t == NULL)num = 0;else num = 1 + CountNode (t->lch) + CountNode (t->rch);return (num);} void CountLeaf (BTNode *t) //叶子节点总数 { if (t != NULL){ if (t->lch == NULL && t->rch == NULL)count...
以二叉链表作存储结构,试编写求二叉树高度的算法
答：Soucula 采纳率:84% 擅长: 数据结构及算法 C/C++ VC++ JAVA相关 为您推荐: 完全二叉树 平衡二叉树 利用二叉链表存储树 若二叉树采用二叉链表 二叉树遍历 什么是二叉树 二叉链表存储结构 二叉树实验报告 二叉树的遍历算法 二叉树的度 其他...
数据结构 二叉树 用二叉链链表存储结构 写出删除二叉树所有的叶子节点的...
答：//初始条件：二叉树T存在，Visit是对结点操作的应用函数 //操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 void PreOrderTraverse(BiTree T){ if (T)//T不空 { printf("%c",T->data);//先访问根结点 PreOrderTraverse(T->lchild);//再先序遍历左子树 PreOrderTraverse(T->...
设二叉树以二叉链表存储,删除一颗二叉树,并释放所有的结点空间的算法...
答：void Binary_Output(Bitnode *t) //前序遍历二叉树 { if (t != NULL){ printf("%d ", t->data);Binary_Output(t->lchild);Binary_Output(t->rchild);} } void Binary_Delete(Bitnode *t) //释放空间 { if (t != NULL){ Binary_Delete(t->lchild);Binary_Delete(t->rchild);...
数据结构的二叉树中,怎么输入字符序列,建立二叉链表?
答：{ // 先序遍历二叉树 if (T==NULL) return;InOrderTraverse(T->lchild, visit); // 遍历左子树 visit(T->data); // 访问根结点 InOrderTraverse(T->rchild, visit); // 遍历右子树 } void main(){ BiTree R;printf("输入带空指针标记的先序序列:(例如AB C D )\n");Create...
