#include
#include
#define MAXL 100
typedef int Elemtype ;
typedef struct
{
Elemtype e;
} Elem;
typedef struct Bitree
{
Elem data;
struct Bitree * lchild,*rchild;
} BITnode,*Bitree;
Bitree T = NULL; ///全局变量
void Createtree(Bitree *T) //创建二叉树
{
Elemtype a;
scanf("%d",&a);
if (a == 0 )
{
*T = NULL;
}
else
{
*T = (Bitree)malloc(sizeof(BITnode));
if(!T)
{
exit(1);
}
(*T)->data.e = a;
Createtree(&(*T)->lchild);
Createtree(&(*T)->rchild);
}
return ;
}
//前序遍历
void PreTravel(Bitree T)
{
if(T)
{
printf(" %d",T->data.e);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
//中序遍历
void MidTravel(Bitree T)
{
if(T)
{
MidTravel(T->lchild);
printf(" %d",T->data.e);
MidTravel(T->rchild);
}
}
//后序遍历
void PostTravel(Bitree T)
{
if(T)
{
PostTravel(T->lchild);
PostTravel(T->rchild);
printf(" %d",T->data.e);
}
}
//递归计算叶子数
int Count_leaf(Bitree 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;
Bitree MAXSIZE[MAXL];
} *Stack, Le_Node;
int Not_Count_Leaf(Bitree 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(Bitree 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(Bitree T)
{
Bitree Que[MAXL];
int hp = 0,dp = 0,rear = 0,tp = 1,lc = 1;
Bitree 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(Bitree T)
{
Bitree Que[MAXL];
int front = 0,rear = 0;
Bitree 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 Not_PreTravel(Bitree T)
{
Bitree stack[MAXL];
Bitree 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 Not_MidTravel(Bitree T)
{
Bitree stack[MAXL];
Bitree 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
{
Bitree ptr;
int tag;
} stacknode;
void Not_PostTravel(Bitree T)
{
stacknode s[MAXL];
stacknode x;
Bitree 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:创建二叉树 12:按层次遍历\n");
printf("2:递归前序遍历 3：非递归前序遍历\n");
printf("4:递归中序遍历 5：非递归中序遍历\n");
printf("6:递归后续遍历 7：非递归后续遍历\n");
printf("8:递归计算叶子数 9: 非递归计算叶子数\n");
printf("10:递归计算高度 11：非递归计算高度\n");
printf("-----------------------------------------------\n");
return ;
}
int main()
{
int icase ;
menu();
do
{
printf("输入您的选择：");
scanf("%d",&icase);
switch (icase)
{
case 0:
{
printf("退出\n");
break ;
}
case 1:
{
printf("创建二叉树\n");
printf("输入数据，以0结束\n");
Createtree(&T);
break;
}
case 2:
{
printf("递归前序遍历\n");
PreTravel(T);
break;
}
case 3:
{
printf("非递归前序遍历\n");
Not_PreTravel(T);
break;
}
case 4:
{
printf("递归中序遍历\n");
MidTravel(T);
break;
}
case 5:
{
printf("非递归中序遍历\n");
Not_MidTravel(T);
break;
}
case 6:
{
printf("递归后序遍历\n");
PostTravel(T);
break;
}
case 7:
{
printf("非递归后序遍历\n");
Not_PostTravel(T);
break ;
}
case 8:
{
printf("递归计算叶子数\n");
printf("叶子树为：%d\n",Count_leaf(T));
break ;
}
case 9:
{
printf("非递归计算叶子数\n");
printf("叶子树为：%d\n",Not_Count_Leaf(T));
break;
}
case 10:
{
printf("递归计算高度\n");
printf("高度为：%d\n",Height_Bitree(T));
break;
}
case 11:
{
printf("非递归计算高度\n");
printf("高度为：%d\n",Not_Height_Bitree(T));
break;
}
case 12:
{
printf("按层次遍历二叉树\n");
Level_Travel(T);
break;
}
default :
;
}
}
while (icase);
printf("-------------欢迎-----------\n");
system("pause");
return 0;
}
前段时间写的，自己看 |
转播
