数据结构实验二叉树的应用.docxVIP

数据结构实验二叉树的应用 数据结构实验二叉树的应用 1 掌握二叉树的逻辑结构特性，以及各种存储结构的特点及适用范围 2 掌握用指针来描述、访问和处理二叉树的各种运算的实现 1 编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序（递归和非递归算法）和按层遍历的算法。 创建的二叉树： （1）创建二叉树算法可参考书P137中的6.8.4节。 （2）创建算法的键盘输入序列为：A B D # # E G # # H # # C # F # # 2 编写一个主函数，将上面函数连在一起，构成一个完整的程序。 3 调试并运行实验源程序。 三、实验结果： #include #include #define StackMaxSize 100 typedef char Elemtype; //定义二叉树的存储结构体 typedef struct Btnode Elemtype data; Btnode *lchild; Btnode *rchild; }*BtTree; struct Stack Btnode *stack[StackMaxSize]; int top; void Initstack(Stack *s) s-top =-1; void Push(Stack *s,Btnode *elem) if(s-top ==StackMaxSize-1) exit(1); s-top++; s-stack [s-top ]=elem; Btnode * Pop(Stack *s,BtTree p) if(s-top ==-1) exit(1); p=s-stack[s-top ]; s-top --; return p; // 创建二叉树 void CreatBtTree(BtTree BT) char ch; cinch; if (ch==#) BT=NULL; BT=new Btnode; BT-data=ch; CreatBtTree(BT-lchild); CreatBtTree(BT-rchild); //先根遍历递归算法 void preOrdetBT(BtTree BT) coutdata ; preOrdetBT(BT-lchild); preOrdetBT(BT-rchild); //中根遍历递归算法 void InOrdetBT(BtTree BT) InOrdetBT(BT-lchild); coutdata; InOrdetBT(BT-rchild); //后根遍历递归算法 void PostOrdetBT(BtTree BT) PostOrdetBT(BT-lchild); PostOrdetBT(BT-rchild); coutdata; //先根遍历非递归算法 void Pre(BtTree BT) BtTree p; Stack *s; s=new Stack; Initstack(s); while((p!=NULL)||(s-top -1)) while (p!=NULL) coutdata ; Push(s,p); p=p-lchild ; Pop(s,p); p=p-rchild ; //中根遍历的非递归算法 void Midium(BtTree BT) BtTree p; Stack *s; s=new Stack; Initstack(s); while((p!=NULL)||(s-top -1)) while (p!=NULL) Push(s,p); p=p-lchild ; Pop(s,p); coutdata ; p=p-rchild ; //链表结点类型 struct Lnode Btnode *data; Lnode *next; struct Linkqueue Lnode *front; Lnode *rear; //队列的初始化