2chalianbiao.txt

最简单的算法集

二叉链表的结构定义

#include <stdio.h>
#include <stdlib.h>

 

typedef struct tree
{
    void *data_p;  //兼容所有类型
    struct tree *left;
    struct tree *right;
}tree_t;
 

初始化一个节点, 初值置为data

int tree_make_node(tree_t **root, void *data)
{
    *root = (tree_t*) malloc(sizeof(tree_t));
    if(*root == NULL)
    {
        printf("malloc error\n");
        return -1;
    }
    (*root)->left = NULL;
    (*root)->right = NULL;
    (*root)->data_p = data;
    return 0;
}
 

将new_node插入树中作为where_to的左孩子, 返回新插入结点的指针

tree_t* tree_insert_left(tree_t *new_node, tree_t *where_to)
{
    if(new_node != NULL)
    {
        tree_t *tmp;
        tmp = where_to->left;
        where_to->left = new_node;
        new_node->left = tmp;
    }
    return new_node;
}

 

将new_node插入树中作为where_to的右孩子, 返回新插入结点的指针

tree_t* tree_insert_right(tree_t *new_node, tree_t *where_to)
{
    if(new_node != NULL)
    {
        tree_t *tmp;
        tmp = where_to->right;
        where_to->right = new_node;
        new_node->right = tmp;
    }
    return new_node;
}
 

删除entry结点的左，右子树

void tree_del_left(tree_t *entry)
{
    entry->left = NULL;
    free(entry);
}

void tree_del_right(tree_t *entry)
{
    entry->right = NULL;
    free(entry);
}
 

 

前序遍历二叉树

void tree_pre_order(tree_t *root)
{
    if(root != NULL)
    {
        VISIT(root);
        tree_pre_order(root->left);
        tree_pre_order(root->right);
    }
}

/*
非递归思路： 先遍历左子树，遍历过程中
那个访问遍历结点，并将其入栈，返回时
退出当前栈顶元素遍历其其右子树
*/

void tree_pre_order_norec(tree_t *root)
{
      tree_t *stack[MAX_ELE];
      int top = 0;

      while(root != NULL || top != 0)
      {
          if(root != NULL)
          {
              VISIT(root);
              stack[top++] = root; //入栈

              root = root->left;
          }
          else
          {
              root = stack[--top]; //出栈

              root = root->right;
          }
      }
}

 

 

中序遍历二叉树

void tree_in_order(tree_t *root)
{
    if(root != NULL)
    {
        tree_in_order(root->left);
        VISIT(root);
        tree_in_order(root->right);
    }
}

/*
非递归思路： 先遍历左子树，并将遍历结点入栈，返回时
退出当前栈顶元素并访问，再遍历其其右子树
*/

void tree_in_order_norec(tree_t *root)
{
    tree_t *stack[MAX_ELE];
    int top = 0;

    while(root != NULL || top != 0)
    {
        if(root != NULL)
        {
            stack[top++] = root;
            root = root->left;
        }
        else
        {
            root = stack[--top];
            VISIT(root);
            root = root->right;
        }
    }
}