/*课程设计题十五：.二叉树用二叉链表表示
一、 设计目的
1．掌握二叉树的概念和性质
2. 掌握任意二叉树存储结构。
3．掌握任意二叉树的基本操作。
二、设计内容和要求
1． 实现二叉树的建立、前序（非递归）、中序和层次遍历；
2． 求二叉树高度、结点数、度为1的结点数和叶子结点数；
3． 插入结点到指定位置、删除指定结点；
4． 将二叉树所有结点的左右子树交换。
源代码 */
#include
#include
#include
#define MAXNODE 100
//树的建立
typedef struct bitnode
{ char data;
struct bitnode *lchild,*rchild;
}bitnode,*bintree;
//二叉树的二叉链表的存储算法
void createbintree(bintree *t)
{ char ch;
cin>>ch;
if(ch=='0')
(*t)=NULL;
else
{ (*t)=new bitnode;
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
//9.中序遍历
void inorderout(bintree bt)
{
if(bt!= NULL){
inorderout(bt->lchild);
printf("%c ", bt->data);
inorderout(bt->rchild);
}
return;
}
/* 11.按层遍历 */
void translevel(bintree b)
{ struct node
{
bitnode *vec[MAXNODE];
int f,r;
} q;
q.f=0;
q.r=0;
if(b!=NULL)printf("%c ",b->data);
q.vec[q.r]=b;
q.r=q.r+1;
while(q.f {
b=q.vec[q.f];
q.f=q.f+1;
if(b->lchild!=NULL)
{
printf("%c ",b->lchild->data);
q.vec[q.r]=b->lchild;
q.r=q.r+1;
}
if(b->rchild!=NULL)
{
printf("%c ",b->rchild->data);
q.vec[q.r]=b->rchild;
q.r=q.r+1;}
}
}
/* 6.输出二叉树(前序遍历) */
void preorder(bitnode *b)
{
bitnode *stack[MAXNODE],*p;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
printf("%c ",p->data);
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
}
/*求树的高度 */
int depth(bitnode *b)
{
int dep1,dep2;
if(b==NULL) return(0);
else
{
dep1=depth(b->lchild);
dep2=depth(b->rchild);
if(dep1>dep2)return(dep1+1);
else return(dep2+1);
}
}
/*所有叶子结点数 */
int countleaf(bintree bt)
{ if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
return (countleaf(bt->lchild)+countleaf(bt->rchild));
}
/*所有结点数 */
int btreecount(bintree bt)
{ if(bt==NULL)
return 0;
else return btreecount(bt->lchild)+btreecount(bt->rchild)+1;
}
/*求度为“1”的结点总数*/
int onechild(bitnode * b)/*求度为“1”的结点总数*/
{
int num1,num2;
if(b==NULL)return(0);
else if(b->lchild==NULL&&b->rchild!=NULL)
return(1+onechild(b->rchild));
if(b->lchild!=NULL&&b->rchild==NULL)
return(1+onechild(b->lchild));
else
{
num1=onechild(b->lchild);
num2=onechild(b->rchild);
return(num1+num2);
}
}
/*将结点的左右子树交换*/
bitnode *swap(bitnode *b)
{
bitnode *t,*t1,*t2;
if(b==NULL) t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=b->data;
t1=swap(b->lchild);
t2=swap(b->rchild);
t->lchild=t2;
t->rchild=t1;
}
return(t);
}
/*插入左子树*/
bitnode *insertl(bitnode *b,char x,char e)
{
bitnode *stack[MAXNODE],*p,*s,*t;
s=(bitnode*)malloc(sizeof(bitnode));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
printf("%c ",p->data);
if(p->data==x)t=p;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
s->lchild=t->lchild;
s->rchild=t->rchild;
t->lchild=s;
printf("\n");
return(b);
}
void print(bitnode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
print(b->lchild);
if(b->rchild!=NULL)printf(", ");
print(b->rchild);
printf(")");
}
}
}
/*插入右子树*/
bitnode *insertr(bitnode *b,char x,char e)
{
bitnode *stack[MAXNODE],*p,*s,*t;
s=(bitnode*)malloc(sizeof(bitnode));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
printf("%c ",p->data);
if(p->data==x)t=p;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
s->lchild=t->lchild;
s->rchild=t->rchild;
t->rchild=s;
printf("\n");
return(b);
}
/*删除左子树*/
bitnode *deletl(bitnode *b,char x)
{
bitnode *stack[MAXNODE],*p,*t;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
printf("%c ",p->data);
if(p->data==x)t=p;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
t->lchild=NULL;
printf("\n");
return(b);
}
/*删除右子树*/
bitnode *deletr(bitnode *b,char x)
{
bitnode *stack[MAXNODE],*p,*t;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
printf("%c ",p->data);
if(p->data==x)t=p;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
t->rchild=NULL;
printf("\n");
return(b);
}
void main()
{
int a;
bintree bt;
printf("\n\n\n***************二叉树的二叉链表表示***************");
cout printf("\n请按先序输入二叉树：\n");
createbintree(&bt);
printf("请选择你要进行的操作：\n");
printf("1.输出树的高度、叶子结点数、所有结点数、度为1的结点数；\n");
printf("2.非递归前序遍历、中序遍历和层次遍历；\n");
printf("3.交换左右子树；\n");
printf("4.插入结点的左孩子；\n");
printf("5.插入结点的右孩子；\n");
printf("6.删除结点的左孩子；\n");
printf("7.删除结点的右孩子；\n");
printf("0.退出程序；\n");
cin>>a;
for(;a!=0;)
{
if(a==1)
{
printf("树的高度为：%d",depth(bt));
printf("\n");
printf("叶子结点数为：%d",countleaf(bt));
printf("\n");
printf("所有结点数为：%d",btreecount(bt));
printf("\n");
printf("度为1的结点数为：%d",onechild(bt));
printf("\n");
cout }
if(a==2)
{
printf("前序遍历为：");
preorder(bt);
printf("\n");
printf("中序遍历为：");
inorderout(bt);
printf("\n");
printf("层次遍历为：");
translevel(bt);
printf("\n");
cout }
if(a==3)
{
printf("交换后的树中序输出为：");
inorderout(swap(bt));
cout
}
if(a==4)
{
printf("请输入要插入结点的双亲及要插入的元素(如bc)-----");
char x,e;
cin>>x>>e;
print(insertl(bt, x, e));
cout
}
if(a==5)
{
printf("请输入要插入结点的双亲及要插入的元素(如bc)-----");
char x,e;
cin>>x>>e;
print(insertr(bt, x, e));
cout
}
if(a==6)
{
printf("请输入要删除的双亲结点-----");
char y;
cin>>y;
print(deletl(bt, y));
cout
}
if(a==7)
{
printf("请输入要删除的双亲结点-----");
char y;
cin>>y;
print(deletr(bt, y));
cout
}
printf("请选择你要进行的操作：\n");
printf("1.输出树的高度、叶子结点数、所有结点数、度为1的结点数；\n");
printf("2.非递归前序遍历、中序遍历和层次遍历；\n");
printf("3.交换左右子树；\n");
printf("4.插入结点的左孩子；\n");
printf("5.插入结点的右孩子；\n");
printf("6.删除结点的左孩子；\n");
printf("7.删除结点的右孩子；\n");
printf("0.退出程序；\n\n\n");
cin>>a;
}
}
