数据结构二叉树遍历实验报告.doc

《数据结构二叉树遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.问题一：二叉树遍历1.问题描述设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##（#代表空子树）请编程完成下列任务：⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；⑵按层次遍历的方法来输出该二叉树按层次遍历的序列；⑶求该二叉树的高度。2.设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类

2、，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根

3、节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。3．源程序12345678#include#include#include#defineElemTypecharstructBTreeNode{ElemTypedata;structBTreeNode*left;structBTreeNode*right;.

4、.910111213141516171819202122232425262728293031323334353637383940414243444546};voidCreateBTree(structBTreeNode**T){charch;scanf_s("%c",&ch);if(ch=='#')*T=NULL;else{(*T)=malloc(sizeof(structBTreeNode));(*T)->data=ch;CreateBTree(&((*T)->left));CreateBTree(&((*T)->rig

5、ht));}}voidPreorder(structBTreeNode*T){if(T!=NULL){printf("%c",T->data);Preorder(T->left);Preorder(T->right);}}voidInorder(structBTreeNode*T){if(T!=NULL){Inorder(T->left);printf("%c",T->data);Inorder(T->right);}}voidPostorder(structBTreeNode*T){if(T!=NULL){Postorder

6、(T->left);Postorder(T->right);printf("%c",T->data);}}voidLevelorder(structBTreeNode*BT)..4748495051525354555657585960616263646566676869707172737475767778798081828384{structBTreeNode*p;structBTreeNode*q[30];intfront=0,rear=0;if(BT!=NULL){rear=(rear+1)%30;q[rear]=BT;}

7、while(front!=rear){front=(front+1)%30;p=q[front];printf("%c",p->data);if(p->left!=NULL){rear=(rear+1)%30;q[rear]=p->left;}if(p->right!=NULL){rear=(rear+1)%30;q[rear]=p->right;}}}intgetHeight(structBTreeNode*T){intlh,rh;if(T==NULL)return0;lh=getHeight(T->left);rh=get

8、Height(T->right);returnlh>rh?lh+1:rh+1;}voidmain(void){structBTreeNode*T;CreateBTree(&T);printf("前序序列：");Preorder(T);printf("");printf