| 数据结构实验6：C++实现二叉树类 | 您所在的位置：网站首页 › excel表减法公式输入值错误怎么办 › 数据结构实验6：C++实现二叉树类 |
数据结构实验6：C++实现二叉树类
|
实验6
学号： 姓名： 专业： 6.1 实验目的 掌握二叉树的动态链表存储结构及表示。 掌握二叉树的三种遍历算法（递归和非递归两类）。 运用二叉树三种遍历的方法求解有关问题。 6.2 实验要求按照C++面向对象方法编写二叉树类；二叉树的测试数据可用多种方式进行输入，如键盘输入、静态写入、文件读入等。//最难的是从文件把数据读进去！ 设计二叉树的二叉链表存储结构，编写算法实现下列问题的求解。 打印出二叉树的三种遍历序列。 设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 求二叉树的高度。 求二叉树的结点数。 求二叉树的叶子结点数。 求二叉树的度为2的结点数。 键盘输入一个元素x，求其父节点、兄弟结点、子结点的值，不存在时给出相应提示信息。对兄弟结点和孩子结点，存在时要明确指出是左兄弟、左孩子、右兄弟或右孩子。 键盘输入一个元素x，求其在树中的层次，不存在时给出相应提示信息。 将按顺序方式存储在数组中的二叉树转换为二叉链表形式。（数组中要扩展为完全二叉树）。 交换二叉树中每个结点的左右孩子指针的值。（即：左子树变为右子树，右子树变为左子树）。 （下面为选做实验，有兴趣的同学完成） 复制一棵二叉树T到T1。 输出二叉树从每个叶子结点到根结点的路径（经历的结点）。 对二叉链表表示的二叉树，按从上到下，从左到右打印结点值，即按层次打印。（提示：需要使用队列） 对二叉链表表示的二叉树，求2个结点最近的共同祖先。 实验测试数据基本要求： 求二叉树中一条最长的路径长度（边数），并输出路径上的个结点值。 实验测试数据基本要求： 6.3 实验数据要求自我编写测试样例，要求每个功能函数的测试样例不少于两组 6.4 运行结果截图及说明
图1 测试（1）、（2）、（3）、（4）、（5）、（6）
图2 测试（1）、（2）、（3）、（4）、（5）、（6）
图3 测试（1）、（2）、（3）、（4）、（5）、（6）
图4 测试（1）、（2）、（3）、（4）、（5）、（6）
图5 测试（1）、（2）、（3）、（4）、（5）、（6）
图6 测试（1）、（2）、（3）、（4）、（5）、（6）
图7 测试（1）、（2）、（3）、（4）、（5）、（6）
图8 测试（1）、（2）、（3）、（4）、（5）、（6）
图9 测试（1）、（2）、（3）、（4）、（5）、（6）
图10 测试（1）、（2）、（3）、（4）、（5）、（6）
图11 测试（1）、（2）、（3）、（4）、（5）、（6）
图12 测试（1）、（2）、（3）、（4）、（5）、（6）
图13 测试（1）、（2）、（3）、（4）、（5）、（6）
图14 测试（1）、（2）、（3）、（4）、（5）、（6）
图15 测试（1）、（2）、（3）、（4）、（5）、（6）
图16 测试（1）、（2）、（3）、（4）、（5）、（6）
图17 测试（1）、（2）、（3）、（4）、（5）、（6）
图18 测试（1）、（2）、（3）、（4）、（5）、（6）
图19 测试（1）、（2）、（3）、（4）、（5）、（6）
图20 测试（1）、（2）、（3）、（4）、（5）、（6）
图21 测试（1）、（2）、（3）、（4）、（5）、（6）
图22 测试（1）、（2）、（3）、（4）、（5）、（6）
图23 测试（1）、（2）、（3）、（4）、（5）、（6）
图24 测试（7）
图25 测试（7）
图26 测试（7）
图27 测试（7）
图28 测试（7）
图29 测试（7）
图30 测试（7）
图31 测试（8）
图32 测试（8）
图33 测试（9）
图34 测试（9）
图35 测试（10）
图36 测试（10）
图37 测试（11）
图38 测试（11）
图39 测试（12）
图40 测试（12）
图41 测试（13）
图42 测试（13）
图43 测试（14）
图44 测试（14）
图45 测试（15）
图46 测试（15）
6.5 附源代码 // stdafx.h : include file for standard system include files, // or project specific include files that are used frequently, but // are changed infrequently // #if !defined(AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_) #define AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include #include using namespace std; typedef char elementType; typedef int elementType1; typedef struct node { elementType data;//刚开始应该写成将data写成string或者直接将整个函数写成模板的，写完了最后测试时 //才发现现在的写法有诸多不便；但修改的话就又要重构一遍，懒得整了。 struct node *leftChild, *rightChild; }bitNode, *binTree; typedef struct charNode { //elementType data; bitNode *data;//the type must be bitNode* struct charNode *link; }CLNode, *CPNode; //typedef struct charNode //{ //elementType data; //struct charNode *leftChild, *rightChild; //}charBitNode, *charBinTree; // TODO: reference additional headers your program requires here //{{AFX_INSERT_LOCATION}} // Microsoft Visual C++ will insert additional declarations immediately before the previous line. #endif // !defined(AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_) // charLinkedQueue.h: interface for the charLinkedQueue class. // // #if !defined(AFX_CHARLINKEDQUEUE_H__13C2F642_81C0_4489_9CF2_3D58D8B48EA9__INCLUDED_) #define AFX_CHARLINKEDQUEUE_H__13C2F642_81C0_4489_9CF2_3D58D8B48EA9__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 //刚开始尝试写英文注释的，后面知难而退了；不过原来的英文注释我保留了 class charLinkedQueue { public: charLinkedQueue(); virtual ~charLinkedQueue(); bool emptyCharLinkedQueue(); //bool fullSeqCircleQueue(); bool enQueue( bitNode *value );//the type must be bitNode* bool deQueue( /*bitNode *value*/ ); bool getFront( bitNode *&value );//the type must be bitNode*& int length(); friend ostream &operatorrightChild =new bitNode ; tmp = BT->rightChild; tmp->data = Arr[ number * 2 + 2 ]; tmp->leftChild = NULL; tmp->rightChild = NULL; createNode( tmp, Arr, number * 2 + 2 ); } } bool _Binary_Tree::createBinaryTree( binTree &BT, elementType stringLine[100][3], int length, int &row ) { if (row >= length || length == 0 ) //strlen存数据的二维数组，nRow结点所在的位数，nlen结点的个数 return false; if ( row == 0 ) BT = BTree; else BT = new bitNode;//new下面是公用的，用if的目的是改变private里BTree里的值 BT->data = stringLine[row][0]; BT->leftChild = NULL; BT->rightChild = NULL; int nextRow = row; if ( stringLine[nextRow][1] == '1' ) { ++ row; createBinaryTree( BT->leftChild, stringLine, length, row ); } if ( stringLine[nextRow][2] == '1' ) { ++row; createBinaryTree( BT->rightChild, stringLine, length, row ); } return true; } bool _Binary_Tree::readFileToArray( elementType stringLine[100][3], int &length ) { FILE *fp; char str[100]; cout name; fp = fopen( name, "r" ); if (!fp) { cout leftChild, value ); bool flag = _exit( BT->leftChild, value ); //if(!index) if(!flag) //_exit( BT->leftChild, value ); _exit( BT->rightChild, value ); } binTree _Binary_Tree::getNodePoint() { //if( emptyBinaryTree() ) //{ //throw "Empty binary tree!Error in binTree _Binary_Tree::getNodePoint()!\n"; //return NULL; //} return (*this).BTree; } binTree _Binary_Tree::getNodePoint( binTree BT, elementType value ) { /* if(!BT) { return NULL; } else { if( BT->data == value ) return BT; else { bitNode *tmp; if( tmp = getNodePoint( BT->leftChild, value ) ) return tmp; if( tmp = getNodePoint( BT->rightChild, value ) ) return tmp; return NULL; } } */ if(!BT) { return NULL; } else { if( BT->data == value ) { return BT; } //getNodePoint( BT->leftChild, value ); //getNodePoint( BT->rightChild, value ); bitNode *tmp = getNodePoint( BT->leftChild, value ); if(!tmp) { getNodePoint( BT->rightChild, value ); } //follow statement can't be added to the code //return tmp; } } void _Binary_Tree::PreOrderTraverse(binTree BT) { //if( emptyBinaryTree() ) // { //throw "Empty binary tree!Error in void _Binary_Tree::PreOrderTraverse(binTree BT) !\n"; //return; //} if (BT) { cout data leftChild); PreOrderTraverse(BT->rightChild); } } void _Binary_Tree::InOrderTraverse(binTree BT) { if (BT) { InOrderTraverse(BT->leftChild); cout data rightChild); } //return 0; } void _Binary_Tree::PostOrderTraverse( binTree BT ) { if (BT) { PostOrderTraverse(BT->leftChild); PostOrderTraverse(BT->rightChild); cout data leftChild ); destroy( BT->rightChild ); delete BT; BT = NULL; } } void _Binary_Tree::level( binTree BT, int number ) { if(BT) { level( BT->leftChild, number + 1 ); ///number +=3; //cout rightChild ) + 1; } } int _Binary_Tree::numberOfBTreeLeafNode( binTree BT, int &number ) { if(!BT) { return 0; } else { if( !BT->leftChild && !BT->rightChild ) //number += 1; number ++; //return 1; else { numberOfBTreeLeafNode( BT->leftChild, number ); numberOfBTreeLeafNode( BT->rightChild, number ); } return number; } } void _Binary_Tree::numberOfNodeDegreeTwo( binTree BT, int &number ) { if(!BT) { return; } else { if( BT->leftChild && BT->rightChild ) //number += 1; number += 1; //return 1; //else //{ numberOfNodeDegreeTwo( BT->leftChild, number ); numberOfNodeDegreeTwo( BT->rightChild, number ); //return numberOfNodeDegreeTwo( BT->leftChild, number ) + numberOfNodeDegreeTwo( BT->rightChild, number ); //} //return number; } } /* void _Binary_Tree::family( binTree BT, elementType1 number ) { if(!BT) { return; } if( BT->leftChild->data == number || BT->rightChild->data == number ) { cout data == number && BT->rightChild ) { cout data leftChild && BT->rightChild->data == number ) { cout data data == number && ( BT->leftChild || BT->rightChild ) ) { cout leftChild ? "left child ---- " : true ) rightChild, number ); //if( BT->data == number && BT-) //if( BT->leftChild->data == number &&) } */ //bool _Binary_Tree::getParent( binTree BT, elementType number, bool flag ) void _Binary_Tree::getParent( binTree BT, elementType value, bool &flag ) { if(!BT) { //return false; return; } if( ( BT->leftChild && BT->leftChild->data == value ) || ( BT->rightChild ) && ( BT->rightChild->data == value ) ) { flag = true; cout rightChild->data == value ) )//|| BT->rightChild->data == value ) { return BT; } bitNode *tmp = getParent( BT->leftChild, value ); if(!tmp) { getParent( BT->rightChild, value ); } } void _Binary_Tree::getSibling( binTree BT, elementType value, bool &flag ) { if(!BT) { cout leftChild; tmp->leftChild = NULL; tmp->rightChild = NULL; copyBTree( tmp, BT->leftChild ); } if( BT->rightChild ) { BT1->rightChild = new bitNode; tmp = BT1->rightChild; tmp->leftChild = NULL; tmp->rightChild = NULL; copyBTree( tmp, BT->rightChild ); } } void _Binary_Tree::levelOrderTraverse( binTree BT ) { clq.enQueue(BT); while( !clq.emptyCharLinkedQueue() ) { //CLNode *tmp = NULL; clq.getFront(BT); cout data leftChild != NULL ) { clq.enQueue( BT->leftChild ); } if( BT->rightChild != NULL ) { clq.enQueue( BT->rightChild ); } } } void _Binary_Tree::allLeafToRootPath( binTree BT, char *path, int &pathLength ) { if(BT) { if( !BT->leftChild && !BT->rightChild ) { path[pathLength] = BT->data; cout data rightChild ) { path[pathLength] = BT->data; if( pathLength > longestLength) { //cout data |
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |