/*
2012年12月9日21:29:35
输入节点建立二叉树,
遍历递归的先中後序,
非递归的先中後序,
计算出深度
结点数
*/
# include <stdio.h>
# include <stdlib.h>
typedef char TElemType;
TElemType Nil = ' ';//字符型以空格符为空
# define form "%c"//输入输出的格式为%c
typedef struct BiTNode
{
TElemType data;
BiTNode * lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//操作结果:构造空的二叉树T
void InitBiTree(BiTree * T)
{
* T = NULL;
}
//按先序次序输入二叉树中结点的值(可为字符型或整型)
//构造二叉链表表示的二叉树T,变量Nil表示空(子)树
void CreateBiTree(BiTree * T)
{
TElemType ch;
scanf(form,&ch);
if (ch == Nil)//空
* T = NULL;
else
{
* T = (BiTree)malloc(sizeof(BiTNode));//生成根结点
if (! T)
exit(-1);
(* T)->data = ch;
CreateBiTree(&(* T)->lchild);//构造左子树
CreateBiTree(&(* T)->rchild);//构造右子树
}
}
//初始条件:二叉树T存在,Visit是对结点操作的应用函数
//操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
void PreOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)//T不空
{
Visit(T->data);//先访问根结点
PreOrderTraverse(T->lchild,Visit);//再先序遍历左子树
PreOrderTraverse(T->rchild,Visit);//最后先序遍历右子树
}
}
//初始条件:二叉树T存在,Visit是对结点操作的应用函数
//操作结果:中序遍历T,对每个结点调用函数Visit一次且仅一次
void InOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)
{
InOrderTraverse(T->lchild,Visit);//先中序遍历左子树
Visit(T->data);//再访问根结点
InOrderTraverse(T->rchild,Visit);//最后中序遍历右子树
}
}
//初始条件:二叉树T存在,Visit是对结点操作的应用函数
//操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
void PostOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)//T不空
{
PostOrderTraverse(T->lchild,Visit);//先后序遍历左子树
PostOrderTraverse(T->rchild,Visit);//再后序遍历左子树
Visit(T->data);//最后访问根结点
}
}
//先序非递归
void PreOrder(BiTNode* b)
{
BiTNode *stack[100], *p;
int top = -1;
if (b != NULL)
{
top++;
stack[top] = b;
while (top > -1)
{
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;
}
}
printf("\n");
}
}
//非递归中序
void InOrder(BiTNode* b)
{
BiTNode *stack[100], *p;
int top = -1;
if (b != NULL)
{
p = b;
while (top > -1 || p != NULL)
{
while (p != NULL)
{
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1)
{
p = stack[top];
top--;
printf("%c ", p->data);
p = p->rchild;
}
}
}
printf("\n");
}
//非递归后序
void PostOrder(BiTNode * b)
{
BiTNode *stack[100], * p;
int sign, top = -1;
if (b != NULL)
{
do
{
while (b != NULL)
{
top++;
stack[top] = b;
b = b->lchild;
}
p = NULL;
sign = 1;
while (top != -1 && sign)
{
b = stack[top];
if (b->rchild == p)
{
printf("%c ", b->data);
top--;
p = b;
}
else
{
b = b->rchild;
sign = 0;
}
}
}
while (top != -1);
printf("\n");
}
}
//初始条件:二叉树T存在
//操作结果:返回T的深度
int BiTreeDepth(BiTree T)
{
int i,j;
if (! T)
{
return 0;//空树的深度为0
}
if (T->lchild)
{
i = BiTreeDepth(T->lchild);//i为左子树的深度
}
else
{
i = 0;
}
if (T->rchild)
{
j = BiTreeDepth(T->rchild);//j为右子树的深度
}
else
{
j = 0;
}
return i > j ? i+1 : j+1;//T的深度为其左右子树的深度中的大者加1
}
//统计结点个数
int Node_Count(BiTree t)
{
if(t == NULL)
return 0;
int left=0,right=0;
if(t->lchild != NULL)
left = Node_Count(t->lchild);
if(t->rchild != NULL)
right = Node_Count(t->rchild);
return left+right+1;
}
void visitT(TElemType e)
{
printf(form" ",e);
}
int main(void)
{
BiTree T;
InitBiTree(&T);
printf("请先序输入二叉树(如:ab三个空格表示a为根节点,b为左子树的二叉树)\n");
CreateBiTree(&T);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visitT);
printf("\n先序非递归遍历二叉树:\n");
PreOrder(T);
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visitT);
printf("\n中序非递归遍历二叉树:\n");
InOrder(T);
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visitT);
printf("\n后序非递归遍历二叉树:\n");
PostOrder(T);
printf("\n二叉树的深度是%d\n",BiTreeDepth(T));
printf("\n二叉树的结点个数是%d\n",Node_Count(T));
printf("\n");
return 0;
}
/*
结果:
------------------------
请先序输入二叉树(如:ab三个空格表示a为根节点,b为左子树的二叉树)
ab c
先序递归遍历二叉树:
a b c
先序非递归遍历二叉树:
a b c
中序递归遍历二叉树:
b a c
中序非递归遍历二叉树:
b a c
后序递归遍历二叉树:
b c a
后序非递归遍历二叉树:
b c a
二叉树的深度是2
二叉树的结点个数是3
Press any key to continue
------------------------------
*/
二叉树的操作--递归非递归遍历、结点个数、树深度
5星 · 超过95%的资源 需积分: 38 188 浏览量
2012-12-10
10:28:12
上传
评论 1
收藏 2KB RAR 举报
_magnificence
- 粉丝: 8
- 资源: 4
最新资源
- STM32单片机FPGA毕设电路原理论文报告一种具有传统中医针刺补泻手法的新型智能电针仪设计
- 2023-04-06-项目笔记 - 第七十七阶段 - 4.4.2.75全局变量的作用域-75 -2024.03.19
- VuforiaObjectScanner-8-3-8.apk.1.1.1
- 上下班打卡_日报_20240201-20240319.xlsx
- 创业天下3.5.500.apk
- POD-data.mat
- ZF逆变器课程电子档及源码
- FileZilla-3.66.5-win64-sponsored2-setup
- SourceTreeSetup-3.4.17
- Docker Desktop Installer
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈