#include <cstdlib>
#include <cstdio>
#define MAXL 100
typedef int Elemtype ;
typedef struct
{
Elemtype e;
} Elem;
typedef struct BITree
{
Elem data;
struct BITree * lchild,*rchild;
} BITnode,*BTree;
void Createtree(BTree &T) //创建二叉树
{
Elemtype a;
scanf("%d",&a);
if (a == -1)
{
(T) = NULL;
}
else
{
(T) = (BTree)malloc(sizeof(BITnode));
if(!T)
{
exit(1);
}
(T)->data.e = a;
Createtree((T)->lchild);
Createtree((T)->rchild);
}
return ;
}
//前序遍历
void PreTravel(BTree T)
{
if(T)
{
printf(" %d",T->data.e);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
//中序遍历
void MidTravel(BTree T)
{
if(T)
{
MidTravel(T->lchild);
printf(" %d",T->data.e);
MidTravel(T->rchild);
}
}
//后序遍历
void PostTravel(BTree T)
{
if(T)
{
PostTravel(T->lchild);
PostTravel(T->rchild);
printf(" %d",T->data.e);
}
}
//递归计算叶子数
int Count_leaf(BTree T)
{
if (T == NULL)
{
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return Count_leaf(T->lchild) + Count_leaf(T->rchild);
}
}
///非递归计算叶子结点个数
///用栈存放节点 Not_Leaf_Count计算叶子结点个数
typedef struct
{
int top;
BTree MAXSIZE[MAXL];
} *Stack, Le_Node;
int Not_Count_Leaf(BTree T)
{
int Not_Leaf_Count = 0;
Stack s;
s = (Stack )malloc(sizeof(Le_Node));
s ->top =0;
while (T != NULL || s->top != 0)
{
if (T != NULL)
{
s->MAXSIZE[s->top] = T;
s->top ++;
T = T->lchild;
}
else
{ s->top --;
T = s->MAXSIZE[s->top];
if (T->lchild == NULL && T->rchild == NULL)
{
Not_Leaf_Count++;
}
T = T->rchild;
}
}
return Not_Leaf_Count;
}
//计算二叉树的高度
int Height_Bitree(BTree T)
{
int h1,h2;
if (T != NULL)
{
h1 = Height_Bitree(T->lchild);
h2 = Height_Bitree(T->rchild);
if (h1 > h2)
{
return h1+1;
}
else
{
return h2+1;
}
}
else
return 0;
}
//非递归计算二叉树高度
int Not_Height_Bitree(BTree T)
{
BTree Que[MAXL];
int hp = 0,dp = 0,rear = 0,tp = 1,lc = 1;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear++] = T;
}
while (rear != 0)
{
p = Que[--rear];//队头元素出队
hp ++; //为已访问的节点数
if (p->lchild != NULL)
{
Que[rear++] = p->lchild;
tp ++; //记录历史入队的节点数
}
if (p->rchild != NULL)
{
Que[rear++] = p->rchild;
tp ++;
}
if(hp == lc) //当hp = lc时，表明本层节点均已访问完
{
dp ++;
lc = tp;
}
}
return dp;
}
//按层次遍历
void Level_Travel(BTree T)
{
BTree Que[MAXL];
int front = 0,rear = 0;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear] = T;
rear = (rear+1)%MAXL;
}
while (front != rear)
{
p = Que[front];//队头元素出队
front = (front +1)% MAXL;
printf(" %d",p->data.e);
if (p->lchild != NULL)
{
Que[rear] = p->lchild;
rear = (rear + 1)%MAXL;
}
if (p->rchild != NULL)
{
Que[rear] = p->rchild;
rear = (rear+1)%MAXL;
}
}
return ;
}
//非递归先序遍历
void NPreTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top ;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
printf(" %d",p->data.e);
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
p = p->rchild;
}
}
}
}
//非递归中序遍历
void NMidTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
printf(" %d",p->data.e);
p = p->rchild;
}
}
}
}
//非递归后续遍历
typedef struct
{
BTree ptr;
int tag;
} stacknode;
void NPostTravel(BTree T)
{
stacknode s[MAXL];
stacknode x;
BTree p = T;
int top;
if (T != NULL)
{
top = 0;
p = T;
do
{
while (p != NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top ++;
p = p->lchild;
}
while (top > 0 && s[top-1].tag == 2)
{
x = s[--top];
p = x.ptr;
printf(" %d",p->data.e); //tag 为2 表示右子数访问完毕，故访问根节点
}
if (top > 0)
{
s[top-1].tag = 2; //遍历右子树
p = s[top-1].ptr->rchild;
}
}
while (top > 0);
}
}
void menu()
{
printf("----------------------------------------------\n\n");
printf("0:退出\n");
printf("1:创建二叉树\n");
printf("2:递归前序遍历\n3:非递归前序遍历\n");
printf("4:递归中序遍历\n5:非递归中序遍历\n");
printf("6:递归后续遍历\n7:非递归后续遍历\n");
printf("8:递归计算叶子数\n9:非递归计算叶子数\n");
printf("10:递归计算高度 \n11:非递归计算高度\n");
printf("12:按层次遍历\n");
printf("-----------------------------------------------\n");
return ;
}
int main()
{
BTree T = NULL;
int select ;
menu();
do
{
printf("输入您的选择：");
scanf("%d",&select);
switch (select)
{
case 0:
{
printf("退出\n");
break ;
}
case 1:
{
printf("创建二叉树\n");
printf("输入数据，以-1结束\n");
Createtree(T);
break;
}
case 2:
{
printf("递归前序遍历\n");
PreTravel(T);
break;
}
case 3:
{
printf("非递归前序遍历\n");
NPreTravel(T);
break;
}
case 4:
{
printf("递归中序遍历\n");
MidTravel(T);
break;
}
case 5:
{
printf("非递归中序遍历\n");
NMidTravel(T);
break;
}
case 6:
{
printf("递归后序遍历\n");
PostTravel(T);
break;
}
case 7:
{
printf("非递归后序遍历\n");
NPostTravel(T);
break ;
}
case 8:
{
printf("递归计算叶子数为：%d\n",Count_leaf(T));
break ;
}
case 9:
{
printf("非递归计算叶子数为：%d\n",Not_Count_Leaf(T));
break;
}
case 10:
{
printf("递归计算高度\n");
printf("高度为：%d\n",Height_Bitree(T));
break;
