Binary Search Tree - Non-recursive traversal

R. E. Donais

Delphi Developer

Sun, 11 Oct 1998 03:00:00 GMT

Binary Search Tree - Non-recursive traversal

Quote

In article <4lk3jl$...@news.nstn.ca> Denis Blondeau wrote:
>Date: Wed, 24 Apr 96 02:23:12 GMT
>From: den...@fox.nstn.ca (Denis Blondeau)
>Newsgroups: comp.lang.pascal.misc
>Subject: Binary Search Tree - Non-recursive traversal

> I am looking for a way to do an ionorder traversal of a Binary
> Search
>Tree (BST), _non-recursively_. I have a pointer implementation of a BST,
> and
>although it is easy to implement with recursion, I am having a hard time
>doing it non-recursively...

> Thanks for your help....

>-> Denis

Hello Denis. In order to traverse a tree you have to be able to return
to the parent nodes. If the child doesn't have a pointer linking back to
the parent, you'll have to implement one - typically done using a stack.
That's why traversing a tree is so easy to do with recursion, because
recursion is a stack operation.

...red

Knowledge is one of the few things that you
can give away and still keep for yourself.

Chris Ryde

Delphi Developer

Mon, 12 Oct 1998 03:00:00 GMT

Re:Binary Search Tree - Non-recursive traversal

Quote

Denis Blondeau wrote:

> I am looking for a way to do an ionorder traversal of a Binary Search
> Tree (BST), _non-recursively_. I have a pointer implementation of a BST, and
> although it is easy to implement with recursion, I am having a hard time
> doing it non-recursively...

This is much easier to achieve if your data structure
tree is doubly linked, that is each node within the
tree has a pointer to it's two children AND to it's
parent. Then the traversal without recursion is quite
easy to implement.

ChrisR:

Other Threads

1. Binary Search Tree - Non-recursive traversal

2. binary search tree

3. Binary Search tree runtime error 103

4. Binary Search Trees

5. Binary Search Tree help needed

6. Information about binary search trees

7. need help in binary search tree - ap.pas (0/1)

8. Binary Search Trees

9. Problem with recursion and binary search trees

10. Binary Search Trees??