数据结构实验报告三(2)

实验题目 姓名

第七章、树形结构 班级

小组合作 学 号

否

一、实验目的

7.1 实现二叉树的各种基本运算的算法 7.2 实现二叉树的各种遍历算法 7.3 求二叉树从根节点到叶子节点的路径 7.4 由遍历序列构造二叉树 7.5 实现中序线索化二叉树 7.6 构造哈夫曼树 7.7 用二叉树来表示代数表达式二.实验环境 安装了 Windows7 操作系统，并且安装了 Microsoft Visual C++ 6.0。

三、实验内容与步骤

7.1 实现二叉树的各种基本运算的算法【编写一个程序 exp7-1.cpp,实现二叉树的各种基本运算的算法。 (1) 输出二叉树 b (2) 输出 H 节点的左右孩子节点值 (3) 输出二叉树 b 的深度 (4) 输出二叉树 b 的宽度 (5) 输出二叉树 b 的节点个数 (6) 输出二叉树 b 的叶子节点个数 (7) 释放二叉树 b1 输入程序如下： ○ #include "stdafx.h" //文件名:exp7-1.cpp #include <stdio.h> #include"algo7-1.cpp" typedef char ElemType; //typedef struct node //{ // // // ElemType data; struct node *lchild; struct node *rchild; //数据元素 //指向左孩子 //指向右孩子

//} BTNode; //extern void CreateBTNode(BTNode *&b,char *str); //extern BTNode *FindNode(BTNode *b,ElemType x); //extern BTNode *LchildNode(BTNode *p); //extern BTNode *RchildNode(BTNode *p); //extern int BTNodeDepth(BTNode *b); //extern void DispBTNode(BTNode *b); //extern int BTWidth(BTNode *b); //extern int Nodes(BTNode *b); //extern int LeafNodes(BTNode *b); //extern void DestroyBTNode(BTNode *&b); void main()

{

BTNode *b,*p,*lp,*rp;; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树的基本运算如下:\n"); printf(" (1)输出二叉树:");DispBTNode(b);printf("\n"); printf(" (2)H 节点:"); p=FindNode(b,'H'); if (p!=NULL) { lp=LchildNode(p); if (lp!=NULL) printf("左孩子为%c ",lp->data); else printf("无左孩子 "); rp=RchildNode(p); if (rp!=NULL) printf("右孩子为%c",rp->data); else printf("无右孩子 "); } printf("\n"); printf(" (3)二叉树 b 的深度:%d\n",BTNodeDepth(b)); printf(" (4)二叉树 b 的宽度:%d\n",BTWidth(b)); printf(" (5)二叉树 b 的节点个数:%d\n",Nodes(b)); printf(" (6)二叉树 b 的叶子节点个数:%d\n",LeafNodes(b)); printf(" (7)释放二叉树 b\n"); DestroyBTNode(b);

}

2 输入程序并运行，如图 ○

7.2 实现二叉树的各种遍历算法编写一个程序 exp7-2.cpp,实现二叉树的各种遍历算法。 1 输入程序如下： ○#include "stdafx.h" //文件名:exp7-2.cpp #include <stdio.h> #include "algo7-1.cpp" #include <malloc.h> #define MaxSize 100 typedef char ElemType; void PreOrder(BTNode *b) //先序遍历的递归算法 { if (b!=NULL) { printf("

%c ",b->data); //访问根节点 PreOrder(b->lchild); //递归访问左子树 PreOrder(b->rchild); //递归访问右子树 } } void PreOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if (b!=NULL) { top++; //根节点入栈 St[top]=b; while (top>-1) //栈不为空时循环 { p=St[top]; //退栈并访问该节点 top--; printf("%c ",p->data); if (p->rchild!=NULL) //右孩子入栈 { top++; St[top]=p->rchild; } if (p->lchild!=NULL) //左孩子入栈 { top++; St[top]=p->lchild; } } printf("\n"); } } void InOrder(BTNode *b) //中序遍历的递归算法 { if (b!=NULL) { InOrder(b->lchild); //递归访问左子树 printf("%c ",b->data); //访问根节点

InOrder(b->rchild); }

//递归访问右子树

} void InOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if (b!=NULL) { p=b; while (top>-1 || p!=NULL) { while (p!=NULL) { top++; St[top]=p; p=p->lchild; } if (top>-1) { p=St[top]; top--; printf("%c ",p->data); p=p->rchild; } } printf("\n"); } } void PostOrder(BTNode *b) //后序遍历的递归算法 { if (b!=NULL) { PostOrder(b->lchild); //递归访问左子树 PostOrder(b->rchild); //递归访问右子树 printf("%c ",b->data); //访问根节点 } } void PostOrder1(BTNode *b) { BTNode *St[MaxSize]; BTNode *p; int flag,top=-1; //栈指针置初值 if (b!=NULL) { do { while (b!=NULL) //将 t 的所有左节点入栈 { top++; St[top]=b; b=b->lchild; } p=NULL; //p 指向当前节点的前一 个已访问的节点 flag=1;

while (top!=-1 && flag) { b=St[top]; if (b->rchild==p) { printf("%c ",b->data); top--; p=b; } else { b=b->rchild; flag=0; } } } while (top!=-1); printf("\n");

//取出当前的栈顶元素 //右子树不存在或已被访问,访问之 //访问*b 节点 //p 指向则被访问的节点

//t 指向右子树

} } void TravLevel(BTNode *b) { BTNode *Qu[MaxSize]; //定义循环队列 int front,rear; //定义队首和队尾指针 front=rear=0; //置队列为空队列 if (b!=NULL) printf("%c ",b->data); rear++; //节点指针进入队列 Qu[rear]=b; while (rear!=front) //队列不为空 { front=(front+1)%MaxSize; b=Qu[front]; //队头出队列 if (b->lchild!=NULL) //输出左孩子,并入队列 { printf("%c ",b->lchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->lchild; } if (b->rchild!=NULL) //输出右孩子,并入队列 { printf("%c ",b->rchild->data); rear=(rear+1)%MaxSize; Qu[rear]=b->rchild; } } printf("\n"); } void main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树 b:");DispBTNode(b);printf("\n"); printf("层次遍历序列:"); TravLevel(b); printf("先序遍历序列:\n");

printf(" 递归算法:");PreOrder(b);printf("\n" …… 此处隐藏：12501字，全部文档内容请下载后查看。喜欢就下载吧 ……