Data Structures Part II - Stacks And Trees
Written by Harry Fairhead & Mike James   
Friday, 15 October 2021
Article Index
Data Structures Part II - Stacks And Trees
Queues And Trees
Trees & Recursion

Working With Trees

There is also the small problem of working with trees as part of a program.

Clearly you can't keep on writing out

LeftNode.RightNode.RightNode.LeftNode;

type names to specify a node of your choice – it’s too clumsy. 

What actually happens in practice is that a pointer to a node is used as the “current” node and this moves its way down the tree by being set to the current nodes left or right child:

CurrentNode=CurrentNode.LeftNode;

And so on.

You can generalize this to more than two child nodes.

Generally speaking tree algorithms are all about manipulating a "current node" pointer of some sort to achieve whatever it is you are trying to do - and it this is usually trying to find something stored in one of the tree nodes. 

Searching a tree is mainly a matter of visiting the nodes and seeing what they contain. This is again another area where things can seem complicated because you can ask that every node is visited in a particular order usually to increase the efficiency of the search.

For example going down each branch as far as possible before starting again to go down the next branch is called “depth first”, while visiting all nodes at the same depth before going deeper, is called “breadth first”.

The jargon also gets more impressive - we talk of “traversing the tree” rather than "visiting the nodes" and eventually you will encounter the fact that trees and “recursion” go together.

How do you search a tree - you start at the root node and search its left sub-tree and if that doesn't work you search its right-sub tree. 

As both of the sub-trees are just slightly smaller trees you can see that the search operation is the same for the sub-trees as for the complete tree. Repeat this recipe and you can search a tree without ever really having to write a search method. 

Recursion is a whole topic in its own right and the source of the only good computer science joke I know –

dictionary definition of recursion “Recursion – see recursion”.

What are trees used for?

Well, everything from keeping track of where files are stored on a disk drive to analysing natural language and applications in artificial intelligence. It's worth point out that XML is a data language that can only describe tree structures so the idea must be powerful.

You can't program for long without meeting trees.

If you would like to know more about trees and their associated algorithms then see: Data structures - Trees 

 fig3

Related Articles

Data Structures Part I - From Data To Objects

Data structures - Trees

The LIFO Stack - A Gentle Guide

Advanced Hashing

Variables revisited

Stack architecture demystified

Reverse Polish Notation - RPN

Brackets are Trees

Javascript data structures - Stacks

Storage Mapping Function

 

What Programmers Know

knowcover

Contents

  1. The Computer - What's The Big Idea?*
  2. The Memory Principle - Computer Memory and Pigeonholes*
  3. Principles of Execution - The CPU
  4. The Essence Of Programming
  5. Variables - Scope, Lifetime And More*
  6. Binary Arithmetic
  7. Hexadecimal*
  8. Binary - Negative Numbers*
  9. Floating Point Numbers*
  10. Inside the Computer - Addressing
  11. The Mod Function
  12. Recursion
  13. The Lost Art Of The Storage Mapping Function *
  14. Hashing - The Greatest Idea In Programming
  15. Advanced Hashing
  16. XOR - The Magic Swap*
  17. Programmer's Introduction to XML
  18. From Data To Objects*
  19. What Exactly Is A First Class Function - And Why You Should Care*
  20. Stacks And Trees*
  21. The LIFO Stack - A Gentle Guide*
  22. Data Structures - Trees
  23. Inside Random Numbers
  24. The Monte Carlo Method
  25. Cache Memory And The Caching Principle
  26. Data Compression The Dictionary Way
  27. Dates Are Difficult*
  28. Sequential Storage*
  29. Magic of Merging*
  30. Power of Operators
  31. The Heart Of A Compiler*
  32. The Fundamentals of Pointers
  33. Functional And Dysfunctional Programming*

* Recently revised

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


Virtual Memory

Virtual memory is a way of pretending that your computer has more memory than it really has. But like all good things it comes at a cost. Virtual memory is an example of trading speed for storage.



The Fundamentals of Pointers

Despite the fact that pointers have been long regarded as "dangerous" they are still deeply embedded in the way we do things. Much of the difficulty in using them stems from not understanding where th [ ... ]


Other Articles

<ASIN:0072253592>

<ASIN:032144146X>

<ASIN:3540779779>

<ASIN:0534390803>



Last Updated ( Friday, 15 October 2021 )