Question

一道数据结构题目--二叉树用二叉链表表示

二叉树用二叉链表表示
1． 实现二叉树的建立、前序（非递归）、中序和层次遍历；
2． 求二叉树高度、结点数、度为1的结点数和叶子结点数；
3． 插入结点到指定位置、删除指定结点；
4． 将二叉树所有结点的左右子树交换。
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);
}
}

//中序遍历
void inorderout(bintree t)
{ inorderout(t->lchild);
cout<<t->data<<endl;
inorderout(t->rchild);

}

void main()
{ bintree bt;
createbintree(&bt);
inorderout(bt);
}

Answer 1

6-11 写出二叉树的先序遍历非递归算法。
答案：
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
《数据结构》习题解
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌 while 实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
6-12 写一算法求二叉树中结点的总数，可以写出多少种方法？
答案：
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{ char data; /*此例中二叉树的结点采用字符类型*/
struct node *lchild, *rchild;
}NODE;
NODE *crt_bt_pre( ) /*按先序遍历序列创建二叉树的二叉链表*/
{
/* 输入 ABC00DE0G00F000 */
NODE *bt;
char ch;
printf("\n\t\t\t");
scanf("%c",&ch);
getchar( );
if(ch==' ')
bt=NULL;
else
{
bt=(NODE *)malloc(sizeof(NODE));
bt->data=ch;
printf("\n\t\t\t 请输入%c 结点的左孩子：",bt->data);
bt->lchild=crt_bt_pre( );
printf("\n\t\t\t 请输入%c 结点的右孩子：",bt->data);
bt->rchild=crt_bt_pre();
}
return(bt);
}
《数据结构》习题解
void CountNode(NODE* bt,int *p) /*统计二叉树中结点的总数*/
{
if(bt==NULL)
return;
else
{
(*p)++;
CountNode(bt->lchild,p);
CountNode(bt->rchild,p);
return;
}
}
main()
{ NODE *crt_bt_pre( )
CountNode(bt,&b); /*调用统计结点总数的函数*/
printf("\n\t\t\t 该二叉树共有%d 个结点。\n",b);
}
6-13 写一算法将二叉树中所有结点的左、右子树相互交换。
答案：
#include "datastru.h"
#include <stdio.h>
#include <malloc.h>
#include "二叉树.c"
BTCHINALR *change(BTCHINALR *bt)
/*二叉树左右子树交换递归算法*/
{ BTCHINALR *p;
if(bt!=NULL)
if(bt->lchild!=NULL || bt->rchild!=NULL)
{p=(BTCHINALR*)malloc(sizeof(BTCHINALR));
p->data=bt->data;
p->rchild=NULL;
p->lchild=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=p->lchild;
bt->lchild=change(bt->lchild);
bt->rchild=change(bt->rchild);
}
return bt;
}

#include<iostream.h>
#include<stdio.h>
#include<iomanip.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
#include<shlobj.h>
#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 levelorder(bintree bt)
{ bintree queue[MAXNODE];
int front,rear;
if(bt==NULL)
return;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{front++;
cout<<queue[front]->data;
if(queue[front]->lchild!=NULL)
{rear++;
queue[rear]=queue[front]->lchild;
}
if(queue[front]->rchild!=NULL)
{rear++;
queue[rear]=queue[front]->rchild;
}

}

}

/* 6.输出二叉树(前序遍历) */
void printBTree(bintree bt)
{ /* 树为空时结束递归，否则执行如下操作 */
if(bt!=NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->lchild!= NULL||bt->rchild!=NULL){
printBTree(bt->lchild);
if(bt->rchild!= NULL){
}
printBTree(bt->rchild);
} }
return; }

/*求树的高度 */
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;
}

void main()
{

bintree bt;
createbintree(&bt);
printf("树的高度为：\n");
printf("%d",depth(bt));
printf("\n");
printf("叶子结点数为：\n");
printf("%d",countleaf(bt));
printf("\n");
printf("所有结点数为：\n");
printf("%d",btreecount(bt));
printf("\n");
printf("前序遍历为：\n");
printBTree(bt);
printf("\n");
printf("中序遍历为：\n");
inorderout(bt);
printf("\n");
printf("层次遍历为：");
levelorder(bt);
printf("\n");

}