课程名： 数据结构
题 目： 树形数据结构实验（1） 班 级：
学 号： 姓 名： 评语： 成绩： 指导教师：
批阅时间： 年
一、目的与要求
1）熟练掌握二叉树的二叉链表表示创建算法与实现； 2）熟练掌握栈的前序、中序与后序递归遍历算法与实现；
3）熟练掌握前序、中序与后序遍历线索二叉树的基本算法与实现; 4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
5）认真书写实验报告,并按时提交。 二、实验内容或题目
1) 创建二叉树：广义表式创建与先序创建；
2) 遍历二叉树：先，中，后，层序遍历，广义表式遍历，凹凸式遍历； 3) 二叉树属性：深度，宽度，结点数，叶子结点数 4) 二叉树路径：叶子结点到根结点的路径； 5）二叉树线索：中序线索二叉树； 6）二叉树置空：清空二叉树。 三、实验步骤与源程序 1)头文件Btree.h
#include /**********************************对象--二叉数**************** ****************/ 第 0 页 typedef char ElemType; // 定义元素类型 #define MAXSIZE 100 // 确定二叉树的最大结点数 /******************************二 叉 数 的 结 点 类 定 义 ******************************/ class BTreeNode private: int ltag,rtag; // 线索标记 BTreeNode *left; // 左子树指针 BTreeNode *right; // 右子树指针 public: ElemType data; // 数据域 // 构造函数 BTreeNode() ltag=0; rtag=0; left=NULL; right=NULL; // 带参数初始化的构造函数 BTreeNode(ElemType item,int ltag1,int *left1,BTreeNode *right1) data=item; ltag=ltag1; rtag=rtag1; 第 1 页 rtag1,BTreeNode left=left1; right=right1; BTreeNode *&Left() // 返回结点的左孩子 return left; // 返回结点的右孩子 BTreeNode *&Right() return right; friend class BinaryTree; // 二叉树类为二叉树结点类的友元类 /*****************************************************************/ class BinaryTree private: BTreeNode *root; public: //构造函数.初始化二叉树为空 BinaryTree() { root=NULL; } // 判断二叉树是否为空 bool BTreeEmpty() { return root==NULL; } /****************************创建二叉数的相关成员函数***********************/ // 按照二叉树的广义表表示创建二叉树 void CreateBTree1(); // 递归创建二叉树,被函数CreateBTree1调用 第 2 页 二 叉 数 的 类 定 义 void Create1(BTreeNode *&BT); // 按一定次序输入二叉树中结点的值(一个字符),空格表示空树 void CreateBTree2(int make); // 递归先序创建二叉树,被函数CreateBTree2调用 void Greate2(BTreeNode*&BT,int mark); // 复制二叉树 void BTreeCopy(BTreeNode *&root,BTreeNode *&BT); /****************************遍历二叉数的相关成员***********************/ // 按任一种遍历次序输出二叉树中的所有结点 void TraverseBTree(int mark); // 用于遍历的递归函数,被函数TraverseBTree调用 void Traverse(BTreeNode *&BT,int mark); // 先序遍历的递归函数 void PreOrder(BTreeNode *&BT); // 先序遍历的非递归函数一 void PreOrder_N1(BTreeNode *&BT); // 先序遍历的非递归函数二 void PreOrder_N2(BTreeNode *&BT); // 中序遍历的递归函数 void InOrder(BTreeNode *&BT); // 中序遍历的非递归函数一 void InOrder_N1(BTreeNode *&BT); 第 3 页 函数// 中序遍历的非递归函数二 void InOrder_N2(BTreeNode *&BT); // 后序遍历的递归函数 void PostOrder(BTreeNode *&BT); // 后序遍历的非递归函数一 void PostOrder_N1(BTreeNode *&BT); // 后序遍历的递归函数 void PostOrder_N2(BTreeNode *&BT); // 层序遍历的非递归函数 void LayerOrder(BTreeNode *&BT); // 按照二叉树的广义表表示输出整个二叉树 void GPrintBTree(); // 广义表形式输出整个二叉树的递归函数,被函数Print调用 void GPrint(BTreeNode *&BT); // 以凹凸表示法输出二叉树 void OPrintTree(); /***************************************************************/ /****************计算二叉数深度,宽度,叶子,结点的相关成员函数****************/ // 求二叉树的深度 int BTreeDepth(); // 用于求二叉树深度的递归函数,被BTreeDepth调用 第 4 页 二 叉 树 的 属 性 int Depth(BTreeNode *&BT); // 求二叉树的宽度 int BTreeWidth(); // 求二叉树中所有结点数 int BTreeCount(); // 用于求二叉树所有结点数的递归函数,被函数BTreeCount调用 int Count(BTreeNode *&BT); // 求二叉树中所有叶子结点数 int BTreeLeafCount(); // 用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用 int LeafCount(BTreeNode *&BT); // 输出二叉树的所有叶子结点 void BTreeLeafPrint(); // 用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用 void LeafPrint(BTreeNode *&BT); /***********************二叉树中从根结点到叶子结点的路径相关函数****************/ // 输出从根结点到叶子结点的路径,以及最长路径 void BTreePath(); // 输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用 void PathLeaf(BTreeNode *&BT,ElemType path[],int pathlen); // 求最长路径的递归函数,被函数BTreePaht调用 第 5 页 void BTreeLongpath(BTreeNode *&BT,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen); // 非递归方法输出从根结点到叶子结点的路径 void BTreePath_N1(); // 返回data域为x的结点指针 void BTreeFind(ElemType x); // 返回data域为x的结点指针的递归函数,被函数BTreeFind调用 BTreeNode *FindNode(BTreeNode *&BT,ElemType x); /*****************************************************************/ // 线索化二叉树 void CreateThread(); // 中序线索化二叉树的递归函数,被函数CreateThread调用 void InOrderThread(BTreeNode *&BT,BTreeNode *&pre); // 中序线索化二叉树中实现中序遍历,被函数CreateThread调用 void ThInOrder(BTreeNode *&BT); /****************************销毁二叉数的相关成员函数***********************/ // 置空二叉树 void BTreeClear(); // 用于清除二叉树的递归函数,被函数BTreeClear与~BinaryTree调用 void Clear(BTreeNode *&BT); // 析构函数,清除二叉树 第 6 页 线 索 二 叉 树 ~BinaryTree(); /******************************创建二叉数的相关成员函数*************************/ // 按照二叉树的广义表表示创建二叉树 void BinaryTree::CreateBTree1() cout<<\"输入广义表形式的二叉树:\"< char ch; while((ch=getchar())!='#') switch(ch) case '(': top++; stack[top]=p; k=1; // 即将建立左结点 break; case ')': top--; break; 第 7 页 case ',': k=2; // 即将建立右结点 break; default: if(!(p=new BTreeNode)) cout<<\"\\n堆内存分配失败\\n\"; exit(1); p->data=ch; p->left=p->right=NULL; if(BT==NULL) // p指向二叉树的根结点,建立根结点 BT=p; else // 已经建立根结点 if(k==1) // 建立左结点 stack[top]->left=p; else // 建立右结点 stack[top]->right=p; }//switch(ch) }//while // 按一定次序输入二叉树中结点的值(一个字符),空格表示空树 void BinaryTree::CreateBTree2(int mark) switch(mark) case 1: puts(\"按先序输入二叉树:\"); 第 8 页 break; case 2: puts(\"按中序输入二叉树:\"); break; case 3: puts(\"按后序输入二叉树:\"); break; root=NULL; // 给树根指针置空 BTreeNode *&p=root; // 定义p为指向二叉树结点的指针 Greate2(p,mark); // 递归创建二叉树,被函数CreateBTree2调用 void BinaryTree::Greate2(BTreeNode *&BT,int mark) char ch; ch=getchar(); switch(mark) case 1: // 先序创建 if(ch==' ') BT=NULL; else if(!(BT=new BTreeNode)) cout<<\"\\n堆内存分配失败\\n\"; exit(1); BT->data=ch; 第 9 页 Greate2(BT->left,mark); Greate2(BT->right,mark); break; case 2: break; case 3: break; // 复制二叉树 void BinaryTree::BTreeCopy(BTreeNode *&root,BTreeNode *&BT) if(root) if(!(BT=new BTreeNode)) exit(1); BT->data=root->data; BTreeCopy(root->left,BT->left); BTreeCopy(root->right,BT->right); else BT=NULL; /*******************************遍历二叉数的相关成员函数************************/ // 按任一种遍历次序输出二叉树中的所有结点 void BinaryTree::TraverseBTree(int mark) srand(time(NULL)); // 产生随机种子数,用来选择相同顺序遍历的不同算法 第 10 页 Traverse(root,mark); cout< case 1: // 先序遍历 option=rand()%3+1; switch(option) // 随机选择一种先序算法 case 1: PreOrder(BT); break; case 2: PreOrder_N1(BT); break; case 3: PreOrder_N2(BT); break; break; case 2: // 中序遍历 option = rand()%3 + 1; switch(option) // 随机选择一种中序算法 case 1: 第 11 页 InOrder(BT); break; case 2: InOrder_N1(BT); break; case 3: InOrder_N2(BT); break; break; case 3: // 后序遍历 option=rand()%3+1; switch(option) // 随机选择一种先序算法 case 1: PostOrder(BT); break; case 2: PostOrder_N1(BT); break; case 3: PostOrder_N2(BT); break; break; case 4: // 层序遍历 第 12 页 LayerOrder(BT); break; default: cout<<\"mark的值无效!遍历失败!\"< void BinaryTree::PreOrder(BTreeNode *&BT) if(BT!=NULL) cout< // 先序遍历的非递归函数一 void BinaryTree::PreOrder_N1(BTreeNode *&BT) BTreeNode *p; struct BTreeNode *pt; int tag; }stack[MAXSIZE]; int top=-1; top++; stack[top].pt=BT; stack[top].tag=1; while(top>-1) // 栈不空时循环 if(stack[top].tag==1) // 不能直接访问 第 13 页 p=stack[top].pt; top--; if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历 top++; stack[top].pt=p->right; // 右孩子入栈 stack[top].tag=1; top++; stack[top].pt=p->left; // 左孩子入栈 stack[top].tag=1; top++; stack[top].pt=p; // 根结点入栈 stack[top].tag=0; // 可以直接访问 if(stack[top].tag==0) // 可以直接访问 cout< // 先序遍历的非递归函数二 void BinaryTree::PreOrder_N2(BTreeNode *&BT) BTreeNode *stack[MAXSIZE],*p; int top = -1; if(BT!=NULL) top++; // 根结点入栈 stack[top] = BT; while(top>-1) // 栈不空时循环 第 14 页 p=stack[top]; top--; cout< if(p->right != NULL) // 右孩子入栈 top++; stack[top] = p->right; if(p->left != NULL) // 左孩子入栈 top++; stack[top] = p->left; }//while }//if(root!=NULL) // 中序遍历的递归函数 void BinaryTree::InOrder(BTreeNode *&BT) if(BT!=NULL) InOrder(BT->left); cout< // 中序遍历的非递归函数一 void BinaryTree::InOrder_N1(BTreeNode *&BT) BTreeNode *p; struct BTreeNode *pt; int tag; 第 15 页 }stack[MAXSIZE]; int top = -1; top++; stack[top].pt = BT; stack[top].tag = 1; while(top>-1) // 栈不空时循环 if(stack[top].tag == 1) // 不能直接访问 p = stack[top].pt; top--; if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历 top++; stack[top].pt=p->right; // 右孩子入栈 stack[top].tag = 1; top++; stack[top].pt = p; // 根结点入栈 stack[top].tag = 0; // 可以直接访问 top++; stack[top].pt =p->left; // 左孩子入栈 stack[top].tag = 1; if(stack[top].tag == 0) // 可以直接访问 cout< // 中序遍历的非递归函数二 第 16 页 void BinaryTree::InOrder_N2(BTreeNode *&BT) BTreeNode *stack[MAXSIZE],*p; int top = -1; if(BT != NULL) p = BT; while(top > -1||p != NULL) while(p != NULL) // 所有左结点入栈 top++; stack[top] = p; p = p->left; if(top > -1) p = stack[top]; top--; cout< }//if // 后序遍历的递归函数 void BinaryTree::PostOrder(BTreeNode *&BT) if(BT!=NULL) PostOrder(BT->left); PostOrder(BT->right); cout< // 后序遍历的非递归函数一 第 17 页 void BinaryTree::PostOrder_N1(BTreeNode *&BT) BTreeNode *p; struct BTreeNode *pt; int tag; }stack[MAXSIZE]; int top = -1; top++; stack[top].pt = BT; stack[top].tag = 1; while(top>-1) // 栈不空时循环 if(stack[top].tag == 1) // 不能直接访问 p = stack[top].pt; top--; if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历 top++; stack[top].pt = p; // 根结点入栈 stack[top].tag = 0; // 可以直接访问 top++; stack[top].pt=p->right; // 右孩子入栈 stack[top].tag = 1; top++; stack[top].pt =p->left; // 左孩子入栈 第 18 页 stack[top].tag = 1; if(stack[top].tag == 0) // 可以直接访问 cout< // 后序遍历的非递归函数二 void BinaryTree::PostOrder_N2(BTreeNode *&BT) BTreeNode *stack[MAXSIZE],*p,*q; q=BT; int top = -1,flag; if(q != NULL) do while(q != NULL) // 所有左结点入栈 top++; stack[top] = q; q = q->left; p=NULL; // p指向当前结点的前一个已访问的结点 flag=1; // 设置q的访问标记为已访问过 while(top > -1&&flag) q = stack[top]; // 取出当前栈顶元素 if(q->right == p) // 当右孩子不存在或已被访问时,则访问 cout< p = q; // p指向刚被访问的结点 第 19 页 else q = q->right; // 指向右孩子 flag = 0; // 设置未被访问的标记 }while(top>-1); }//if // 层序遍历的非递归函数 void BinaryTree::LayerOrder(BTreeNode *&BT) BTreeNode *Queue[MAXSIZE]; // 定义存储二叉树结点指针的数组空间作为队列使用 int front=0,rear=0; // 定义队首指针与队尾指针,初始均置0表示空队 BTreeNode *p; if(BT!=NULL) rear=(rear+1)%MAXSIZE; // 后移队尾指针 Queue[rear]=BT; // 将树根结点指针进队 while(front!=rear) // 当队列非空时执行循环 front=(front+1)%MAXSIZE; // 后移队首指针 p=Queue[front]; // 删除队首结点的值 cout< if(p->left!=NULL) // 若结点存在左孩子,则左孩子结点指针进队 rear=(rear+1)%MAXSIZE; Queue[rear]=p->left; if(p->right!=NULL) // 若结点存在右孩子,则右孩子结点指针进队 rear=(rear+1)%MAXSIZE; 第 20 页 Queue[rear]=p->right; // 按照二叉树的广义表表示输出整个二叉树 void BinaryTree::GPrintBTree() GPrint(root); cout< return; // 树为空时返回 else // 否则执行如下操作 cout< cout<<'('; // 输出左括号 GPrint(BT->left); // 输出左子树 if(BT->right!=NULL) cout<<','; // 若右子树不为空则输出逗号分隔符 GPrint(BT->right); // 输出右子树 cout<<')'; // 输出右括号 // 以凹凸表示法输出二叉树 void BinaryTree::OPrintTree() cout< int level[MAXSIZE][2],top=-1,n,i,width=4; 第 21 页 int maxwidth=40; char type[20]; char *pre_type=type; if(root!=NULL) top++; // 根结点入栈 stack[top]=root; level[top][0]=width; level[top][1]=2; // 2表示是根 while(top>-1) p=stack[top]; // 退栈并凹入显示该结点值 n=level[top][0]; switch(level[top][1]) case 0: pre_type=\"左结点\"; break; case 1: pre_type=\"右结点\"; break; case 2: pre_type=\"根结点\"; for(i=1;i<=n;i++) // n为显示场宽,字符以右对齐显示 cout<<\" \"; cout<<\" \"< for(i=n+1;i<=maxwidth;i+=2) cout<<\"--\"; cout< top++; // 将右子树树根结点入栈 stack[top]=p->right; level[top][0]=n+width; // 显示场宽增加width level[top][1]=1; // 1表示右子树 if(p->left!=NULL) top++; // 将左子树树根结点入栈 stack[top]=p->left; level[top][0]=n+width; // 显示场宽增加width level[top][1]=0; // 0表示左子树 }//while }//if /******************计算二叉数深度,宽度,叶子,结点的相关成员函数******************/ // 求二叉树的深度 int BinaryTree::BTreeDepth() return Depth(root); // 用于求二叉树深度的递归函数,被BTreeDepth调用 int BinaryTree::Depth(BTreeNode *&BT) 第 23 页 if(BT==NULL) return 0; // 对于空树,返回0并结束递归 else int dep_left=Depth(BT->left); // 计算左子树的深度 int dep_right=Depth(BT->right); // 计算右子树的深度 if(dep_left>dep_right) // 返回树的深度 return dep_left+1; else return dep_right+1; // 求二叉树的宽度 int BinaryTree::BTreeWidth() struct Queue int layer; // 结点的层次编号 BTreeNode *p; // 结点指针 }Queue[MAXSIZE]; // 定义顺序队列,存储二叉数所有的结点 int front,rear; front=rear=0; int cur_layer; // 存储当前结点所在的层数 BTreeNode *q=root; if(q!=NULL) rear++; Queue[rear].p=q; // 根结点指针入队 Queue[rear].layer=1; // 根结点的层次编号为1 第 24 页 while(rear!=front) // while循环通过层次遍历求每个结点的层次 front++; q=Queue[front].p; // 队头出队 cur_layer=Queue[front].layer; // 当前结点所在的层数 if(q->left!=NULL) // 左孩子入队 rear++; Queue[rear].p=q->left; Queue[rear].layer=cur_layer+1; // 当前结点的孩子在该结点 的下一层 if(q->right!=NULL) // 右孩子入队 rear++; Queue[rear].p=q->right; Queue[rear].layer=cur_layer+1; // 当前结点的孩子在该结点 的下一层 }//while int max_layer=0,i=1,n; cur_layer=1; // 从第一层开始 while(i<=rear) // 通过比较相同层次的结点数求树的深度 n=0; while(i<=rear&&Queue[i].layer==cur_layer) n++; // n累计cur_lay层中的结点层次 i++; cur_layer=Queue[i].layer; // 取下一个层次,此时Queue[i]存放下 第 25 页 一个层次的第一个结点 if(n>max_layer) max_layer=n; // 将最大层的结点树赋给max return max_layer; else return 0; // 求二叉树中所有结点数 int BinaryTree::BTreeCount() return Count(root); // 用于求二叉树中所有结点数的递归函数,被函数BTreeCount调用 int BinaryTree::Count(BTreeNode *&BT) if(BT==NULL) return 0; else return Count(BT->left)+Count(BT->right)+1; // 求二叉树中所有叶子结点数 int BinaryTree::BTreeLeafCount() return LeafCount(root); // 用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用 int BinaryTree::LeafCount(BTreeNode *&BT) if(BT == NULL) return 0; 第 26 页 else if(BT->left==NULL&&BT->right==NULL) return 1; else return LeafCount(BT->left)+LeafCount(BT->right); // 输出二叉树的所有叶子结点 void BinaryTree::BTreeLeafPrint() LeafPrint(root); // 用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用 void BinaryTree::LeafPrint(BTreeNode *&BT) if(BT != NULL) if(BT->left == NULL && BT->right==NULL) cout<<\" \"< else LeafPrint(BT->left); LeafPrint(BT->right); // 返回data域为x的结点指针 void BinaryTree::BTreeFind(ElemType x) BTreeNode *p; p=FindNode(root,x); if(p!=NULL) cout<<\" \"< cout<<\" \"< // 返回data域为x的结点指针的递归函数,被函数BTreeFind调用 BTreeNode *BinaryTree::FindNode(BTreeNode *&BT,ElemType x) BTreeNode *p; if(BT==NULL) return NULL; else if(BT->data==x) return BT; else p=FindNode(BT->left,x); if(p!=NULL) return p; else return FindNode(BT->right,x); /***********************二叉树中从根结点到叶子结点的路径相关函数****************/ // 输出从根结点到叶子结点的路径,以及最长路径 void BinaryTree::BTreePath() int longpathlen=0; ElemType path[MAXSIZE],longpath[MAXSIZE]; PathLeaf(root,path,0); cout< for(int i=longpathlen-1;i>=0;i--) cout<<\" \"< if(BT->left==NULL&&BT->right==NULL) // BT为叶子结点 cout<<\"叶子结点\"< cout< path[pathlen]=BT->data; // 将当前结点放入路径中 pathlen++; // 路径长度加1 PathLeaf(BT->left,path,pathlen); // 递归扫描左子树 PathLeaf(BT->right,path,pathlen); // 递归扫描右子树 pathlen--; // 恢复环境 // 求最长路径的递归函数,被函数BTreePaht调用 void BinaryTree::BTreeLongpath(BTreeNode *&BT,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen) if(BT==NULL) 第 29 页 if(pathlen>longpathlen) // 若当前路径更长,将路径保存在longpath 中 for(int i=pathlen-1;i>=0;i--) longpath[i]=path[i]; longpathlen=pathlen; else path[pathlen]=BT->data; // 将当前结点放入路径中 pathlen++; // 路径长度加1 BTreeLongpath(BT->left,path,pathlen,longpath,longpathlen); 扫描左子树 BTreeLongpath(BT->right,path,pathlen,longpath,longpathlen); // 扫描右子树 pathlen--; // 恢复环境 // 非递归方法输出从根结点到叶子结点的路径 void BinaryTree::BTreePath_N1() BTreeNode *q=root; struct BTreeNode *pt; // 存放当前结点的指针 int parent; // 存放双亲结点在队列中的位置 }Queue[MAXSIZE]; int front,rear,p; front=rear=-1; rear++; 第 30 页 // Queue[rear].pt=q; // 根结点入队 Queue[rear].parent=-1; // 根结点没有双亲结点 while(front if(q->left==NULL&&q->right==NULL) // q为叶子结点 cout<<\"叶子结点\"< while(Queue[p].parent!=-1) // p指向根结点时退出循环 cout< p=Queue[p].parent; cout< Queue[rear].pt=q->left; Queue[rear].parent=front; if(q->right!=NULL) // 右孩子入队 rear++; Queue[rear].pt=q->right; Queue[rear].parent=front; }//while cout< 线 索 二 叉 第 31 页 树 ********************************/ // 线索化二叉树 void BinaryTree::CreateThread() BTreeNode *pre; BTreeNode *t_root; BTreeCopy(root,t_root); // 复制二叉树root给t_root BTreeNode *throot; // 二叉线索树的头结点指针 throot=new BTreeNode; // 创建二叉线索树头结点 throot->ltag=0; throot->rtag=1; throot->right=throot; if(root==NULL) throot->left=throot; // 空二叉树 else throot->left=t_root; pre=throot; // pre是p的前驱结点 InOrderThread(t_root,pre); // 中序线索化二叉树 pre->right=throot; // 最后处理,加入指向根结点的线索 pre->rtag=1; throot->right=pre; // 根结点右线索化 ThInOrder(throot); // 中序线索化二叉树中实现中序遍历 // 中序线索化二叉树的递归函数,被函数CreateThread调用 void BinaryTree::InOrderThread(BTreeNode *&BT,BTreeNode *&pre) 第 32 页 if(BT!=NULL) InOrderThread(BT->left,pre); // 左子树线索化 if(BT->left==NULL) // 前驱线索 BT->left=pre; // 建立当前结点的前驱线索 BT->ltag=1; else BT->ltag=0; if(pre->right==NULL) // 后续线索 pre->right=BT; // 建立前驱结点的后续线索 pre->rtag=1; else pre->rtag=0; pre=BT; InOrderThread(BT->right,pre); // 右子树线索化 // 中序线索化二叉树中实现中序遍历,被函数CreateThread调用 void BinaryTree::ThInOrder(BTreeNode *&BT) BTreeNode *p=BT->left; // p指向根结点 while(p!=BT) // 空树或遍历结束时,p==BT while(p->ltag==0) p=p->left; cout<<\" \"< p=p->right; 第 33 页 cout<<\" \"< p=p->right; cout< void BinaryTree::BTreeClear() Clear(root); // 析构函数,清除二叉树 BinaryTree::~BinaryTree() Clear(root); // 用于清除二叉树的递归函数 void BinaryTree::Clear(BTreeNode *&BT) if(BT!=NULL) // 当二叉树非空时进行如下操作 Clear(BT->left); // 删除左子树 Clear(BT->right); // 删除右子树 delete BT; // 删除根结点 BT=NULL; 2) 源文件Btree.cpp #include \"Btree.h\" int main(void) BinaryTree Btree; 第 34 页 char option; int flag=0; // 标志当前二叉树是否已经创建,初始化为0,即还没有创建 do cout<<\" 二叉树演示程序\\n\\n\"; if(flag==0) // 标志二叉树还没有创建 cout<<\"[1] 二叉树创建\"< cout<<\"[1] 二叉树创建＋\"< char option1; do if(flag==0) // 标志二叉树还没有创建 cout<<\"二叉树创建\"< else // 标志二叉树已经创建 cout<<\"二叉树创建＋\"< Btree.CreateBTree1(); flag=1; // 标志二叉树已经创建 cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '2': // 先序式输入 Btree.CreateBTree2(1); flag=1; // 标志二叉树已经创建 cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; 第 36 页 case '3': // 返回主菜单 break; default: cout<<\"您的选择超出范围,请重新选择\"< cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; }while(option1!='3'); break; case '2': // 二叉树遍历 char option2; do cout<<\"二叉树遍历\"< cin>>option2; cout< cout<<\"先序遍历: \"; Btree.TraverseBTree(1); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '2': // 中序遍历 cout<<\"中序遍历: \"; Btree.TraverseBTree(2); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '3': // 后序遍历 cout<<\"后序遍历: \"; Btree.TraverseBTree(3); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); 第 38 页 break; case '4': // 层序遍历 cout<<\"层序遍历: \"; Btree.TraverseBTree(4); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '5': // 广义表式遍历 cout<<\"广义表式遍历: \"; Btree.GPrintBTree(); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '6': // 凹凸式遍历 cout<<\"凹凸式遍历: \"; Btree.OPrintTree(); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '7': // 查找结点 第 39 页 cout<<\"请输入要查找的数据: \"; ElemType find; cin>>find; Btree.BTreeFind(find); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '8': // 返回主菜单 break; default: cout<<\"您的选择超出范围,请重新选择\"< cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; }while(option2!='8'); break; case '3': // 二叉树属性 char option3; do cout<<\"二叉树属性\"< cout<<\" \"<<\"[2] 返回主菜单\"< int temp; temp=Btree.BTreeDepth(); cout<<\"二叉树的深度: \"< break; default: cout<<\"您的选择超出范围,请重新选择\"< cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; }while(option3!='2'); break; case '4': // 二叉树路径 char option4; do cout<<\"二叉树属性\"< Btree.BTreePath(); cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); break; case '2': // 返回主菜单 第 42 页 break; default: cout<<\"您的选择超出范围,请重新选择\"< }while(option4!='2'); break; case '5': // 二叉树线索 char option4; do cout<<\"二叉树线索\"< cout<<\"中序线索化二叉树内中序遍历: \"; Btree.CreateThread(); cout<<\"\\npress any key to continue\"; 第 43 页 cin.get(); cin.get(); break; case '2': // 返回主菜单 break; default: cout<<\"您的选择超出范围,请重新选择\"< cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; }while(option4!='2'); break; case '6': // 二叉树置空 cout<<\"是否置空当前二叉树(Y/N): \"; char dtemp; cin>>dtemp; if(dtemp=='Y'||dtemp=='y') Btree.BTreeClear(); flag=0; // 标志二叉树还没有创建 cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); 第 44 页 cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; break; case '7': // 退出 cout<<\"是否退出(Y/N): \"; char temp; cin>>temp; if(temp=='Y'||temp=='y') option='~'; cout<<\"\\npress any key to continue\"; cin.get(); cin.get(); cout<<\"\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"; break; case '~': // 真正退出 break; default: cout<<\"您的选择超出范围,请重新选择\"< }while(option!='~'); return 0; 第 45 页 四、测试数据与实验结果 图1 创建二叉树：先序式输入二叉树 图2 遍历二叉树：先序遍历二叉树 图3遍历二叉树：中序遍历二叉树 图4 遍历二叉树：后序遍历二叉树 图5 遍历二叉树：层序遍历二叉树 图6 遍历二叉树：广义表式二叉树 图7 遍历二叉树：凹凸式遍历二叉树 图8 二叉树属性：深度，宽度，结点数，叶子数 图9二叉树路径：叶子结点到根结点的路径 图10二叉树线索：中序线索二叉树 五、结果分析与实验体会 1、与同学讨论中明白了二叉树的二叉链表表示创建算法与实现 2、在打程序的过程中掌握了栈的前序、中序与后序递归遍历算法与实现，以及前序、中序与后序 遍 线索二叉树的基本算法与实现 3、在这个实验中明白了.h与.cpp的不同。 第 46 页 因篇幅问题不能全部显示，请点此查看更多更全内容