\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
Terceira Lista de Exerc\'\i cios  -- Entrega: 19 de abril
\end{center}

\begin{enumerate}

\item
Descreva uma representação de árvores (não necessariamente binárias). \\
a. Escreva um método {\tt ImprimePorNivel()} \\
b. Escreva um método {\tt Elemento MaiorGrau()} que retorna o elemento de
maior grau. 

\item 
Escreva um programa que recebe a lista de nós de uma árvore binária 
quando percorrida em in-ordem e pré-ordem e devolve a árvore. 

\item 
Dada uma \'arvore bin\'aria $T$, discuta a implementa\c c\~ao mais eficiente 
poss\'\i vel e fa\c ca um algoritmo para as seguintes opera\c c\~oes: \\
a. Dados dois elementos $u$ e $v$, acha o primeiro ancestral comum de $u$ e $v$. \\
b. Determinar a altura de $T$. \\
c. Dado um elemento $u$, achar todas as folhas descendentes de $u$. 

\item 
Considere uma árvore de busca binária com os elementos $1,2,\dots,1000$. As
seqüências a seguir poderiam ser a seqüência de nós visitados quando estamos
procurando o nó 374? \\
a. 423 -- 118 -- 256 -- 450 -- 354 -- 375 -- 374 \\
b. 423 -- 231 -- 394 -- 300 -- 350 -- 382 -- 374

\item 
Considere uma árvore de busca binária contendo números inteiros. \\
a. Escreva um método que recebe dois inteiros $x$ e $y$ e imprime todos os nós
da árvore que têm conteúdo $z$ com $x \le z \le y$. \\
b. Qual a complexidade de sua função? Justifique. \\
 
\item 
a. Escreva uma descrição da classe ArvoreBB, que implementa uma árvore de
busca binária. \\
b. Escreva um método {\tt int ContaNos()} que devolve o número de nós de uma
árvore de busca binária. \\
c. Escreva um método {\tt Elemento AchaKesimo(int k)} que devolve o $k$-ésimo
menor elemento da árvore, sem utilizar um vetor auxiliar. 
\end{enumerate}
\end{document}