10.Traversing A Binary Tree

spatlou

All queries, discussions, updates and clarifications related to Session 05.Traversing A Binary Treeshould be posted here.

spatlou

spatlou

nirmalpg124

DOUBLE POINTER HERE I'M EXPRESSING A DEEP ROOTED CONCEPT

**tree is a double pointer or array of pointers

pointer notation array notation

*(tree+0) is same as tree[0] // THIS IS ACTUALLY AN ADDRESS NOT A DATA VALUE

if *(tree+0) = NULL

tree[1] = NULL

then

printf( "\n *( tree+0 ): %p", *( tree+0 ) );

printf( "\n tree[1]: %p", tree[1] );

result:

NULL

----------------------------------- -------------------------------- -----------------------------

typedef struct node

{

Node* left;

int data;

Node* right;

}Node;

tree[1]->data will give the value at 1st location in double pointer.

as also depicted in :

typedef struct Item
{
struct Item *next;
void **data;
}Item;

Item* curr->data = (void**)malloc( sizeof(char*)*no_of_reg);

copy_from_user( curr->data[i], ubuff, 1 ); // to kernelspacedataAddress, from UserSpaceDataAddress, sizeofdata

nirmalpg124

Node **tree;

tree = (Node**)realloc(tree, sizeof(Node*)*2);

tree[0] = NULL;

tree[1] = (Node*)creatNode(0);

printf( "children: %p", *(tree+0) );

printf( "children: %p", tree[0] );

printf( "children: %p", *(tree+1) );

printf( "children: %p", tree[1] );

Result:

creatNode: End

children: (nil)children: (nil)children: 0x1ecbae0children: 0x1ecbae0creatTree: End

mohdmohsinkhanee

Yes, you are correct. The expressions *(tree + 0) and tree[0] are equivalent in C.

*(tree + 0) is using pointer arithmetic to calculate the address of the element at index 0 in the array pointed to by tree and then dereferencing that address to get the value.

tree[0] is using the array subscript notation to directly access the value at index 0 in the array pointed to by tree.

nirmalpg124

RAW observ:

typedef struct node

{

Node* parent;

int data;

Node** children;

}Node;

tree[1] = NULL;

tree[1] = (Node*)realloc(tree, sizeof(Node*)); // Node size allocation

tree[1]->children = (Node**)realloc( tree[1]->children, sizeof(Node*)*2 );

then using pointer arithmetic tree[1]->children [0] or tree[1]->children[1] points to NULL after reallocation also.

error : printf( "%s: tree[ %d ]->children[0]:address %p \n", __func__, 2*j+k+i-1 , temp->children[0] ); // used 3 loops i,j,k to reach to a particular node

tree[1]->chlidren[0]->data is not ACCESSIBLE even after entering value for data.

THIS IS BECAUSE THESE TWO HAVE BEEN ALLOCATED MEMORY IN FRAGMENTED WAY.

we have used a double linked list here for memory representation.

THIS IS POSSIBLE ON USE OF 1-D ARRAY INSTEAD OF double LinkedList use.

nirmalpg124

So, a better way is to use a 1-D array for a tree & a double linked list for a BINARY Search Tree.

THE SIMPLICITY LIES IN using left and right nodes for a binary search tree for traversal.

typedef struct node

{

Node* left;

int data;

Node* right;

}Node;

This is an easy way .

nirmalpg124

DELETION IN BST: corrected code

Node* deleteElement( Node* tree, int val)
{
printf("%s:Begin \n", __func__)

Node* cur, *parent, *suc, *psuc, *ptr;
parent = tree;
cur = tree->left;

while( cur!= NULL && val!= cur->data)
{
    parent = cur;
    cur = (val < cur->data)? cur->left : cur->right;
}

if( cur->left == NULL )       // single child node deletion
    ptr = cur->right;
else if( cur->right == NULL )
    ptr = cur->left;
else                          // both child node deletion
{
      // find the in-order successor and its parent
      psuc = cur;
      suc = cur->right;

      while( suc->left != NULL)
      {
          psuc = suc;
          suc = suc->left;
      }

      if( psuc == cur)
      {
          psuc->right = suc->right;
      }
      else
      {
         suc->left = cur->left;
         psuc->left = suc->right;
         suc->right = cur->right;

      }

      ptr = suc;

}

// attach ptr to the parent node
if( parent->left == cur)
    parent->left = ptr;
else
    parent->right = ptr;

free( cur);

return tree;

printf("%s:End \n", __func__);

}

10.Traversing A Binary Tree

Howdy, Stranger!

Categories