Binary Tree/Recursion

This is a discussion on Binary Tree/Recursion within the C Programming forums, part of the General Programming Boards category; Hi, i'm trying to write a function to find the rightmost leaf node (a node with no children). This is ...

  1. #1
    Young C n00b
    Join Date
    Jul 2006
    Posts
    59

    Binary Tree/Recursion

    Hi, i'm trying to write a function to find the rightmost leaf node (a node with no children).

    This is the code I have so far.
    Code:
    #include "tree.h"
    
    void inorder(BTREE root);
    
    int main()
    {
    
    
    
    
    
            return 0;
    }
    
    void inorder(BTREE root)
    {
            if (root != NULL)
            {
                    inorder(root -> left);
                    printf("%c ", root -> d);
                    inorder(root -> right);
            }
    }
    
    /*BTREE findRightMostLeaf(BTREE root)
    {
            if (root != NULL)
            {
                    findRightMostLeaf(root -> right)
                    if()
            }
    
    }*/
    
    void replaceWithRightmost(BTREE root)
    {
            root = findRightMostLeaf(root);
    }
    in file tree.h
    Code:
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef   char   DATA;
    
    struct node {
       DATA          d;
       struct node   *left;
       struct node   *right;
    };
    
    typedef   struct node   NODE;
    typedef   NODE          *BTREE;
    I can figure out how to solve this problem with a bunch of messy if statement/loop code, but I was looking for a recursive solution, similar to the function already defined in main.

    Recursion is my weakness. Thanks for any help.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    If I'm a leaf, return me (how do you check if I'm a leaf?)
    if not, return a call to get the rightmost leaf of my right child.
    if I don't have a right child, but I'm not a leaf, what do you do (special case)?

  3. #3
    Young C n00b
    Join Date
    Jul 2006
    Posts
    59
    Very clever Perspective =)

    How's this look?

    Code:
    BTREE findRightMostLeaf(BTREE root)
    {
            if (root != NULL)
            {
                    if((root -> left == NULL) && (root -> right)) //node is a leaf
                            return root;
                    else if((root -> left != NULL) && 
                               (root -> right))           &&
                               (root -> left -> right != NULL))
                            return findRightMostLeaf(root -> left -> right);
    
                    else
                            return findRightMostLeaf(root -> right);
            }
    
    }

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Your test seems a bit too complex - I'm pretty sure you don't need to do all those tests multiple times [you may get more if-statements, but as long as you don't repeat things in each if-statement, that's fine].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    It looks like it wouldn't compile.
    You should get some error along the lines of "Not all code paths return a value".

    Your middle case is wrong, you're trying to skip a level of recursion. Just pass the left child. Afterall, you want it to work in a case like this right...
    Code:
             H
         /       \
      B             M
                  /
                 L
                /
               J
    Here the answer should be J.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Young C n00b
    Join Date
    Jul 2006
    Posts
    59
    Ok.. i'm getting there but i've hit a snag. When I print out the results, nothing comes out for the data of the switched node.

    Here's the updated source..

    ex32.c
    Code:
    #include "tree.h"
    
    void inorder(BTREE root);
    BTREE   create_tree(DATA a[], int i, int size);
    void replaceWithRightmost(BTREE root);
    
    int main()
    {	
       BTREE   t;
       DATA    a[]  = "ABCDEFGHIK";
       int     size = 10;                                   /* size of a[] */
    
       t = create_tree(a, 0, size);
       replaceWithRightmost(t);
    
    	return 0;
    }
    
    void inorder(BTREE root)
    {
    	if (root != NULL)
    	{
    		inorder(root -> left);
    		printf("&#37;c ", root -> d);
    		inorder(root -> right);
    	}
    }
    
    BTREE findRightMostLeaf(BTREE root)
    {
    	if (root != NULL)
    	{
    		if((root -> left == NULL) &&
    		   (root -> right == NULL)) //it's a leaf
    			return root;
    		else if((root -> right == NULL) &&
    			(root -> left != NULL))
    			return findRightMostLeaf(root -> left);
    		else
    		findRightMostLeaf(root -> right);		
    	}
    }
    
    void replaceWithRightmost(BTREE root)
    {
    	printf("\n\n%c replaced with ", root -> d);
    	root = findRightMostLeaf(root);
    	printf("%c.\n\n", root -> d);
    }
    tree.h
    Code:
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef   char   DATA;
    
    struct node {
       DATA          d;
       struct node   *left;
       struct node   *right;
    };
    
    typedef   struct node   NODE;
    typedef   NODE          *BTREE;
    
    /*
    // Function prototypes.
    */
    
    BTREE   create_tree(DATA a[], int i, int size);
    BTREE   init_node(DATA d1, BTREE p1, BTREE p2);
    BTREE   new_node(void);
    
    void    inorder(BTREE root);
    void    preorder(BTREE root);
    void    postorder(BTREE root);
    create.c
    Code:
    #include "tree.h"
    
    /*
    // Create a linked binary tree from an array.
    */
    
    BTREE create_tree(DATA a[], int i, int size)
    {
       if (i >= size)
          return NULL;
       else
          return (init_node(a[i],
                            create_tree(a, 2 * i + 1, size),
                            create_tree(a, 2 * i + 2, size)));
    }
    
    /*
    // Initialize a node in a binary tree.
    */
    
    BTREE init_node(DATA d1, BTREE p1, BTREE p2)
    {
       BTREE   t;
    
       t = new_node();
       t -> d = d1;
       t -> left = p1;
       t -> right = p2;
       return t;
    }
    
    /*
    // Create a new node.
    */
    
    BTREE new_node(void)
    {
       BTREE   t;
    
       t = (BTREE) malloc(sizeof(NODE));
       assert(t != NULL);
       return t;
    }

    Output:
    Code:
    [fl76a06@cisweb ex32]$ ./ex32
    
    
    A replaced with
    .
    
    [fl76a06@cisweb ex32]$

  7. #7
    Young C n00b
    Join Date
    Jul 2006
    Posts
    59
    *Bump* Plz help. This is due today =(

  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,543
    Error:
    Warning 2 warning C4715: 'findRightMostLeaf' : not all control paths return a value 42
    Should probably return NULL if not found.

    Code:
    BTREE create_tree(DATA a[], int i, int size)
    {
    	if (i >= size)
    		return NULL;
    	else
    		return (init_node(a[i],
    		create_tree(a, 2 * i + 1, size),
    		create_tree(a, 2 * i + 2, size)));
    }
    create_tree is misleading. It's actually PART of the if, but one can't be sure if it is or not.
    I propose you put brackets around that else and indent create_tree (both lines) by one to signify it's a multiline command.
    It's also very confusing - I would just use a hard-coded value or a loop or something. Very confusing.
    Also just rewrite that function or get rid of it, because it's so very confusing. Create a tree a more normal way.

    But insteado of:
    Code:
    BTREE findRightMostLeaf(BTREE root)
    {
    	if (root != NULL)
    	{
    		if((root -> left == NULL) &&
    			(root -> right == NULL)) //it's a leaf
    			return root;
    		else if((root -> right == NULL) &&
    			(root -> left != NULL))
    			return findRightMostLeaf(root -> left);
    		else
    			findRightMostLeaf(root -> right);		
    	}
    	return NULL;
    }
    How about just:
    Code:
    BTREE findRightMostLeaf(BTREE root)
    {
    	if (root == NULL) return NULL; /* Not found */
    	if ( (root->left == NULL) && (root -> right == NULL) ) return root;
    	if (root->right != NULL) return findRightMostLeaf(root->right); /* If the root->right isn't empty, then search it. */
    	if (root->left != NULL) findRightMostLeaf(root->left);	/* Is root->left isn't empty, then search it */
    	return NULL;
    }
    As for your bug... can it be something like:
    Code:
    BTREE findRightMostLeaf(BTREE root)
    {
    	if (root != NULL)
    	{
    		if((root -> left == NULL) &&
    			(root -> right == NULL)) //it's a leaf
    			return root;
    		else if((root -> right == NULL) &&
    			(root -> left != NULL))
    			return findRightMostLeaf(root -> left);
    		else
    			return findRightMostLeaf(root -> right);		
    	}
    	return NULL;
    }
    Perhaps?
    Last edited by Elysia; 12-14-2007 at 07:22 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Young C n00b
    Join Date
    Jul 2006
    Posts
    59
    YES!! Solved!! Thank you so much Elysia! The problem was the missing return statement. Sometimes I just need someone to look at my code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  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. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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