柴伦洋作业数据结构三.doc

《柴伦洋作业数据结构三.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构（三）树和二叉树1、实验目的（1）熟悉二叉树结点的结构。（2）掌握对二叉树基本操作的实现。（3）理解遍历的概念，会利用递归方法编写对二叉树结构进行遍历的算法。（4）理解二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。2、实验要求（1）二叉树的存储及基本操作的实现。（2）二叉树及线索二叉树的相关运算的实现。3、实验内容实验①创建并输出二叉树实验②二叉树遍历实验③线索二叉树及遍历实验结果与分析：#includeusingnamespacestd;classtree{public:tree(){lchild=NULL;

2、rchild=NULL;}chardata;classtree*lchild;classtree*rchild;};//树与二叉树的定义部分voidCreateBiTree(BiTree*T){TElemTypech;scanf("%d",&ch);if(ch==0)*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)->data=ch;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);}}StatusBiTreeIsEmp

3、ty(BiTreeT){if(T)returnFALSE;elsereturnTRUE;}intBiTreeDepth(BiTreeT){inti,j;if(!T)return0;if(T->lchild)i=BiTreeDepth(T->lchild);elsei=0;if(T->rchild)j=BiTreeDepth(T->rchild);elsej=0;returni>j?i+1:j+1;}TElemTypeRoot(BiTreeT){if(BiTreeIsEmpty(T))return0;elsereturnT->data;}TElemTypeValue(BiTreep

4、){returnp->data;}TElemTypeRightChild(BiTreeT,TElemTypee){BiTreea;if(T){a=Point(T,e);if(a&&a->rchild)returna->rchild->data;}return0;}TElemTypeLeftSibling(BiTreeT,TElemTypee){TElemTypea;BiTreep;if(T){a=Parent(T,e);p=Point(T,a);if(p->lchild&&p->rchild&&p->rchild->data==e)returnp->lchild->data;}r

5、eturn0;}右孩子节点的定义voidpreorder(tree*root)//这是递归实现{if(root!=NULL)根节点不为空{preorder(root->lchild);cout<data;preorder(root->rchild);}}classstack{public:tree*top,*base;};