实验3 二叉树的应用.docVIP

实验五：二叉树的应用 一、实验预备知识 1 树是一种非线性的结构，它具有递归特点。 2 二叉树有四种遍历方法，分别为：先根，后根、中根和层次。掌握四种遍历的规则。（每个结点都访问，并且只访问一次） 二、实验目的 1 掌握二叉树的逻辑结构特性，以及各种存储结构的特点及适用范围。 2 掌握用指针类型描述、访问和处理二叉树的各种运算的实现算法。 三、实验内容 1 编写采用二叉链表形式存储的二叉树的创建算法。 2 编写二叉树的先序、中序、后序遍历的递归算法、先序和中序的非递归算法和按层遍历的算法。 2 编写将一棵二叉树的所有左右子树进行交换的算法。 3 编写统计二叉树中叶子结点的算法。 4编写一个主函数，将上面函数连在一起，构成一个完整的程序。 5将实验源程序调试并运行。 四、实验要求 建立的二叉树为： #includeiostream using namespace std; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bintnode; typedef bintnode *bintree; typedef struct stack { bintree data[100]; int tag[100]; int top; }seqstack; 创建二叉树算法： void CreateBinTree(bintree *t) { char ch; if((ch=getchar())==0) (*t)=NULL; else { *t=new bintnode ; (*t)-data=ch; CreateBinTree((*t)-lchild); CreateBinTree((*t)-rchild); } } 前序遍历递归算法： void Preorder(bintree t) { if(t) { coutt-data ; Preorder(t-lchild); Preorder(t-rchild); } } 中序遍历递归算法： void Inorder(bintree t) { if(t) { Inorder(t-lchild); coutt-data ; Inorder(t-rchild); } } 后序遍历递归算法： void Postorder(bintree t) { if(t) { Postorder(t-lchild); Postorder(t-rchild); coutt-data ; } } void Push(seqstack *s,bintree t) { s-data[++s-top]=t; } bintree Pop(seqstack *s) { if(s-top!=-1) { s-top--; return (s-data[s-top+1]); } else return NULL; } 前序遍历非递归算法： void Preorder1(bintree t) { seqstack s; s.top=-1; while((t)||(s.top!=-1)) { while(t) { coutt-data ; s.top++; s.data[s.top]=t; t=t-lchild; } if(s.top-1) { t=Pop(s); t=t-rchild; } } } 中序遍历非递归算法： void Inorder1(bintree t) { seqstack s; s.top=-1; while((t!=NULL)||(s.top!=-1)) { while(t) { Push(s,t); t=t-lchild; } if(s.top!=-1) { t=Pop(s); coutt-data ; t-rchild; } } } 层次遍历算法： void Levelorder(bintree t) { bintree queue[100]; int front,rear; if(t==NULL) return; front=-1; rear=0; queue[rear]=t; while(front!=rear) { front++; coutqueue[front]-data ; if(queue[front]-lch