7-10 先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数 (10 分)
对于给定的二叉树，输出其先序序列、中序序列、后序序列并输出叶子结点数。
输入格式:
二叉树的先序遍历序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
若是非空二叉树，则输出四行内容 第一行是二叉树的先序遍历序列； 第二行是二叉树的中序遍历序列； 第三行是二叉树的后序遍历序列； 第四行是叶子结点数；
若是空二叉树 只需输出叶子数0
输入样例1:
FCA##DB###EHM###G##
结尾无空行
输出样例1:
1. FCADBEHMG 2. ACBDFMHEG 3. ABDCMHGEF 4. 4
结尾无空行
输入样例2:
#
结尾无空行
输出样例2:
0
结尾无空行
#include<iostream> using namespace std; typedef struct bt{ char data; struct bt *l,*r; }*tree; void create(tree &t){ char ch; scanf("%c",&ch); if(ch=='#')t=NULL; else{ t=new(struct bt); t->data=ch; create(t->l); create(t->r); } } void pre(tree t){ if(t){ printf("%c",t->data); pre(t->l); pre(t->r); } } void in(tree t){ if(t){ in(t->l); printf("%c",t->data); in(t->r); } } void post(tree t){ if(t){ post(t->l); post(t->r); printf("%c",t->data); } } int leaf_sum(tree t){ if(!t)return 0; if(!t->l&&!t->r)return 1; return leaf_sum(t->l)+leaf_sum(t->r); } int main(){ tree t; create(t); if(t){ pre(t); printf("\n"); in(t); printf("\n"); post(t); printf("\n"); } printf("%d",leaf_sum(t)); return 0; }
#include<iostream> #include<cstdio> #include<malloc.h> #define OVERFLOW -2 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void CreateBiTree(BiTree &L){ char ch; scanf("%c",&ch); if(ch=='#')L=NULL; else{ L=(BiTree)malloc(sizeof(BiTNode)); if(!L)exit(OVERFLOW); L->data=ch; CreateBiTree(L->lchild); CreateBiTree(L->rchild); } } void PreOrderTraverse(BiTree L){ if(L){ printf("%c",L->data); PreOrderTraverse(L->lchild); PreOrderTraverse(L->rchild); } } void PostOrderTraverse(BiTree L){ if(L){ PostOrderTraverse(L->lchild); PostOrderTraverse(L->rchild); printf("%c",L->data); } } void InOrderTraverse(BiTree L){ if(L){ InOrderTraverse(L->lchild); printf("%c",L->data); InOrderTraverse(L->rchild); } } int Depth(BiTree L){ int d1,d2,d3; if(!L)d1=0; else{ d2=Depth(L->lchild); d3=Depth(L->rchild); d1=1+(d2>d3?d2:d3); } return d1; } int Leaf(BiTree L,int &c){ if(L!=NULL){//在树不为空的时候才能讨论左右结点 if(L->lchild==NULL&&L->rchild==NULL)c++; Leaf(L->lchild,c); Leaf(L->rchild,c); } return c; } void GetFloor(BiTree L,char data,int floor,int &res){ if(L!=NULL){ if(L->data==data){ res=floor; } GetFloor(L->lchild,data,floor+1,res); GetFloor(L->rchild,data,floor+1,res); } } int c=0; void Count(BiTree L){ if(L!=NULL){ c++; Count(L->lchild); Count(L->rchild); } } int main(){ BiTree T; CreateBiTree(T); printf("先序遍历序列为：\n"); PreOrderTraverse(T); printf("\n中序遍历序列为：\n"); InOrderTraverse(T); printf("\n后序遍历序列为：\n"); PostOrderTraverse(T); printf("\n高度：%d\n",Depth(T)); int m=0; Leaf(T,m); printf("叶子数：%d\n",m); int floor=1,res; GetFloor(T,'D',floor,res); printf("在第%d层\n",res); Count(T); printf("一共有%d个结点\n",c); }
#include <stdio.h> #include <iostream> #include <malloc.h> #include <string.h> using namespace std; //定义二叉树结构 typedef struct Node { char data; struct Node *lchild,*rchild;//创建左右结点指针 }*BTree,BTNode; //程序使用的函数 void CreateBTree(BTree &T);//按先序遍历方式创建二叉树 void PreOrderTraverse(BTree T);//先序遍历函数 void InOrderTraverse(BTree T);//中序遍历函数 void PostOrderTraverse(BTree T);//后序遍历函数 void LevelTraverse(BTree T) ;//层次遍历函数 int SearchDepth(BTree T);//求树的高度度函数 int NodeNum(BTree T);//求二叉树中结点个数函数 int LeafNum(BTree T);//求二叉树中叶子结点个数函数 void ExChangeTree(BTree &T);//左右结点交换函数 //按先序遍历方式创建二叉树 void CreateBTree(BTree &T) { char ch; cin>>ch;//将输入的字符储存在数组ch中 if(ch=='*')//定义符号*为空树 T=NULL; else //输入字符不为*，将其储存在树中 { T=new BTNode; T->data=ch; CreateBTree(T->lchild); CreateBTree(T->rchild); } } //先序遍历函数 void PreOrderTraverse(BTree T) { if(T!=NULL)//当结点不为空时，遍历二叉树 { cout<<T->data; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } //中序遍历函数 void InOrderTraverse(BTree T) { if(T!=NULL)//当结点不为空时，遍历二叉树 { InOrderTraverse(T->lchild); cout<<T->data; InOrderTraverse(T->rchild); } } //后序遍历函数 void PostOrderTraverse(BTree T) { if(T!=NULL)//当结点不为空时，遍历二叉树 { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data; } } //层次遍历函数 void LevelTraverse(BTree T) { if(T==NULL) { printf("二叉树为空树"); return; } BTNode *queue[50]; //创建应该队列 int front=0; int rear=0; BTNode *p; queue[rear]=T;//树根入队 while(front!=rear)//当前端和后端不相等时 { p=queue[front];//p指向根，读出根，并出队 printf("%c",p->data);//输出二叉树的结点 if(p->lchild!=NULL) //左子树不为空，入队 { queue[rear]=p->lchild; } if(p->rchild!=NULL) //右子树不为空，入队 { queue[rear]=p->rchild; } } } //求树的高度度函数 int SearchDepth(BTree T) { if(T==NULL) { return 0; } else { int m=SearchDepth(T->lchild); int n=SearchDepth(T->rchild); if(m>n) { return (m+1); } else { return (n+1); } } } //求二叉树中结点个数函数 int NodeNum(BTree T) { if(T==NULL) //如果第一个为空节点，则二叉树为空，返回值为0 { return 0; } else //第一个结点不为空，结点数为左右子树数加上第一个结点 { return NodeNum(T->lchild)+NodeNum(T->rchild)+1; } } //求二叉树中叶子结点个数函数 int LeafNum(BTree T) { if(T==NULL) //如果第一个为空节点，则二叉树为空，返回值为0 { return 0; } if(T->lchild==NULL &&T->rchild==NULL)//如果二叉树左右子树皆为空,说明该二叉树只有根节点为叶子节点,返回值1. { return 1; } else //否则叶子结点数为左右子树之和 { return LeafNum(T->lchild)+LeafNum(T->rchild); } } //左右结点交换函数 void ExChangeTree(BTree &T) { BTree tem; if(T!=NULL)//判断T是否为空，非空进行转换，否则不转换 { tem=T->lchild; T->lchild=T->rchild;//直接交换节点地址 T->rchild=tem; ExChangeTree(T->lchild); ExChangeTree(T->rchild); } } int main()//主函数调用前面子函数并输出结果 { BTree T; cout<<"按先序遍历方式创建二叉树(用*表示空树):"; CreateBTree(T); cout<<"中序遍历输出结果:"; InOrderTraverse(T); cout<<endl<<"先序遍历输出结果:"; PreOrderTraverse(T); cout<<endl<<"后序遍历输出结果:"; PostOrderTraverse(T); cout<<endl<<"层次遍历输出结果:"; LevelTraverse(T); cout<<endl<<"树的高度:"<<SearchDepth(T); cout<<endl<<"总结点的个数:"<<NodeNum(T); cout<<endl<<"叶结点的个数:"<<LeafNum(T); BTree temporarytree=T; //复制一颗树，在不改变原树的情况下，对临时树进行交换。 ExChangeTree(temporarytree); cout<<endl<<"左右结点交换结果:"; PreOrderTraverse(temporarytree); printf("\n"); return 0; }
