二叉链表为存储结构,实现二叉树的创建、遍历 |
您所在的位置:网站首页 › abcdefg大写字母表 › 二叉链表为存储结构,实现二叉树的创建、遍历 |
【问题描述】 以二叉链表为存储结构,实现二叉树的创建、遍历 实验要求:在程序中定义下述函数,并实现要求的函数功能: CreateTree():按从键盘输入的扩展前序序列,创建二叉树 PreOrderTree():前序遍历树(递归) InOrderTree():中序(非递归)遍历树 LaOrderTree(): 后序遍历树(递归) 【输入形式】 以扩展二叉树的前序遍历序列作为输入,创建二叉树。 【输出形式】 输出前、中、后序遍历结果 【样例输入】 AB#D##C## 【样例输出】 ABDC BDAC DBCA //链表为存储结构,实现二叉树的创建、遍历 #include #include #include //二叉树的存储结构;1个数据域,2个指针域 typedef char ElemType; typedef struct node{ ElemType data; struct node *lchild; struct node *rchild; }BiNode; typedef BiNode* BiTree; //创建二叉树 BiTree CreateTree(){ BiTree T; char x; scanf("%c",&x); if(x=='#') return T=NULL; if(x=='\n') return T; else{ T=(BiTree)malloc(sizeof(BiNode)); T->data=x; T->lchild=CreateTree(); T->rchild=CreateTree(); return T; } } //前序遍历 (递归) void PreOrderTree(BiTree T){ if(T==NULL) return; printf("%c",T->data); PreOrderTree(T->lchild); PreOrderTree(T->rchild); } //中序遍历 (非递归) void InOrderTree(BiTree T){ if(T==NULL) return; InOrderTree(T->lchild); printf("%c",T->data); InOrderTree(T->rchild); } //后序遍历 (递归) void LaOrderTree(BiTree T){ if(T==NULL) return; LaOrderTree(T->lchild); LaOrderTree(T->rchild); printf("%c",T->data); } int main(){ BiTree T; T=CreateTree(); //建立 PreOrderTree(T); //前序遍历输出 printf("\n"); InOrderTree(T); //中序遍历输出 printf("\n"); LaOrderTree(T); //后序遍历输出 return 0; } |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |