一道阿里巴巴笔试题--二叉树
发布于 2014-10-12 01:37:57 | 249 次阅读 | 评论: 0 | 来源: 网友投递
阿里巴巴
阿里巴巴（中国电子商务公司） 即 阿里巴巴集团 。
阿里巴巴集团经营多元化的互联网业务，致力为全球所有人创造便捷的交易渠道。自成立以来，阿里巴巴集团建立了领先的消费者电子商务、网上支付、B2B网上交易市场及云计算业务，近几年更积极开拓无线应用、手机操作系统和互联网电视等领域。
题目:
写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。
完整的二叉树建立，先序遍历，中序遍历，后序遍历，统计叶子结点个数，输出叶子结点，输出结点最大值，最小值，以及最大值与最小值的差。
参考答案:
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef char DataType_char;
typedef int DataType_int;
typedef struct Node
{
DataType_int data;
struct Node *LChild;
struct Node *RChild;
}BiTNode,*BiTree;
void Visit(DataType_int a)//输出各节点
{
cout<<a<<" ";
}
//先序建立二叉树
BiTree InitTree()
{
DataType_char ch;
BiTree T;
cin>>ch;
if(ch=='.') T=NULL;//空结点用'.'代替
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch-'0';
T->LChild=InitTree();
T->RChild=InitTree();
}
return T;//返回根节点
}
void PreOrder(BiTree root)//先序遍历
{
if(root!=NULL)
{
Visit(root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
void InOrder(BiTree root)//中序遍历
{
if(root!=NULL)
{
InOrder(root->LChild);
Visit(root->data);
InOrder(root->RChild);
}
}
void PostOrder(BiTree root)//后序遍历
{
if(root!=NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root->data);
}
}
//先序遍历输出二叉树的叶子结点,root为指向二叉树根结点的指针
void Pre_Leaf(BiTree root)//求叶子结点
{
if(root!=NULL)
{
if((root->LChild==NULL)&&(root->RChild==NULL))
{
Visit(root->data);
}
Pre_Leaf(root->LChild);
Pre_Leaf(root->RChild);
}
}
int Pre_Leaf_Value(BiTree root)//求叶子结点个数
{
static int count=0;
if(root!=NULL)
{
if((root->LChild==NULL)&&(root->RChild==NULL))
{
count++;
}
Pre_Leaf_Value(root->LChild);
Pre_Leaf_Value(root->RChild);
}
return count;
}
int Max(BiTree root)//返回最大值
{
static int max;
static int i=0;
if(root!=NULL)
{
if(i==0)
{
max=root->data;
i++;
}
if(root->data>max)
max=root->data;
Max(root->LChild);
Max(root->RChild);
}
return max;
}
int Min(BiTree root)//返回最小值
{
static int min;
static int i=0;
if(root!=NULL)
{
if(i==0)
{
min=root->data;
i++;
}
if(root->data<min)
min=root->data;
Min(root->LChild);
Min(root->RChild);
}
return min;
}
int Max_Min(BiTree root)//求最大值与最小值的差
{
static int min,max,i=0;
if(root!=NULL)
{
if(i==0)
{
min=root->data;
max=root->data;
i++;
}
if(root->data>max)
max=root->data;
if(root->data<min)
min=root->data;
Max_Min(root->LChild);
Max_Min(root->RChild);
}
return max-min;
}
int main()
{
BiTree T;
T=InitTree();
cout<<"二叉树的先序遍历:";
PreOrder(T);
cout<<endl;
cout<<"二叉树的中序遍历:";
InOrder(T);
cout<<endl;
cout<<"二叉树的后序遍历:";
PostOrder(T);
cout<<endl;
cout<<"先序遍历输出二叉树的叶子结点:"<<endl;
cout<<"个数："<<Pre_Leaf_Value(T)<<endl;
Pre_Leaf(T);
cout<<endl;
cout<<"结点最大的值:"<<Max(T)<<endl;
cout<<"结点最小的值:"<<Min(T)<<endl;
cout<<"最大结点与最小结点的差:"<<Max_Min(T)<<endl;
system("pause");
return 0;
}
