算法之数学--二叉树的各种遍历方法和相关问题 2021-03-11（未完待续）-白红宇

算法之数学--二叉树的各种遍历方法和相关问题 2021-03-11（未完待续）

阅读量：4101 次

发布时间：2019-05-25

本文共 1288 字，大约阅读时间需要 4 分钟。

二叉树的建立和遍历

题目描述

Time Limit: 1000 ms

Memory Limit: 256 mb

建立以二叉链作为存储结构的二叉树，实现 1）先序遍历； 2）中序遍历； 3）后序遍历； 4）层序遍历； 5）编程计算二叉树的叶子结点个数。

输入描述:

按照先序遍历序列输入二叉树中数据元素的值，没有的输入0表示。

输出描述:

第一行输出先序遍历序列第二行输出中序遍历序列第三行输出后序遍历序列第四行输出叶子结点的个数。

代码

#include 
   
    using namespace std;typedef struct node{
   	char data;	struct node *leftchild,*rightchild;}*BitTree;//先序遍历方式建立二叉树void CreateBitTree(BitTree &T){
   	char c;	cin>>c;	if(c=='0')		T==NULL;	else{
   		T = new node;		T->data = c;		CreateBitTree(T->leftchild);		CreateBitTree(T->rightchild);	}	}//先序输出void PreOrderTraverse(BitTree T){
   	if(!T==NULL){
   		cout<
    
     data<<' ';		PreOrderTraverse(T->leftchild);		PreOrderTraverse(T->rightchild);	}}//中序输出void InOrderTraverse(BitTree T){
   	if(!T==NULL){
   		InOrderTraverse(T->leftchild);		cout<
     
      data<<' ';		InOrderTraverse(T->rightchild);	}}//后序输出void PostOrderTraverse(BitTree T){
   	if(!T==NULL){
   		PostOrderTraverse(T->leftchild);		PostOrderTraverse(T->rightchild);		cout<
      
       data<<' ';	}}int sum = 0;//输出叶子结点个数int Count(BitTree T){
   	if(T!=NULL){
   		if(T->leftchild==NULL&&T->rightchild==NULL){
   			sum++;		}		Count(T->leftchild);		Count(T->rightchild);	}	return sum;}int main(){
   	BitTree T;	CreateBitTree(T);	PreOrderTraverse(T);	cout<