实验3 二叉树的应用.docx

1、实验3 二叉树的应用实验五：二叉树的应用一、实验预备知识 1 树是一种非线性的结构，它具有递归特点。 2 二叉树有四种遍历方法，分别为：先根，后根、中根和层次。掌握四种遍历的规则。（每个结点都访问，并且只访问一次）二、实验目的1 掌握二叉树的逻辑结构特性，以及各种存储结构的特点及适用范围。2 掌握用指针类型描述、访问和处理二叉树的各种运算的实现算法。三、实验内容1 编写采用二叉链表形式存储的二叉树的创建算法。2 编写二叉树的先序、中序、后序遍历的递归算法、先序和中序的非递归算法和按层遍历的算法。 2 编写将一棵二叉树的所有左右子树进行交换的算法。3 编写统计二叉树中叶子结点的算法。4编写一个主

2、函数，将上面函数连在一起，构成一个完整的程序。5将实验源程序调试并运行。四、实验要求建立的二叉树为： #includeusing namespace std;typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild;bintnode;typedef bintnode *bintree;typedef struct stack bintree data100; int tag100; int top;seqstack;创建二叉树算法：void CreateBinTree(bintree

3、 *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) coutdatalchild); Preorder(t-rchild); 中序遍历递归算法：void Inorder(bintree t) if(t) Inorder(t-lchild); coutdatarchild); 后序遍历递归算法：

4、void Postorder(bintree t) if(t) Postorder(t-lchild); Postorder(t-rchild); coutdatadata+s-top=t;bintree Pop(seqstack *s) if(s-top!=-1) s-top-; return (s-datas-top+1); else return NULL;前序遍历非递归算法：void Preorder1(bintree t) seqstack s; =-1; while(t)|!=-1) while(t) coutdatalchild; if-1) t=Pop(&s); t=t-rch

5、ild; 中序遍历非递归算法：void Inorder1(bintree t) seqstack s; =-1; while(t!=NULL)|!=-1) while(t) Push(&s,t); t=t-lchild; if!=-1) t=Pop(&s); coutdatarchild; 层次遍历算法：void Levelorder(bintree t) bintree queue100; int front,rear; if(t=NULL) return; front=-1; rear=0; queuerear=t; while(front!=rear) front+; coutdatal

6、child!=NULL) rear+; queuerear=queuefront-lchild; if(queuefront-rchild!=NULL) rear+; queuerear=queuefront-rchild; 遍历叶子节点算法：void CountLeaf(bintree t) if(!t) return; if(!(t-lchild|t-rchild) coutdatalchild); CountLeaf(t-rchild);交换左右子树算法：void SwapBinTree(bintree t) bintree s; if(t) SwapBinTree(t-lchild);

7、 SwapBinTree(t-rchild); s=t-lchild; t-lchild=t-rchild; t-rchild=s; 主函数实现：void main() bintree root; cout*endl; cout请按前序遍历次序顺序读入所要生成的二叉树：; CreateBinTree(&root); cout*endl; cout*endl; cout递归实现前序遍历结果：; Preorder(root); coutendl; coutn递归实现中序遍历结果：; Inorder(root); coutendl; coutn递归实现后序遍历结果：; Postorder(root)

8、; coutendl; cout*endl; cout*endl; cout非递归实现前序遍历结果：; Preorder1(root); coutendl; coutn非递归实现中序遍历结果：; Inorder(root); coutendl; coutn层次遍历结果：; Levelorder(root); coutendl; coutn叶子结点为：; CountLeaf(root); coutendl; cout*endl; cout*endl; printf(交换左右子树后遍历如下：); coutendl; SwapBinTree(root); coutn递归实现前序遍历结果：; Preorder(root); coutendl; coutn递归实现中序遍历结果：; Inorder(root); coutendl; coutn递归实现后序遍历结果：; Postorder(root); coutendl; cout*endl;5、实验结果：