---

BinaryTrees.c

Go to the documentation of this file.

/* Binary trees. */

#include <stdlib.h>
#include "LinkedLists.h"

void InsertInTree(BinaryNodePtr theNode, BinaryNodePtr *root,
      SInt8 (*CompareFunction)(NodePtr a, NodePtr b))
{
  BinaryNode **curPos = root;
  while (1) /* Who needs recursion? */
  {
    if (!*curPos)
    {
      *curPos = theNode;
      break;
    }
    else if (CompareFunction((NodePtr)(theNode), (NodePtr)(*curPos)) >= 0)
    {
      curPos = &((*curPos)->right);
    }
    else
    {
      curPos = &((*curPos)->left);
    }
  }
}


BinaryNodePtr SortedDoubleToBinaryWithSize(DoubleNodePtr linkedList, UInt32 size)
{
  UInt32 halfSize = (size >> 1), counter, sizeA, sizeB;
  DoubleNodePtr middleNode;
  
  sizeA = halfSize;
  sizeB = halfSize;
  sizeB -= ((size & 1) ? (0) : (1));
  
  counter = halfSize;
  middleNode = linkedList;
  while (counter--)
    middleNode = middleNode->next;
  
  if (sizeB)
    middleNode->next = /* Or ->right */
    (DoubleNodePtr)(SortedDoubleToBinaryWithSize(middleNode->next, sizeB));
  else
    middleNode->next = (DoubleNodePtr)(0);
  
  if (sizeA)
    middleNode->prev = /* Or ->left */
    (DoubleNodePtr)(SortedDoubleToBinaryWithSize(linkedList, sizeA));
  else
    middleNode->prev = (DoubleNodePtr)(0);
  
  return (BinaryNodePtr)(middleNode);
}

DoubleNodePtr BinaryToDouble(BinaryNodePtr root, UInt8 fillPrev)
{
  IndirectNodePtr list;
  DoubleNodePtr doubleList;
  LeftNodeRight(root, &list);
  ApplyIndirectOnSimple(list);
  if (fillPrev)
    FillPrev((DoubleNodePtr)(list->nodePtr));
  doubleList = (DoubleNodePtr)(list->nodePtr);
  DestroyLinkedList((NodePtr)(list), DestroyIndirectNode);
  return doubleList;
}


IndirectNodePtr* LeftNodeRight(BinaryNodePtr node, IndirectNodePtr *theList)
{
  IndirectNodePtr newNode = malloc(sizeof(IndirectNode));
  if (node->left)
    theList = LeftNodeRight(node->left, theList);
  newNode->nodePtr = (NodePtr)(node);
  newNode->nodeHeader.next = (NodePtr)(0);
  *theList = newNode;
  theList = (IndirectNodePtr*)(&newNode->nodeHeader.next);
  if (node->right)
    theList = LeftNodeRight(node->right, theList);
  return theList;
}


void BalanceTree(BinaryNodePtr *root)
{
  DoubleNodePtr doubleList = BinaryToDouble(*root, 0);
  *root = SortedDoubleToBinary(doubleList);
  /* It's that small! Wow! */
}

---