[计算机的那些事]算法-二叉树

common.h 为常用的头文件，代码实现了add、show。

#include "common.h"

typedef struct tree_node TNode;
struct tree_node{
    int data;
    struct tree_node *left;
    struct tree_node *right;
};

TNode *tree_init(int value)
{
    TNode *node = NULL;
    node = (TNode *)malloc(sizeof(TNode));
    if(!node){
        printf("head malloc failed\n");
        goto err;
    }
    node->data = value;
    node->left = NULL;
    node->right = NULL;

err:
    return node;
}

int tree_add(TNode *root ,TNode *node)
{
    TNode *head = root;
    TNode *cur = head;
    while(cur){
        if(node->data < cur->data){
            //left
            if(!(cur->left)){
                cur->left = node;
                break;
            }
            cur = cur->left;
        }else{
            //right
            if(!(cur->right)){
                cur->right = node;
                break;
            }
            cur = cur->right;
        }
    }

    return 0;
}
#define ARRAY_MAX 40
TNode *array[ARRAY_MAX];

void tree_init_right()
{
    int i = 0;
    while(i < ARRAY_MAX){
        array[i++] = NULL;
    }
}
TNode *tree_get_right()
{
    int i = -1;
    TNode *rt = NULL;
    while(!array[++i]){
        if(i >= ARRAY_MAX){
            return NULL;
        }
    }

    rt = array[i];
    array[i] = NULL;
    return rt;
}

void tree_set_right(TNode *pointer)
{
    int i = 0;
    while(i < ARRAY_MAX){
        if(!array[i]){
            array[i] = pointer;
            break;
        }
        i++;
    }
}
void tree_show(TNode *root)
{
    TNode *head = root;
    TNode *cur = head;
    tree_init_right();

    while(cur){
        printf("data:[%d]\n" ,cur->data);
        if(cur->left){
            tree_set_right(cur->right);
            cur = cur->left;
        }else if(cur->right){
            tree_set_right((cur->left));
            cur = cur->right;
        }else{
            cur = tree_get_right();
            if(!cur){
                goto out;
            }
        }
    }
out:
    return;
}
int main(void)
{
    TNode *head = NULL;
    TNode *node = NULL;
    int value[10] = {6,7,2,1,4,3,8,10,9,5};
    int i = 1;

    head = tree_init(value[0]);
    if(!head){
        goto err;
    }

    while(i < 10){
        node = tree_init(value[i]);
        if(!node){
            goto err;
        }

        tree_add(head ,node);
        i++;
    }
    tree_show(head);
    return 0;

err:
    printf("err msg\n");
    return -1;
}