算法思想(重点是递归的使用)
利用扩展先序遍历序列创建二叉链表
采用类似先序遍历的递归算法,首先读入当前根结点的数据,如果是'.'则将当前
树根置为空,否则申请一个新结点,存入当前根结点的数据,分别用当前根结点的
左子域和右子域进行递归调用,创建左、右子树.
Code
#include <stdio.h> #include <stdlib.h> typedef char DataType; //二叉链表结点的数据类型 typedef struct Node //定义二叉树的二叉链表结点结构 { DataType data; struct Node *LChild; //左子树 struct Node *RChild; //右子树 }BiTNode,*BiTree; void CreateBiTree(BiTree *bt); //创建二叉链表函数 void PreOrder(BiTree root); //先序遍历二叉树 void InOrder(BiTree root); //中序遍历二叉树 void PostOrder(BiTree root); //后序遍历二叉树 int main() { BiTree bt; int choice; while(true) { //二叉树操作选择菜单 printf("*****************Please enter your choice***************** "); printf(" choice 1:创建二叉树 "); printf(" choice 2:先序遍历二叉树 "); printf(" choice 3:中序遍历二叉树 "); printf(" choice 4:后序遍历二叉树 "); printf(" choice 0:退出 "); scanf("%d",&choice); switch(choice) { case 1: CreateBiTree(&bt); break; case 2: PreOrder(bt); printf(" "); break; case 3: InOrder(bt); printf(" "); break; case 4: PostOrder(bt); printf(" "); break; case 0: exit(0); break; default: printf("ERROR!! "); exit(0); break; } } return 0; } void CreateBiTree(BiTree *bt) { char ch; printf("Please enter data:"); getchar(); ch = getchar(); if(ch == '.') //读入的数据是'.'则将当前树根置为空 { *bt = NULL; } else //读入正常数据,为当前树根分配地址空间 { *bt = (BiTree)malloc(sizeof(BiTNode)); (*bt)->data = ch; CreateBiTree(&((*bt)->LChild)); //递归调用CreateBiTree()函数,处理左子树 CreateBiTree(&((*bt)->RChild)); //递归调用CreateBiTree()函数,处理右子树 } } void PreOrder(BiTree root) //先序遍历二叉树,root为指向二叉树根结点的指针 { if(root!=NULL) { printf("%c ",root->data); //访问根结点 PreOrder(root->LChild); //先序遍历左子树 PreOrder(root->RChild); //先序遍历右子树 } } void InOrder(BiTree root) //中序遍历二叉树,root为指向二叉树根结点的指针 { if(root!=NULL) { InOrder(root->LChild); //中序遍历左子树 printf("%c ",root->data); //访问根结点 InOrder(root->RChild); //中序遍历右子树 } } void PostOrder(BiTree root) //中序遍历二叉树,root为指向二叉树根结点的指针 { if(root!=NULL) { PostOrder(root->LChild); //后序遍历左子树 PostOrder(root->RChild); //后序遍历右子树 printf("%c ",root->data); //访问根结点 } }