实验二二叉树及其应用
实验二二叉树及其应用实验目的1. 加深对二叉树的结构特性的理解；2. 熟练掌握二叉树的存储结构，特别是二叉链表结构的特点；3. 熟练掌握二叉树的遍历算法原理及实现；4. 学会编写实现二叉树的各种算法；5. 掌握二叉树的应用方法；实验学时：建议 24学时实验内容内容 1：二叉树及其操作【问题描述】建立一棵以二叉链表结构存储的二叉树，并对其进行遍历。 求该二叉树中的结点个数等操作。【基本要求】（1）建立二叉树的方法可以用教材中的先序方式建立，也可以根据二叉树的先序序列和中序序列来建立。（2）对二叉树的遍历可采用递归或非递归的算法。【实现提示】（1） 二叉链表的结点结构描述typedef struct btnode / 定义结点类型ElemType data; /数据域struct btnode * lchild ，* rchild; /左、右指针域 / *bitree; / btnode （2） 可设计以下功能函数：bitree createbitree(); /建立二叉链表void preorder(bitree bt); /先序遍历二叉树int sum(bitree bt); /求二叉树中的结点个数算法可用递归或非递归实现。建立二叉树可用以下两种算法实现：方案 1：btnode * createBT ( ) /前序建树 bitree T; char ch; cin >>ch ; if(ch=#) return NULL; / 二叉树为空T=new BinTNode; /申请根结点T->data=ch; T->lchild=createBTpre(); /创建根的左子树T->rchild=createBTpre(); /创建根的右子树return T; 方案 2：btnode* createBT ( char *preorder,char *midorder) /由前序 preorder和中序 midorder 建树，返回根指针if(strlen (preorder) =0) return NULL; / 空二叉树T= new Node; /建立根结点T->data=*preorder; k=locate(midorder， *preorder); /找根在中序中的位置lmidorder=fetch(midorder,0,k); /左子树的中序lpreorder =fetch(preorder,1,k); /左子树的前序rmidorder=fetch(midorder,k+1); /右子树的中序rpreorder =fetch(preorder, k+1); /右子树的前序T->lchild=createBT (lmidorder , lpreorder);/建根的左子树T->rchild=createBT(rmidorder , rpreorder); /建根的右子树return T; int sum(bitree bt) /求二叉树中的结点个数 if(!bt) return 0; /二叉树为空return sum(bt->lchild) + sum(bt->rchild) +1; 【选做内容】（1） 对二叉树进行层次遍历算法。（2） 求二叉树的深度、宽度等操作。（3） 复制二叉树，交换二叉树中左右子树的问题怎么实现? 建立的二叉树为：A B C D E F G H #include using namespace std; typedef char datatype; typedef struct node datatype data; struct node *lchild,*rchild; bintnode; typedef bintnode *bintree; typedef struct stack bintree data100; int tag100; int top; seqstack; 创建二叉树算法：void CreateBinTree(bintree *t) char ch; if(ch=getchar()='0') (*t)=NULL; else *t=new bintnode ; (*t)->data=ch; CreateBinTree( CreateBinTree( 前序遍历递归算法：void Preorder(bintree t) if(t) coutdatalchild); Preorder(t->rchild); 中序遍历递归算法：void Inorder(bintree t) if(t) Inorder(t->lchild); coutdatarchild); 后序遍历递归算法：void Postorder(bintree t) if(t) Postorder(t->lchild); Postorder(t->rchild); coutdatadata+s->top=t; bintree Pop(seqstack *s) if(s->top!=-1) s->top-; return (s->datas->top+1); else return NULL; 前序遍历非递归算法：void Preorder1(bintree t) seqstack s; s.top=-1; while(t)|(s.top!=-1) while(t) coutdatalchild; if(s.top>-1) t=Pop( t=t->rchild; 中序遍历非递归算法：void Inorder1(bintree t) seqstack s; s.top=-1; while(t!=NULL)|(s.top!=-1) while(t) Push( t=t->lchild; if(s.top!=-1) t=Pop( coutdatarchild; 层次遍历算法：void Levelorder(bintree t) bintree queue100; int front,rear; if(t=NULL) return; front=-1; rear=0; queuerear=t; while(front!=rear) front+; coutdatalchild!=NULL) rear+; queuerear=queuefront->lchild; if(queuefront->rchild!=NULL) rear+; queuerear=queuefront->rchild; 遍历叶子节点算法：void CountLeaf(bintree t) if(!t) return; if(!(t->lchild|t->rchild) coutdatalchild); CountLeaf(t->rchild); 交换左右子树算法：void SwapBinTree(bintree t) bintree s; if(t) SwapBinTree(t->lchild); SwapBinTree(t->rchild); s=t->lchild; t->lchild=t->rchild; t->rchild=s; 主函数实现：void main() bintree root; cout3.#include 4.usingnamespace std; 5.6.struct BTNode 7. 8.char m_value; 9. BTNode *m_left; 10. BTNode *m_right; 11.; 12.13./ 先序创建二叉树14.void CreatBTree(BTNode * 17. cin >> nValue; 18.if ( '#' = nValue) 19. 20.return; 21. 22.else23. 24. root = new BTNode(); 25. root->m_value = nValue; 26. CreatBTree(root->m_left); 27. CreatBTree(root->m_right); 28. 29. 30.31./ 求二叉树的深度32.int GetDepth(BTNode *pRoot) 33. 34.if (pRoot = NULL) 35. 36.return 0; 37. 38.39./ int nLeftLength = GetDepth(pRoot->m_left);40./ int nRigthLength = GetDepth(pRoot->m_right);41./ return nLeftLength > nRigthLength ? (nLeftLength + 1) : (nRigthLength + 1);42.43.return GetDepth(pRoot->m_left) > GetDepth(pRoot->m_right) ? 44. (GetDepth(pRoot->m_left) + 1) : (GetDepth(pRoot->m_right) + 1); 45. 46.47./ 求二叉树的宽度48.int GetWidth(BTNode *pRoot) 49. 50.if (pRoot = NULL) 51. 52.return 0; 53. 54.55.int nLastLevelWidth = 0;/ 记录上一层的宽度56.int nTempLastLevelWidth = 0; 57.int nCurLevelWidth = 0;/ 记录当前层的宽度58.int nWidth = 1;/ 二叉树的宽度59. queue myQueue; 60. myQueue.push(pRoot);/ 将根节点入队列61. nLastLevelWidth = 1; 62. BTNode *pCur = NULL; 63.64.while (!myQueue.empty()/ 队列不空65. 66. nTempLastLevelWidth = nLastLevelWidth; 67.while (nTempLastLevelWidth != 0) 68. 69. pCur = myQueue.front();/ 取出队列头元素70. myQueue.pop();/ 将队列头元素出对71.72.if (pCur->m_left != NULL) 73. 74. myQueue.push(pCur->m_left); 75. 76.77.if (pCur->m_right != NULL) 78. 79. myQueue.push(pCur->m_right); 80. 81.82. nTempLastLevelWidth-; 83. 84.85. nCurLev
