二叉树的建立，采取while switch（）后执行起来就不对了，大神们帮忙看看
二叉树的建立，采用while switch（）后执行起来就不对了，大神们帮忙看看
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW -1
typedef char TElemType;
typedef struct BitNode
{
TElemType data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
typedef struct QNode
{
BitNode data;
struct QNode *next;
}QNode,*Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}LinkQueue;
BitTree BitTreeInit(BitTree BT)
{
BT=(BitTree)malloc(sizeof(BitNode));
BT=NULL;
return BT;
}
BitTree BitTreeCreat(BitTree &BT)
{
char c;
scanf("%c",&c);
if(c==' ') BT=NULL;
else
{
if(!(BT=(BitTree)malloc(sizeof(BitNode))))
exit(OVERFLOW);
BT->data=c;
BitTreeCreat(BT->lchild);
BitTreeCreat(BT->rchild);
}
return BT;
}
void BitTreeEmpty(BitTree BT)
{
if(!BT) printf("树为空!\n");
else printf("树非空!\n");
}
void visit(BitTree BT)
{
printf("%c",BT->data);
}
void PreOrderTraverse(BitTree BT)
{
if(BT)
{
visit(BT);
PreOrderTraverse(BT->lchild);
PreOrderTraverse(BT->rchild);
}
}
void InOrderTraverse(BitTree BT)
{
if(BT)
{
InOrderTraverse(BT->lchild);
visit(BT);
InOrderTraverse(BT->rchild);
}
}
void PostOrderTraverse(BitTree BT)
{
if(BT)
{
PostOrderTraverse(BT->lchild);
PostOrderTraverse(BT->rchild);
visit(BT);
}
}
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));
if(!Q->front) exit(OVERFLOW);
Q->front->next=NULL;
}
int QueueEmpty(LinkQueue *Q)
{
if(Q->front==Q->rear) return 1;//是==不是=
else return 0;
}
void EnQueue(LinkQueue *Q,BitNode e)
{
QNode *p;
p=(Queueptr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
void DeQueue(LinkQueue *Q,BitTree e)
{
QNode *p;
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p) Q->rear=Q->front;
free(p);
}
void BFSTraverse(BitTree BT)
{
BitNode m;
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q,*BT);
while(!QueueEmpty(&Q))
{
DeQueue(&Q,&m);
visit(&m);
if(m.lchild) EnQueue(&Q,*(m.lchild));
if(m.rchild) EnQueue(&Q,*(m.rchild));
}
}
int BitTreeDepth(BitTree BT)
{
int dep1,dep2;
if(BT==NULL) return 0;
else
{
dep1=BitTreeDepth(BT->lchild);
dep2=BitTreeDepth(BT->rchild);
if(dep1>dep2) return dep1;
else return dep2;
}
}
void BitCountleaf(BitTree BT,int *count)
{
if(BT)
{
if(!BT->lchild&&!BT->rchild)
(*count)++;
BitCountleaf(BT->lchild,count);
BitCountleaf(BT->rchild,count);
}
}
void BitTreeClear(BitTree &BT)
{
if(BT)
{
BitTreeClear(BT->lchild);
BitTreeClear(BT->rchild);
free(BT);
BT=NULL;
}
}
int main()
{
int i=1,j,count=0;
BitTree BT;
while(i!=0){
printf("-----------------欢迎使用-------------------\n");
printf("请选择要进行的操作\n");
printf("1.初始化一棵树 2.建立一棵树 3.判断树是否为空\n");
printf("4.按先序遍历树 5.按中序遍历树 6.按后序遍历树\n");
printf("7.按层次遍历树 8.求树的深度 9.求树的叶子节点个数\n");
printf("0.把树清空\n");
printf("-----------------感谢使用-------------------\n");
scanf("%d",&j);
switch(j){
case 1:BT=BitTreeInit(BT); break;
case 2:printf("请输入二叉树(空格代表树的元素为空,最后输入空格键结束输入):\n");
BT=BitTreeCreat(BT);break;
case 3:BitTreeEmpty(BT);break;
case 4:printf("先序遍历: ");
PreOrderTraverse(BT);printf("\n");break;
case 5:printf("中序遍历:");
InOrderTraverse(BT);printf("\n");break;
case 6: printf("后序遍历:");
PostOrderTraverse(BT);printf("\n");break;
case 7:printf("层次遍历：");
BFSTraverse(BT);printf("\n");break;
case 8:printf("该树的深度是%d\n",BitTreeDepth(BT));break;
case 9:BitCountleaf(BT,&count);
printf("二叉树的叶子节点个数为:%d\n",count);break;
case 0:BitTreeClear(BT);break;
return 0;
}
}
}
------解决思路----------------------
仅供参考：
------解决思路----------------------
修改如下：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW -1
typedef char TElemType;
typedef struct BitNode
{
TElemType data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
typedef struct QNode
{
BitNode data;
struct QNode *next;
}QNode,*Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}LinkQueue;
BitTree BitTreeInit(BitTree BT)
{
BT=(BitTree)malloc(sizeof(BitNode));
BT=NULL;
return BT;
}
BitTree BitTreeCreat(BitTree &BT)
{
char c;
scanf("%c",&c);
if(c==' ') BT=NULL;
else
{
if(!(BT=(BitTree)malloc(sizeof(BitNode))))
exit(OVERFLOW);
BT->data=c;
BitTreeCreat(BT->lchild);
BitTreeCreat(BT->rchild);
}
return BT;
}
void BitTreeEmpty(BitTree BT)
{
if(!BT) printf("树为空!\n");
else printf("树非空!\n");
}
void visit(BitTree BT)
{
printf("%c",BT->data);
}
void PreOrderTraverse(BitTree BT)
{
if(BT)
{
visit(BT);
PreOrderTraverse(BT->lchild);
PreOrderTraverse(BT->rchild);
}
}
void InOrderTraverse(BitTree BT)
{
if(BT)
{
InOrderTraverse(BT->lchild);
visit(BT);
InOrderTraverse(BT->rchild);
}
}
void PostOrderTraverse(BitTree BT)
{
if(BT)
{
PostOrderTraverse(BT->lchild);
PostOrderTraverse(BT->rchild);
visit(BT);
}
}
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));
if(!Q->front) exit(OVERFLOW);
Q->front->next=NULL;
}
int QueueEmpty(LinkQueue *Q)
{
if(Q->front==Q->rear) return 1;//是==不是=
else return 0;
}
void EnQueue(LinkQueue *Q,BitNode e)
{
QNode *p;
p=(Queueptr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
void DeQueue(LinkQueue *Q,BitTree e)
{
QNode *p;
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p) Q->rear=Q->front;
free(p);
}
void BFSTraverse(BitTree BT)
{
BitNode m;
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q,*BT);
while(!QueueEmpty(&Q))
{
DeQueue(&Q,&m);
visit(&m);
if(m.lchild) EnQueue(&Q,*(m.lchild));
if(m.rchild) EnQueue(&Q,*(m.rchild));
}
}
int BitTreeDepth(BitTree BT)
{
int dep1,dep2;
if(BT==NULL) return 0;
else
{
dep1=BitTreeDepth(BT->lchild);
dep2=BitTreeDepth(BT->rchild);
if(dep1>dep2) return dep1;
else return dep2;
}
}
void BitCountleaf(BitTree BT,int *count)
{
if(BT)
{
if(!BT->lchild&&!BT->rchild)
(*count)++;
BitCountleaf(BT->lchild,count);
BitCountleaf(BT->rchild,count);
}
}
void BitTreeClear(BitTree &BT)
{
if(BT)
{
BitTreeClear(BT->lchild);
BitTreeClear(BT->rchild);
free(BT);
BT=NULL;
}
}
int main()
{
int i=1,j,count=0;
BitTree BT;
while(i!=0){
printf("-----------------欢迎使用-------------------\n");
printf("请选择要进行的操作\n");
printf("1.初始化一棵树 2.建立一棵树 3.判断树是否为空\n");
printf("4.按先序遍历树 5.按中序遍历树 6.按后序遍历树\n");
printf("7.按层次遍历树 8.求树的深度 9.求树的叶子节点个数\n");
printf("0.把树清空\n");
printf("-----------------感谢使用-------------------\n");
scanf("%d",&j);
switch(j){
case 1:BT=BitTreeInit(BT); break;
case 2:printf("请输入二叉树(空格代表树的元素为空,最后输入空格键结束输入):\n");
BT=BitTreeCreat(BT);break;
case 3:BitTreeEmpty(BT);break;
case 4:printf("先序遍历: ");
PreOrderTraverse(BT);printf("\n");break;
case 5:printf("中序遍历:");
InOrderTraverse(BT);printf("\n");break;
case 6: printf("后序遍历:");
PostOrderTraverse(BT);printf("\n");break;
case 7:printf("层次遍历：");
BFSTraverse(BT);printf("\n");break;
case 8:printf("该树的深度是%d\n",BitTreeDepth(BT));break;
case 9:BitCountleaf(BT,&count);
printf("二叉树的叶子节点个数为:%d\n",count);break;
case 0:BitTreeClear(BT);break;
return 0;
}
}
}
------解决思路----------------------
仅供参考：
#include <iostream>
#include <stack>
#include <queue>
#include <locale.h>
using namespace std;
typedef struct BiTNode {//二叉树结点
char data; //数据
struct BiTNode *lchild,*rchild; //左右孩子指针
} BiTNode,*BiTree;
int CreateBiTree(BiTree &T) {//按先序序列创建二叉树
char data;
scanf("%c",&data);//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
if (data == '#') {
T = NULL;
} else {
T = (BiTree)malloc(sizeof(BiTNode));
T->data = data; //生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return 0;
}
void Visit(BiTree T) {//输出
if (T->data != '#') {
printf("%c ",T->data);
}
}
void PreOrder(BiTree T) {//先序遍历
if (T != NULL) {
Visit(T); //访问根节点
PreOrder(T->lchild); //访问左子结点
PreOrder(T->rchild); //访问右子结点
}
}
void InOrder(BiTree T) {//中序遍历
if (T != NULL) {
InOrder(T->lchild); //访问左子结点
Visit(T); //访问根节点
InOrder(T->rchild); //访问右子结点
}
}
void PostOrder(BiTree T) {//后序遍历
if (T != NULL) {
PostOrder(T->lchild); //访问左子结点
PostOrder(T->rchild); //访问右子结点
Visit(T); //访问根节点
}
}
void PreOrder2(BiTree T) {//先序遍历(非递归)
//访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
stack<BiTree> stack;
BiTree p = T;//p是遍历指针
while (p
------解决思路----------------------
!stack.empty()) { //栈不空或者p不空时循环
if (p != NULL) {
stack.push(p); //存入栈中
printf("%c ",p->data); //访问根节点
p = p->lchild; //遍历左子树
} else {
p = stack.top(); //退栈
stack.pop();
p = p->rchild; //访问右子树
}
}
}
void InOrder2(BiTree T) {//中序遍历(非递归)
//T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
//先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
stack<BiTree> stack;
BiTree p = T;//p是遍历指针
while (p
------解决思路----------------------
!stack.empty()) { //栈不空或者p不空时循环
if (p != NULL) {
stack.push(p); //存入栈中
p = p->lchild; //遍历左子树
} else {
p = stack.top(); //退栈，访问根节点
printf("%c ",p->data);
stack.pop();
p = p->rchild; //访问右子树
}
}
}
typedef struct BiTNodePost{
BiTree biTree;
char tag;
} BiTNodePost,*BiTreePost;
void PostOrder2(BiTree T) {//后序遍历(非递归)
stack<BiTreePost> stack;
BiTree p = T;//p是遍历指针
BiTreePost BT;
while (p != NULL
------解决思路----------------------
!stack.empty()) {//栈不空或者p不空时循环
while (p != NULL) {//遍历左子树
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
BT->tag = 'L';//访问过左子树
stack.push(BT);
p = p->lchild;
}
while (!stack.empty() && (stack.top())->tag == 'R') {//左右子树访问完毕访问根节点
BT = stack.top();
stack.pop();//退栈
printf("%c ",BT->biTree->data);
}
if (!stack.empty()) {//遍历右子树
BT = stack.top();
BT->tag = 'R';//访问过右子树
p = BT->biTree;
p = p->rchild;
}
}
}
void LevelOrder(BiTree T) {//层次遍历
if (T == NULL) return;
BiTree p = T;
queue<BiTree> queue;//队列
queue.push(p);//根节点入队
while (!queue.empty()) { //队列不空循环
p = queue.front(); //对头元素出队
printf("%c ",p->data); //访问p指向的结点
queue.pop(); //退出队列
if (p->lchild != NULL) {//左子树不空，将左子树入队
queue.push(p->lchild);
}
if (p->rchild != NULL) {//右子树不空，将右子树入队
queue.push(p->rchild);
}
}
}
int main() {
BiTree T;
setlocale(LC_ALL,"chs");
CreateBiTree(T);
printf("先序遍历 ：");PreOrder (T);printf("\n");
printf("先序遍历(非递归)：");PreOrder2 (T);printf("\n");
printf("\n");
printf("中序遍历 ：");InOrder (T);printf("\n");
printf("中序遍历(非递归)：");InOrder2 (T);printf("\n");
printf("\n");
printf("后序遍历 ：");PostOrder (T);printf("\n");
printf("后序遍历(非递归)：");PostOrder2(T);printf("\n");
printf("\n");
printf("层次遍历 ：");LevelOrder(T);printf("\n");
return 0;
}
//ABC##DE#G##F###
//先序遍历 ：A B C D E G F
//先序遍历(非递归)：A B C D E G F
//
//中序遍历 ：C B E G D F A
//中序遍历(非递归)：C B E G D F A
//
//后序遍历 ：C G E F D B A
//后序遍历(非递归)：C G E F D B A
//
//层次遍历 ：A B C D E F G
//
/// A
/// /
/// B
/// / \
/// C D
/// / \
/// E F
/// \
/// G
------解决思路----------------------
修改如下：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW -1
typedef char TElemType;
typedef struct BitNode
{
TElemType data;
struct BitNode *lchild, *rchild;
}BitNode, *BitTree;
typedef struct QNode
{
BitNode data;
struct QNode *next;
}QNode, *Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}LinkQueue;
//初始化，就是建一棵空树？
BitTree BitTreeInit(BitTree *pBT)
{
//BT = (BitTree)malloc(sizeof(BitNode));
*pBT = NULL;
return *pBT;
}
BitTree BitTreeCreat(BitTree *pBT)
{
char c;
scanf("%c", &c);
getchar(); //zx 读入回车
if (c == ' ') *pBT = NULL;
else
{
if (!(*pBT = (BitTree)malloc(sizeof(BitNode))))
exit(OVERFLOW);
(*pBT)->data = c;
printf("%c的左节点：", c);
BitTreeCreat(&((*pBT)->lchild));
printf("%c的右节点：", c);
BitTreeCreat(&((*pBT)->rchild));
}
return *pBT;
}
void BitTreeEmpty(BitTree BT)
{
if (!BT) printf("树为空!\n");
else printf("树非空!\n");
}
void visit(BitTree BT)
{
printf("%c", BT->data);
}
void PreOrderTraverse(BitTree BT)
{
if (BT)
{
visit(BT);
PreOrderTraverse(BT->lchild);
PreOrderTraverse(BT->rchild);
}
}
void InOrderTraverse(BitTree BT)
{
if (BT)
{
InOrderTraverse(BT->lchild);
visit(BT);
InOrderTraverse(BT->rchild);
}
}
void PostOrderTraverse(BitTree BT)
{
if (BT)
{
PostOrderTraverse(BT->lchild);
PostOrderTraverse(BT->rchild);
visit(BT);
}
}
void InitQueue(LinkQueue *Q)
{
Q->front = Q->rear = (Queueptr)malloc(sizeof(QNode)); //zx 队头、队尾指向同一节点？
if (!Q->front) exit(OVERFLOW);
Q->front->next = NULL;
}
int QueueEmpty(LinkQueue *Q)
{
if (Q->front == Q->rear) return 1;//是==不是=
else return 0;
}
void EnQueue(LinkQueue *Q, BitNode e)
{
QNode *p;
p = (Queueptr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
void DeQueue(LinkQueue *Q, BitTree e)
{
QNode *p;
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) Q->rear = Q->front;
free(p);
}
//广度优先遍历
void BFSTraverse(BitTree BT)
{
BitNode m;
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q, *BT);
while (!QueueEmpty(&Q))
{
DeQueue(&Q, &m);
visit(&m);
if (m.lchild) EnQueue(&Q, *(m.lchild));
if (m.rchild) EnQueue(&Q, *(m.rchild));
}
}
int BitTreeDepth(BitTree BT) //求树的深度
{
int dep1, dep2;
if (BT == NULL) return 0;
else
{
dep1 = BitTreeDepth(BT->lchild);
dep2 = BitTreeDepth(BT->rchild);
if (dep1 > dep2) return dep1 + 1;
else return dep2 + 1;
}
}
void BitCountleaf(BitTree BT, int *count)
{
if (BT)
{
if (!BT->lchild && !BT->rchild)
(*count)++;
BitCountleaf(BT->lchild, count);
BitCountleaf(BT->rchild, count);
}
}
void BitTreeClear(BitTree BT)
{
if (BT)
{
BitTreeClear(BT->lchild);
BitTreeClear(BT->rchild);
free(BT);
BT = NULL;
}
}
int main()
{
int i = 1, j, count = 0;
BitTree BT = NULL;
while (1) {
printf("-----------------欢迎使用-------------------\n");
printf("请选择要进行的操作\n");
printf("1.初始化一棵树 2.建立一棵树 3.判断树是否为空\n");
printf("4.按先序遍历树 5.按中序遍历树 6.按后序遍历树\n");
printf("7.按层次遍历树 8.求树的深度 9.求树的叶子节点个数\n");
printf("0.把树清空\n");
printf("-----------------感谢使用-------------------\n");
scanf("%d", &j);
getchar();
switch (j) {
case 1:BT = BitTreeInit(&BT); break;
case 2:printf("请输入二叉树(空格代表树的元素为空,最后输入空格键结束输入):\n");
BT = BitTreeCreat(&BT); break;
case 3:BitTreeEmpty(BT); break;
case 4:printf("先序遍历: ");
PreOrderTraverse(BT); printf("\n"); break;
case 5:printf("中序遍历:");
InOrderTraverse(BT); printf("\n"); break;
case 6: printf("后序遍历:");
PostOrderTraverse(BT); printf("\n"); break;
case 7:printf("层次遍历：");
BFSTraverse(BT); printf("\n"); break;
case 8:printf("该树的深度是%d\n", BitTreeDepth(BT)); break;
case 9:BitCountleaf(BT, &count);
printf("二叉树的叶子节点个数为:%d\n", count); break;
case 0:BitTreeClear(BT); break;
default: return 0; //zx
}
}
return 0;
}