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

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

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

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

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

4、Node氺right;}；voidCreateBTree(structBTreeNode氺氺T){charch;scanf_s(，z%c，z,&ch);if(ch==’#’)*T=NULL;else{(*T)=malloc(sizeof(structBTreeNode));(*T)->data=ch;CreateBTree(&((*T)->left));CreateBTree(&((*T)->right));}}voidPreorder(structBTreeNode氺T){if(T!=NULL){printf(

5、〃%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(T->left);Postorder(T->right);printf(〃％c〃，T->data);vo

6、idLcvclordcr(structBTreeNode*BT)structBTreeNode氺p;structBTreeNode*q[30];intfront=0,rear=0;if(BT!=NULL){rear=(rear+l)%30;q[rear]=BT;}while(front!=rear){front=(front+l)%30;p=q[front];printf(z，%c〃,p-〉data);if(p->left!=NULL){rear=(rear+l)%30;q[rear]=p->left;}if(p->

7、right!=NULL){rear=(rear+l)%30;q[rear]=p->right;}}}intgetlleight(structBTreeNode氺T){intlh,rh;if(T==NULL)return0;lh=getHeight(T->left);rh=getHeight(T~>right);returnlh>rh?lh+1:rh+1;}voidmain(void){structBTreeNode*T;CreateBTree(&T);printf("前序序列:〃)；Preorder(T);pri

8、ntf(，，，z);printf("中序序列:");85Inorder(T);86printf(，z，z);87printf（〃后序序列："）;88Postorder(T);89printf(zz/z);90printf（"层次遍历序列："）;91Levelorder(T);92printf(/z/z);93prin