Thread: preorder traverse

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    preorder traverse

    Hi ; can someone please explain to me the preorder recursive traverse?
    I'm not accepting the idea that the root of the tree could be not just the first root on the whole tree, it might be also be a root of the subtree ...so how one tree could have many roots? isn't the term root mean the first root on the whole tree? or it could be different when we talk ib recursive?

    thanks alot

  2. #2
    Banned
    Join Date
    Apr 2015
    Posts
    596
    I'm confused about term "root" , is in't it mean just the first root of the whole tree? if so then how preorder consider every sub-tree is a new root? and how PC knows that's now we have sub-tree .. ?

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,085
    Quote Originally Posted by RyanC
    I'm confused about term "root" , is in't it mean just the first root of the whole tree? if so then how preorder consider every sub-tree is a new root?
    Every non-empty tree has a root. A subtree is a tree, so it has a root different from the root of the overall tree.

    Quote Originally Posted by RyanC
    and how PC knows that's now we have sub-tree .. ?
    It's not the "PC". It's you writing the code such that you keep track of the root of each subtree, e.g., in a recursive function it could be a parameter.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    Every non-empty tree has a root. A subtree is a tree, so it has a root different from the root of the overall tree.
    So how is that done? I mean how the PC/SOFTWARE know we are in subtree so it's a tree etc .. I mean how the PC thinks like us?! how the PC knows that we are now in a new subtree so we have new tree?

    who said that every subtree is a tree? how do you make that conclusion ?


    those really the gap I'm facing through my learning on preorder and inorder and postorder, so it would be really appreciated if you could help me to understand them.
    I'm really stuck in understanding how is subtree is a tree .. and how the PC knows that at every call we have new "tree/subtree" ! ?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,085
    Quote Originally Posted by RyanC
    So how is that done? I mean how the PC/SOFTWARE know we are in subtree so it's a tree etc .. I mean how the PC thinks like us?! how the PC knows that we are now in a new subtree so we have new tree?
    Usually, a recursive function written to work with tree wouldn't "know" it is dealing with a subtree, and it shouldn't have to: it just handles a tree, and if it so happens that a subtree was passed to it, great! Still works either way.

    Quote Originally Posted by RyanC
    who said that every subtree is a tree? how do you make that conclusion ?
    That's by definition of "subtree": The tree which is a child of a node.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Banned
    Join Date
    Apr 2015
    Posts
    596
    thanks alot

  7. #7
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Laser , I really still a lil confused and lemme explain what's confusing me to help me up (I really struggle that)
    lets say I have fully tree with node X yeah? I call a function by node X so the root is X .. yup? that's fine!!!
    in another time I called one of the child of node X lets say it's y, so if I call a function with node y, the new root is y, my question why "y" called new root?! I mean how does the PC know now I've new root? and how he's assign it as root and not a node?! here is my problem/gap !!!

    thanks in advance for your help, I'm not kidding or something , that's really struggling me!

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,085
    Quote Originally Posted by RyanC
    lets say I have fully tree with node X yeah? I call a function by node X so the root is X .. yup? that's fine!!!
    in another time I called one of the child of node X lets say it's y, so if I call a function with node y, the new root is y, my question why "y" called new root?! I mean how does the PC know now I've new root? and how he's assign it as root and not a node?!
    Let's consider a concrete example: a binary tree denoted by a pointer to its root node, and a simple recursive function for computing the height of the binary tree:
    Code:
    struct node
    {
        struct node *left;
        struct node *right;
    };
    
    size_t compute_height(struct node *root)
    {
        if (!root)
        {
            return 0;
        }
    
        size_t left_subtree_height = compute_height(root->left);
        size_t right_subtree_height = compute_height(root->right);
        return 1 + ((left_subtree_height > right_subtree_height) ? left_subtree_height : right_subtree_height);
    }
    So, we see that in the compute_height function, the root parameter is initially called with the root of the overall tree. But wait, if the tree is not empty, we call compute_height(root->left). In this recursive call, the compute_height function's argument is root->left, which means that the parameter root in this recursive call corresponds to the argument root->left, i.e., from the perspective of this recursive function call, root->left is the root of the tree. This tree is actually a subtree, but from the perspective of the recursive function call, it might as well be the overall tree.

    That's the key to recursive thinking here: a subtree is a tree, so whatever can be done with a tree, can be done with a subtree. A tree has a root; a subtree has a root. What's the height of a binary tree? 0 if the tree is empty, otherwise it's 1 + the height of the taller of its two subtrees. How do we compute the height of the subtrees? They are trees, so recursively apply this function to compute the height of a tree, i.e., for one recursive call, the root is the root of the left subtree, and for the other recursive call, the root is the root of the right subtree.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Very helpful and straight forward! thanks alot!!!! I appreciate your help to me!

    for the term "tree" is actually a nodes that linking between each other ! so every node we can call it a tree!
    and PC isn't know of tree, he just knows nodes and data .. I just was thinking that there's a configuration in pc called "TREE"

  10. #10
    Banned
    Join Date
    Apr 2015
    Posts
    596
    So basically tree is a subset of NODES!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recriating a bst tree from preorder
    By cfan in forum C Programming
    Replies: 4
    Last Post: 08-04-2009, 04:22 AM
  2. constarcting tree from its preorder,inorder..
    By transgalactic2 in forum C Programming
    Replies: 2
    Last Post: 04-17-2009, 01:05 PM
  3. Print Tree Preorder
    By enisxisi in forum C Programming
    Replies: 10
    Last Post: 01-10-2007, 05:04 PM
  4. Preorder Traversal
    By AmazingRando in forum C Programming
    Replies: 17
    Last Post: 10-29-2003, 03:22 AM
  5. how to do the preorder N Postorder?? (Pascal)
    By razoblade in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 11-16-2001, 04:52 AM

Tags for this Thread