[数据结构与算法]【无标题】树和二叉树

#include<iostream>
using namespace std;
#define MAXTSIZE 100

typedef struct BiTNode{
?? ?char data;
?? ?struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

//1．输入先序遍历字符序列，建立二叉链表。
void CreateBiTree(BiTree &T)
{
?? ?char ch;
?? ?cin>>ch;
?? ?if(ch=='#') T=NULL;
?? ?else
?? ?{
?? ??? ?T=new BiTNode;
?? ??? ?T->data=ch;
?? ??? ?CreateBiTree(T->lchild);
?? ??? ?CreateBiTree(T->rchild);
?? ?}
}

//2．分别输出先序、中序和后序遍历二叉树的序列（递归算法）。
void PreOrderTraverse(BiTree T)//先序遍历（递归）
{
?? ?if(T)
?? ?{
?? ??? ?cout<<T->data;
?? ??? ?PreOrderTraverse(T->lchild);
?? ??? ?PreOrderTraverse(T->rchild);
?? ?}
}?

void InOrderTraverse(BiTree T)//中序遍历（递归）
{
?? ?if(T)
?? ?{
?? ??? ?InOrderTraverse(T->lchild);
?? ??? ?cout<<T->data;
?? ??? ?InOrderTraverse(T->rchild);
?? ?}
}?

void PostOrderTraverse(BiTree T)//后序遍历（递归）
{
?? ?if(T)
?? ?{
?? ??? ?PostOrderTraverse(T->lchild);
?? ??? ?PostOrderTraverse(T->rchild);
?? ??? ?cout<<T->data;
?? ?}
}?

//3．求二叉树的结点个数。
int NodeCount(BiTree T)
{
?? ?if(T==NULL) return 0;
?? ?else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

//4．输出二叉树的叶子结点。
void LeafNode(BiTree T)
{
?? ?if(T!=NULL)
?? ?{
?? ??? ?if(T->lchild==NULL&&T->rchild==NULL)
?? ??? ??? ?cout<<T->data;
?? ??? ?LeafNode(T->lchild);
?? ??? ?LeafNode(T->rchild);
?? ?}
}

//5．求二叉树的高度。
int Depth(BiTree T)
{
?? ?if(T==NULL) return 0;
?? ?else
?? ?{
?? ??? ?int m,n;
?? ??? ?m=Depth(T->lchild);
?? ??? ?n=Depth(T->rchild);
?? ??? ?if(m>n) return (m+1);
?? ??? ?else return (n+1);
?? ?}
}

void test(BiTree T)
{
?? ?while(1)
?? ?{
?? ??? ?cout<<"功能介绍："<<endl;
?? ??? ?cout<<"1．输入先序遍历字符序列，建立二叉链表。"<<endl;
?? ??? ?cout<<"2．输出先序遍历二叉树的序列（递归算法）。"<<endl;
?? ??? ?cout<<"3．输出中序遍历二叉树的序列（递归算法）。"<<endl;
?? ??? ?cout<<"4．输出后序遍历二叉树的序列（递归算法）。"<<endl;
?? ??? ?cout<<"5．求二叉树的结点个数。"<<endl;
?? ??? ?cout<<"6．输出二叉树的叶子结点。"<<endl;
?? ??? ?cout<<"7．求二叉树的高度。"<<endl;
?? ??? ?cout<<"8. 退出。"<<endl;
?? ??? ?fflush(stdin);
?? ??? ?int x,choose;
?? ??? ?cout<<"请选择："<<endl;
?? ??? ?cin>>choose;
?? ??? ?while(choose!=8)
?? ??? ?{
?? ??? ??? ?while(choose<1||choose>8)
?? ??? ??? ?{
?? ??? ??? ??? ?cout<<"暂时没有此功能，请重新输入："<<endl;
?? ??? ??? ??? ?fflush(stdin);
?? ??? ??? ??? ?cin>>choose;
?? ??? ??? ?}
?? ??? ??? ?switch(choose)
?? ??? ??? ?{
?? ??? ??? ??? ?case 1:CreateBiTree(T);
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 2:PreOrderTraverse(T);
?? ??? ??? ??? ??? ??? ?cout<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 3:InOrderTraverse(T);
?? ??? ??? ??? ??? ??? ?cout<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 4:PostOrderTraverse(T);
?? ??? ??? ??? ??? ??? ?cout<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 5:cout<<NodeCount(T)<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 6:LeafNode(T);
?? ??? ??? ??? ??? ??? ?cout<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case 7:cout<<Depth(T)<<endl;
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?fflush(stdin);
?? ??? ??? ?cout<<"请选择："<<endl;
?? ??? ??? ?cin>>choose;
?? ??? ?}
?? ??? ?break;
?? ?}
}

int main()
{
?? ?BiTree T;
?? ?test(T);
?? ?system("pause");
?? ?return 0;
}