二叉树

内容

实现二叉树的创建算法与中序列遍历算法。步骤如下：

将二叉树模拟成完全二叉树，从根结点开始对所有结点进行编号，编号从1开始，在运行过程中输入结点对应的编号和值，最后以编号i=0，结点值x=’$’为循环结束条件；中序遍历已建立的二叉树，并输出遍历结果，中序遍历算法可选择递归和非递归方法。

实验代码

GOGOGO!!!

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<Stdlib.h>#include<memory.h>#define OK 1 //宏定义#define ERROR -1#define OVERFLOW -2#define MAXSIZE 100----------------------------------typedef int ElemType;typedef int Status; ----------------------------------typedef struct Node //结构体{ElemType data;struct Node *lch, *rch;int num;}TNode;typedef struct BiTree{TNode *root;}Tree;void test();Status Init_SqBiTree(Tree *T);//初始化二叉树Status Creat_SqBiTree(Tree *T); //顺序存储创建二叉树void InOder_Traverse(TNode *T); //中序递归遍历二叉树Status Init_SqBiTree(Tree *T){T->root=(TNode*)malloc((MAXSIZE+1)*sizeof(TNode));memset(T->root, 0, (MAXSIZE + 1)*sizeof(TNode));return OK;}Status Creat_SqBiTree(Tree *T){int len;int i = 0; //计算结点个数int num;//结点编号ElemType e; //结点数据值while (1){printf("请输入结点位置:");scanf("%d", &num);fflush(stdin);printf("请输入当前节点的数据:");scanf("%d",&e);fflush(stdin);if (num == 0 || e == '$')break;T->root[i+1].num=num;T->root[i+1].data = e;i++;}len = i;for (i = 1; 2 * i <= len; i++){T->root[i].lch = &(T->root[2 * i]);}for (i = 1; (2 * i +1)<= len; i++){T->root[i].rch = &(T->root[2 * i+1]);}return OK;}void InOder_Traverse(TNode *T){if (T!=NULL){InOder_Traverse(T->lch);printf(" %d ",T->data);InOder_Traverse(T->rch);}}int main(){//test();Tree T;Init_SqBiTree(&T);Creat_SqBiTree(&T);printf("中序递归遍历：");InOder_Traverse(T.root + 1);printf("\n");return 0;}void test(){Tree T;Init_SqBiTree(&T);Creat_SqBiTree(&T);InOder_Traverse(T.root+1);}

实现结果

顺序存储一个二叉树序列：

中序递归遍历该序列：

运行结果：

总结

日有所获！！！！！！！！！！！！