erchashu.rar_完全erchashu

#include <stdio.h> #include <string.h> #include <stdlib.h> #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针 int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数 //==========基于先序遍历算法创建二叉树============== //=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void) { BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //读入#，返回空指针 else{ T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } } //========NLR 先序遍历============= void Preorder(BinTree T) { if(T) { printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //========LNR 中序遍历=============== void Inorder(BinTree T) { if(T){ Inorder(T->lchild); printf("%c",T->data); Inorder(T->rchild); } } //==========LRN 后序遍历============ void Postorder(BinTree T) { if(T){ Postorder(T->lchild); Postorder(T->rchild); printf("%c",T->data); } } //=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int hl,hr,max;TreeDepth(BinTree T) { if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。 return(max+1); } else return(0); } //====利用"先进先出"（FIFO）队列，按层次遍历二叉树========== void Levelorder(BinTree T) { int front=0,rear=1; BinTNode *cq[Max],*p; //定义结点的指针数组cq cq[1]=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出队 printf("%c",p->data); //出队，输出结点的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子树入队 } } } void Swaporder(BinTree T) { struct BinTree *T1; if(T!=NULL) { T1=T->lchild; T->lchild=T->rchild; T->rchild=T1; Swaporder(T->rchild); Swaporder(T->lchild); } } //==========主函数================= void main() { BinTree root; int i,depth; printf("\n"); printf("构建二叉树，输入完全二叉树的先序序列:\n"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 do { //从菜单中选择遍历方式，输入序号。 printf("\t********** 菜单 ************\n"); printf("\t1: 先序遍历\n"); printf("\t2: 中序遍历\n"); printf("\t3: 后序遍历\n"); printf("\t4: 输出树的深度,结点数,叶子数\n"); printf("\t5: 层次遍历\n"); //按层次遍历之前，先选择4，求出该树的结点数。 printf("\t6: 交换左右子树\n"); printf("\t0: Exit\n"); printf("\t*******************************\n"); scanf("%d",&i); //输入菜单序号（0-5） switch (i){ case 1: printf("先序序列打印二叉树: "); Preorder(root); //先序遍历 break; case 2: printf("中序序列打印二叉树: "); Inorder(root); //中序遍历 break; case 3: printf("后序序列打印二叉树: "); Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf("二叉树深度为%d 二叉树结点数为%d",depth,NodeNum); printf(" 二叉树叶子数为%d",leaf); break; case 5: printf("按层次遍历二叉树: "); Levelorder(root); //按层次遍历 break; case 6:printf("交换左右子树\n"); Swaporder(root); NodeNum=0; leaf=0; printf("交换完成，请重新遍历。"); break; default: exit(1); } printf("\n"); } while(i!=0); }