Thread: Finding parents in a general tree

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    Finding parents in a general tree

    I'm making a general tree structure (unlimited number of children), and in some of my functions, I need to determine if a node has a parent. The problem is the nodes don't link back to their parents. Given this, what would be a good method of finding a node's parent?

    When I picture the tree structure, I don't see any node not having a parent unless it is the root node, so to check if a node has a parent or not, would all I have to do is compare the node in question to the root node? Is it that simple?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Well, this is just a guess, so take it for what it's worth.

    Assuming that you got to any given node by searching down the tree to get there, you can always pass the a pointer to the current node as a parent parameter to your search call. On the initial call, you would pass NULL. So you can always test for the root by checking for NULL. That way you will have the parent pointer during search operations, but you don't have to permenantly store it in the data structure.

    Hopefully this helps?
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Yes, that is good idea, but looking at my task at hand, I don't think I need to actually refer to the parent node, just see if it has a parent. In which case all nodes in a tree have to have a parent (except the root node), right?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Is it that simple?
    If a non-root node has no parent then you're dealing with a free tree, which is likely a graph. If it's not a graph then it's likely to be a forest. If you want to be truly general then no, it's not that simple. If you just want a tree with potentially more than two children then yes, it is that simple:
    Code:
    bool has_parent ( node *root, node *item )
    {
      return root == item;
    }
    My best code is written with the delete key.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Yes, if its possible to compare it to the root then all you need to do is say if its not the root then it has a parent.

    [edit] beaten by Prelude [/edit]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM