How to create a c/c++ tree script?

Question

How to create a script to :

compare two trees,

in c/c++ in a non recursive mode?

also,

How to create a script in c/c++ to verify if a tree is binary, in a non recursive mode?

thanks in advance.

Answer 1

First of all, in C/C++ you don't write scripts. you write programs and compile them with a compiler.

You can simulate any recursive algorithm by explicitly managing a stack data structure. So assuming you know who do to something recursively, you can also do it iterativly.

Verifying that a tree is "binary" doesn't really have alot of meaning in C++. In C++, every node of a binary tree has something like a left pointer and a right pointer. To end up with a binary tree you need to desing your data structure to be a binary tree.

If you have a general tree that can have any number of children and you want to verify that every node has <= 2 children, simply iterate over all of the nodes, recursivly or iterativly and check that the children count is <= 2.

Answer 2

To compare two binary trees, you have to visit (traverse) every node and compare the contents. You should also compare the quantity of nodes also (this may be faster if the tree header has a variable containing the number of nodes).

Without recursion, you will have to remember parent nodes when you traverse subtrees. A convenient structure for this is a stack. One method is to push the current node onto the stack, traverse left subtree, pop node, traverse right subtree.

Search the web for some examples, "traverse binary tree". I like the web pages that display diagrams versus the all text ones. :-)