[C语言]链式二叉树insert 和 find 操作

天道酬勤，每日记点笔记也是蛮有意思的。

插入函数：

#include <assert.h>
#include <stdio.h>
#include <malloc.h>

typedef TREE_TYPE int;

typedef struct TREE_NODE{
  TREE_TYPE value;
  struct TREE_NODE *left;
  struct TREE_NODE *right;
}TreeNode;

static TreeNode *tree;

/*
  insert
*/
void insert(TREE_TYPE value){
  TreeNode *current; //point to the current node
  TreeNode **linked; //pointer pointing to another pointer

  linked = &tree;
  // as we know,left node is less than mid, and mid bigger than right
  // left < mid < right
  while( (current = *linked) != NULL ){
      if(current->value > value){
        linked = &current->left;
      }else{
        assert(value != current->value);
        linked = &current->right;
      }
  }
  /*
      now find which position to insert the node 
      because of the node is left ,means the end 
  */
  current = (TreeNode *)malloc(sizeof(TreeNode));
  assert(current != NULL);//guarantee The memory alloced never be NULL
  current->value = value;
  current->left =NULL;
  current->right = NULL;
  *linked = current;
}

find函数相对来说简单一些：

TREE_TYPE *find(TREE_TYPE value)
{
  TreeNode *current;      //this time ,just use one simple pointer
  current = tree;

  // notice node and child relation : left < mid < right
  while(current != NULL && current->value != value){
      if(value < current->value)
            current = current->left
      else
            current = current->right
  }
  
  // not find
  if(current == NULL)  return NULL;

  return &current->value;  // return a pointer means you can change it!
}

前序（pre-order）遍历，即先遍历当前中间节点，后遍历左节点和右节点。这里使用递归比较合适：

notice : pre-order / in-order / post-order / breadth-first

static void do_pre_order_traverse(TreeNode *current,void (*callback)(TREE_TYPE value)){
  if(current != NULL){
      callback(current->value);  //do something with mid item
      
      do_pre_order_traverse(current->left);//do something with left item
      do_pre_order_traverse(current->right);//do something with right item
  }
}
void pre_order_traverse(void (*callback)(TREE_TYPE value)){
  do_pre_order_traverse(tree,callback);
}