Successors and predecessors of a node in binary trees...

This is a discussion on Successors and predecessors of a node in binary trees... within the C Programming forums, part of the General Programming Boards category; HI, What are Successors and predecessors of a node in binary trees? thnx...

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Successors and predecessors of a node in binary trees...

    HI,

    What are Successors and predecessors of a node in binary trees?

    thnx

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    A
    |\
    BC

    I'm not quite sure about these English terms. But if I am correct than A is the predecessor of B and C. And B and C are the successors of A.

  3. #3
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    mmmmmmm but isn't this the same name as to 'parents' and 'children'? A is parent of B and C and B and C are children or child nodes of A ?

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    B and C are the children of A, so A is parent of B and C. I guess successor and predecessor are just other words for child and parent.

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    I am not sure about that, after looking at the code in my book. Maybe u can have a look at the this:
    Code:
    /* A binary tree node with parent pointer. */
    struct pbin_node {
      int data;
      struct pbin_node *left;
      struct pbin_node *right;
      struct pbin_node *parent;
    };
    
    /* A binary tree. */
    struct pbin_tree {
      struct pbin_node *root;
      int count;
    };
    
    /* Returns the next node in in-order in the tree after X, or NULL if X
       is the greatest node in the tree. */
    static struct pbin_node *successor(struct pbin_node *x)
    {
      struct pbin_node *y;
    
      assert(x != NULL);
      if (x->right != NULL) {
        y = x->right;
        while (y->left != NULL)
          y = y->left;
      }
      else {
        y = x->parent;
        while (y != NULL && x == y->right) {
          x = y;
          y = y->parent;
        }
      }
    
      return y;
    }
    The function finds the successor of *x.

    thnx

  6. #6
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    Found these definitions:

    If a node N has a right subtree: The successor of N will be the smallest node in the right subtree of N.

    If a node N has no right subtree: If N is a left child, then the next node visited by the in-order traversal will be the parent of N. But what if N is a right child? Then the in-order traversal will keep going up the tree until it gets to a node for which the previous node is a left child.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 17
    Last Post: 11-16-2006, 09:06 PM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21