数据结构专科辅导五

1、13数据结构专科辅导五一个程序采用结构定义二叉 第二个程序采用类定义二叉-二叉树操作算法下面给出两个程序， 它们都是用来实现对二叉树的操作。树结点的类型， 采用普通函数对二叉树进行每一种操作的处理； 树的类型，采用成员函数实现二叉树的每一种操作。程序 1:/定义二叉树结点结构和操作的头文件btree1.h/定义二叉树结点值的类型为字符型typedef char ElemType;/定义二叉树结点类型struct BTreeNode ElemType data;BTreeNode* left;BTreeNode* right;/初始化二叉树，即把树根指针置空void InitBTree(BTre

2、eNode*& BT);/根据存于字符数组 a 的二叉树广义表建立对应的二叉树存储结构 void CreateBTree(BTreeNode*& BT, char* a);/判断二叉树是否为空bool BTreeEmpty(BTreeNode* BT); /按任一种遍历次序输出二叉树中的所有结点void TraverseBTree(BTreeNode* BT, int mark); /求二叉树的深度int BTreeDepth(BTreeNode* BT); /求二叉树中所有结点数int BTreeCount(BTreeNode* BT); /求二叉树中所有叶子结点数int B

3、TreeLeafCount(BTreeNode* BT); /按照二叉树的一种表示方法输出整个二叉树 void PrintBTree(BTreeNode* BT);/清除二叉树，使之变为一棵空树void ClearBTree(BTreeNode*& BT);/二叉树操作的实现文件 btree1.cpp #include<iostream.h>#include<stdlib.h>#include<strstrea.h> /初始化二叉树，即把树根指针置空 void InitBTree(BTreeNode*& BT) BT=NULL;/根据存于字符

4、数组 a 的二叉树广义表建立对应的二叉树存储结构void CreateBTree(BTreeNode*& BT, char* a)BTreeNode* s10; int top=-1; BT=NULL;BTreeNode* p;/s 数组作为存储二叉树中根结点指针的栈/top 作为 s 栈的栈顶指针 /给树根指针置空/定义 p 为指向二叉树结点的指针int k;/用 k 作为处理结点的左子树和右子树的标记，k=1 处理/左子树， k=2 处理右子树istrstream ins(a);/把字符串 a 定义为输入字符串流对象 inschar ch;ins>>ch;/从 ins

5、流对象顺序读入一个字符，while (ch!='') / 每循环一次处理一个读入的字符，直到扫描到''字符为止switch(ch)case '(':top+; stop=p; k=1; break;case ')':top-; break;case ',':k=2; break;default:p=new BTreeNode;p->data=ch; p->left=p->right=NULL; if(BT=NULL) BT=p;else if(k=1) stop->left=p;else s

6、top->right=p;ins>>ch;/判断二叉树是否为空bool BTreeEmpty(BTreeNode* BT)return BT=NULL;/按任一种遍历次序输出二叉树中的所有结点void TraverseBTree(BTreeNode* BT, int mark)if(mark=1) / 先序遍历if(BT!=NULL) cout<<BT->data<<' ' TraverseBTree(BT->left,mark); TraverseBTree(BT->right,mark);else if(mark=

7、2) / 中序遍历if(BT!=NULL) TraverseBTree(BT->left,mark); cout<<BT->data<<' ' TraverseBTree(BT->right,mark);else if(mark=3) / 后续遍历if(BT!=NULL) TraverseBTree(BT->left,mark);TraverseBTree(BT->right,mark); cout<<BT->data<<' 'else if(mark=4) /按层遍历const

8、 MaxLength=30;BTreeNode* QMaxLength;/定义存储二叉树结点指针的数组空间作为队列使用int front=0, rear=0;/定义队首指针和队尾指针，初始均置0 表示空队BTreeNode* p;if(BT!=NULL) rear=(rear+1)%MaxLength; /后移队尾指针 Qrear=BT; / 将树根结点指针进队while (front!=rear) / 当队列非空时执行循环front=(front+1)%MaxLength;/后移队首指针p=Qfront;/删除队首结点cout<<p->data<<' &

9、#39;/输出队首结点的值if(p->left!=NULL) / 若结点存在左孩子，则左孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p->left;if(p->right!=NULL) / 若结点存在右孩子，则右孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p->right;else cerr<<"mark 的值无效 ! 遍历失败 !"<<endl;exit(1);/求二叉树的深度int BTreeDepth(BTreeNode* BT)if(BT=NULL

10、)return 0; / 对于空树，返回 0 并结束递归else/计算左子树的深度int dep1=BTreeDepth(BT->left);/计算右子树的深度int dep2=BTreeDepth(BT->right);/返回树的深度if(dep1>dep2) return dep1+1;else return dep2+1;/求二叉树中所有结点数int BTreeCount(BTreeNode* BT) if(BT=NULL) return 0; elsereturn BTreeCount(BT->left)+BTreeCount(BT->right)+1;/

11、求二叉树中所有叶子结点数int BTreeLeafCount(BTreeNode* BT) if(BT=NULL) return 0; else if(BT->left=NULL && BT->right=NULL) return 1; else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);/按照二叉树的一种表示方法输出整个二叉树 void PrintBTree(BTreeNode* BT)/输出二叉树的广义表表示 if(BT=NULL) return;/ 树为空时返回else /

12、否则执行如下操作cout<<BT->data; / 输出根结点的值 if(BT->left!=NULL | BT->right!=NULL) cout<<'(' PrintBTree(BT->left); if(BT->right!=NULL) cout<<','PrintBTree(BT->right); cout<<')'/清除二叉树，使之变为一棵空树void ClearBTree(BTreeNode*& BT)if(BT!=NULL) / 当二叉树非

13、空时进行如下操作 ClearBTree(BT->left); ClearBTree(BT->right); delete BT; BT=NULL;/输出左括号/输出左子树/若右子树不为空则输出逗号分隔符/ 输出右子树/输出右括号/删除左子树/删除右子树 /删除根结点/置根指针为空/进行二叉树操作的主程序文件btreeMain1.cpp#include<iostream.h>#include"btree1.h"#include"btree1.cpp"void main()/定义指向二叉树结点的指针，并用它作为树根指针 BTreeNo

14、de* bt;/ 初始化二叉树，即置树根指针bt 为空InitBTree(bt);/定义一个用于存放二叉树广义表的字符数组char b50;/从键盘向字符数组b输入以''字符结束的二叉树广义表："<<endl；cout<<" 输入以 ''字符作为结束符的二叉树广义表表示 cin.getline(b,sizeof(b);/建立以 bt 作为树根指针的二叉树的链接存储结构 CreateBTree(bt,b);/以广义表形式输出二叉树PrintBTree(bt); cout<<endl;/前序遍历以 bt 为树根

15、指针的二叉树cout<<" 前序： "TraverseBTree(bt,1); cout<<endl;/中序遍历以 bt 为树根指针的二叉树 cout<<" 中序： "TraverseBTree(bt,2); cout<<endl;/后序遍历以 bt 为树根指针的二叉树 cout<<" 后序： "TraverseBTree(bt,3); cout<<endl;/按层遍历以 bt 为树根指针的二叉树 cout<<" 按层： "Trav

16、erseBTree(bt,4); cout<<endl;/求出以 bt 为树根指针的二叉树的深度cout<<" 二叉树的深度为： " cout<<BTreeDepth(bt)<<endl;/求出以 bt 为树根指针的二叉树中的所有结点数cout<<"二叉树中的结点数："； cout<<BTreeCount(bt)<<endl;/求出以 bt 为树根指针的二叉树中的所有叶子结点数 cout<<"二叉树中的叶子结点数："；cout<<

17、;BTreeLeafCount(bt)<<endl；/ 清除以 bt 为树根指针的二叉树 ClearBTree(bt);程序 2:/二叉树类定义头文件 btree2.h/定义二叉树结点值的类型为字符型 typedef char ElemType;/定义二叉树结点类型struct BTreeNode ElemType data; BTreeNode* left; BTreeNode* right;/定义二叉树类class BinaryTree BTreeNode* root;public:/构造函数，初始化二叉树为空 BinaryTree() root=NULL;/根据存于字符数组

18、a 的二叉树广义表建立对应的二叉树存储结构 void CreateBTree(char* a);/判断二叉树是否为空bool BTreeEmpty() return root=NULL; /按任一种遍历次序输出二叉树中的所有结点 void TraverseBTree(int mark);/求二叉树的深度 int BTreeDepth();/求二叉树中所有结点数int BTreeCount(); /求二叉树中所有叶子结点数 int BTreeLeafCount();/按照二叉树的一种表示方法输出整个二叉树 void PrintBTree();/析构函数，清除二叉树 BinaryTree();/二

19、叉树类的实现文件 btree2.cpp#include<iostream.h>#include<stdlib.h>#include<strstrea.h> static void Traverse(BTreeNode* BT, int mark); static int Depth(BTreeNode* BT);static int Count(BTreeNode* BT);static int LeafCount(BTreeNode* BT);static void Print(BTreeNode* BT);static void Clear(BTreeN

20、ode*& BT);/根据存于字符数组 a 的二叉树广义表建立对应的二叉树存储结构void BinaryTree:CreateBTree(char* a) BTreeNode* s20; int top=-1; root=NULL;BTreeNode* p;/s 数组作为存储二叉树中根结点指针的栈/top 作为 s 栈的栈顶指针 /给树根指针置空/定义 p 为指向二叉树结点的指针int k;/用 k 作为处理结点的左子树和右子树的标记，k=1 处理/左子树，k=2 处理右子树istrstream ins(a); char ch; ins>>ch;while (ch!=

21、9;')/把字符串 a 定义为输入字符串流对象 ins/从 ins 流对象顺序读入一个字符，/ 每循环一次处理一个读入的字符，直到扫描到''字符为止switch(ch)case '(':top+; stop=p; k=1; break;case ')':top-; break;case ',':k=2; break;default:p=new BTreeNode;p->data=ch; p->left=p->right=NULL; if(root=NULL) root=p;else if(k=1) sto

22、p->left=p; else stop->right=p;ins>>ch;/按任一种遍历次序输出二叉树中的所有结点void BinaryTree:TraverseBTree(int mark)Traverse(root,mark);/用于遍历的递归函数void Traverse(BTreeNode* BT, int mark)if(mark=1) / 先序遍历if(BT!=NULL) cout<<BT->data<<' ' Traverse(BT->left,mark); Traverse(BT->right,

23、mark);else if(mark=2) / 中序遍历if(BT!=NULL) Traverse(BT->left,mark);cout<<BT->data<<' 'Traverse(BT->right,mark);else if(mark=3) / 后续遍历if(BT!=NULL) Traverse(BT->left,mark);Traverse(BT->right,mark); cout<<BT->data<<' 'else if(mark=4) /按层遍历const Ma

24、xLength=30;BTreeNode* QMaxLength; /定义存储二叉树结点指针的数组空间作为队列使用 int front=0, rear=0;/定义队首指针和队尾指针，初始均置0 表示空队BTreeNode* p;if(BT!=NULL) rear=(rear+1)%MaxLength; /后移队尾指针Qrear=BT;/将树根结点指针进队while (front!=rear) / 当队列非空时执行循环front=(front+1)%MaxLength;/后移队首指针p=Qfront;/删除队首结点cout<<p->data<<' '

25、/输出队首结点的值if(p->left!=NULL) / 若结点存在左孩子，则左孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p->left;if(p->right!=NULL) / 若结点存在右孩子，则右孩子结点指针进队 rear=(rear+1)%MaxLength; Qrear=p->right;else cerr<<"mark 的值无效 ! 遍历失败 !"<<endl; exit(1);/求二叉树的深度int BinaryTree:BTreeDepth()return Depth(ro

26、ot);/用于求二叉树深度的递归函数int Depth(BTreeNode* BT)if(BT=NULL)return 0; / 对于空树，返回 0 并结束递归else/计算左子树的深度int dep1=Depth(BT->left);/计算右子树的深度int dep2=Depth(BT->right);/返回树的深度 if(dep1>dep2) return dep1+1; else return dep2+1;/求二叉树中所有结点数int BinaryTree:BTreeCount()return Count(root);/用于求二叉树中所有结点数的递归函数int Cou

27、nt(BTreeNode* BT)if(BT=NULL) return 0;elsereturn Count(BT->left)+Count(BT->right)+1;/求二叉树中所有叶子结点数int BinaryTree:BTreeLeafCount()return LeafCount(root);/用于求二叉树中所有叶子结点数的递归函数int LeafCount(BTreeNode* BT)if(BT=NULL) return 0;else if(BT->left=NULL && BT->right=NULL) return 1; else retu

28、rn LeafCount(BT->left)+LeafCount(BT->right); /按照二叉树的广义表表示输出整个二叉树void BinaryTree:PrintBTree()Print(root);/用于输出整个二叉树的递归函数void Print(BTreeNode* BT)/输出二叉树的if(BT=NULL) return;/ 树为空时返回else / 否则执行如下操作 cout<<BT->data; / 输出根结点的值 if(BT->left!=NULL | BT->right!=NULL) cout<<'('

29、; Print(BT->left); if(BT->right!=NULL) cout<<',' Print(BT->right); cout<<')'/输出左括号/输出左子树/若右子树不为空则输出逗/输出右子树/输出右括号分隔符/析构函数，清除二叉树BinaryTree:BinaryTree() Clear(root);/用于清除二叉树的递归函数 void Clear(BTreeNode*& BT) if(BT!=NULL)/删除左子树/删除右子树 /删除根结点/置根指针为空 / 当二叉树非空时进行如下操作Clear(BT->left);Clear(BT->right);delete BT;BT=NULL;/进行二叉树操作的主文件btree