Percurso não recursivo e
impressão em árvores binárias
Drozdek
Implementação Java
Drozdek
Classe usada para ilustração
public class BSTNode {
protected int key;
protected BSTNode left,right;
public BSTNode() {
left = right = null;
}
}
3
Percurso Pré-fixo
public void iterativePreorder() {
BSTNode p = root;
Stack travStack = new Stack();
if (p != null) {
travStack.push(p);
while (!travStack.isEmpty()) {
p = (BSTNode) travStack.pop();
visit(p);
if (p.right != null)
travStack.push(p.right);
if (p.left != null)
// filho da esquerda empilhado
// após o da direita
travStack.push(p.left);
// para estar no topo da pilha;
}
}
}
4
Percurso Infixo
public void iterativeInorder() {
BSTNode p = root;
Stack travStack = new Stack();
while (p != null) {
while(p != null) {
// empilhar filho da direita (se houver)
if (p.right != null) // e o próprio nó quando for
travStack.push(p.right); // para a esquerda;
travStack.push(p);
p = p.left;
}
p = (BSTNode) travStack.pop();
// pop em nó sem filho esquerdo
while (!travStack.isEmpty() && p.right == null) {
// visita-lo e a todos os nós
visit(p);
// sem filho direito;
p = (BSTNode) travStack.pop();
}
visit(p);
// visitar também o primeiro nó com
if (!travStack.isEmpty()) // um filho direito (se houver);
p = (BSTNode) travStack.pop();
else p = null;
}
5
Percurso Pós-fixo
public void iterativePostorder() {
BSTNode p = root, q = root;
Stack travStack = new Stack();
while (p != null) {
for ( ; p.left != null; p = p.left)
travStack.push(p);
while (p != null && (p.right == null ||
p.right == q)) {
visit(p);
q = p;
if (travStack.isEmpty())
return;
p = (BSTNode) travStack.pop();
}
travStack.push(p);
p = p.right;
}
}
6
Impressão de árvores
public void printTree (int inicio, int incremento)
{
int i;
if(!isEmpty ())
{
right.printTree (inicio + incremento);
for(i = 1; i <= inicio; i++)
System.out.print(" ");
System.out.print(this.key);
left.printTree(inicio + incremento);
} // End if(isEmpty())
} // printTree (int n)
7
Implementação C++
Drozdek
Classe usada para ilustração
template<class T>
class BSTNode {
public:
BSTNode() {
left = right = 0;
}
BSTNode
(const T& el, BSTNode *l = 0, BSTNode *r = 0)
{ key = el; left = l; right = r;
}
T key;
BSTNode *left, *right;};
}
9
Percurso Pré-fixo
template<class T>
void BST<T>::iterativePreorder() {
Stack<BSTNode<T>*> travStack;
BSTNode<T> *p = root;
if (p != 0) {
travStack.push(p);
while (!travStack.empty()) {
p = travStack.pop();
visit(p);
if (p->right != 0)
travStack.push(p->right);
if (p->left != 0)
// filho da esquerda
// emplilhado depois
// do da direita
travStack.push(p->left);
// para ficar no topo da pilha;
}
}
10
}
Percurso Infixo
template<class T>
void BST<T>::iterativeInorder() {
Stack<BSTNode<T>*> travStack;
BSTNode<T> *p = root;
while (p != 0) {
while (p != 0) {
// empilhar filho da direita (se houver)
if (p->right)
// e o próprio nó quando for
travStack.push(p->right); // para a direita;
travStack.push(p);
p = p->left;
}
p = travStack.pop();
// pop em nó sem filho esquerdo
while (!travStack.empty() && p->right == 0) {
// visita-lo e a todos os nós
visit(p);
// sem filho direito;
p = travStack.pop();
}
visit(p);
// visitar também o primeiro nó com
if (!travStack.empty())
// um filho direito (se houver);
p = travStack.pop();
else p = 0;
}
11
}
Percurso Pós-fixo
template<class T>
void BST<T>::iterativePostorder() {
Stack<BSTNode<T>*> travStack;
BSTNode<T>* p = root, *q = root;
while (p != 0) {
for ( ; p->left != 0; p = p->left)
travStack.push(p);
while (p != 0 && (p->right == 0 || p->right == q)) {
visit(p);
q = p;
if (travStack.empty())
return;
p = travStack.pop();
}
travStack.push(p);
p = p->right;
}
}
12
Impressão de árvores
void Tree::PrintTree1(TreeNode *t, short inicio,
short incremento) const
{
int i;
if(t == NULL) return;
PrintTree1(t->right(),inicio + incremento);
for(i = 0; i < inicio; i++)
cout << ' ';
cout << "( " << t->Key() << ", ";
cout << endl;
PrintTree1(t->left(),inicio + incremento);
}
void Tree::PrintTree(void) const
{
PrintTree1(fRoot, inicio, incremento);
}
13