//

// Created by mao on 16-9-18.

//

#include "ArrayBinaryTree.h"

#include <assert.h>

#include <stdio.h>

unsigned long leftChild(unsigned long current)

{

    return 2 * current;

}

unsigned long rightChild(unsigned long current)

{

    return  2 * current + 1;

}

void insert(TREE_TYPE value)

{

    int current = 1;

    while(tree[current] != 0 && current < TREE_SIZE){

        if(tree[current] < value){

            current = 2 * current + 1;

        }else if(tree[current] > value){

            current = 2 * current;

        }else {

            //一插入直接返回

            return ;

        }

    }

    assert(current <= TREE_SIZE);

    tree[current] = value;

}

TREE_TYPE *find(TREE_TYPE value)

{

    int current = 1;

    while(tree[current] != 0 && current < TREE_SIZE){

        if(tree[current] < value){

            current = 2 * current + 1;

        }else if(tree[current] > value){

            current = 2 * current;

        }else {

            //找到值

            break;

        }

    }

    assert(current <= TREE_SIZE);

    return (tree + current);

}

//先序遍历

void do_pre_order_traverse(unsigned long current)

{

    if(tree[current] != 0){

        printf("%d ", tree[current]);

        do_pre_order_traverse(leftChild(current));

        do_pre_order_traverse(rightChild(current));

    }

}

//寻找current树下面的最大值的树，返回指向该地址的指针

TREE_TYPE *findMax(unsigned long current)

{

    assert(tree[current] != 0);

    while(tree[current] != 0){

        current = rightChild(current);

    }

    return tree + (current / 2);

}

//寻找最小树

TREE_TYPE *findMin(unsigned long current)

{

    assert(tree[current] != 0);

    while(tree[current] != 0){

        current = leftChild(current);

    }

    return tree + (current / 2);

}

//查找左子树最大节点然后替换，然后删除最大节点

void delete(TREE_TYPE value)

{

    TREE_TYPE *ptr = find(value);

    TREE_TYPE temp;

    //待删除节点的下标

    unsigned long current = ptr - tree;

    if(tree[leftChild(current)] != 0 && tree[rightChild(current)] != 0){

        //如果有两个子树,用左子树最大值替换，然后删除最大值树

        TREE_TYPE *leftMax = findMax(leftChild(current));

        temp = *leftMax;

        //删除最大值然后替换

        delete(temp);

        tree[current] = temp;

    }else if(tree[leftChild(current)] == 0 && tree[rightChild(current)] == 0){

        //如果没有子树

        tree[current] = 0;

    }else{

        if(tree[leftChild(current)] != 0){

            //左子树，最大值树删除，替换

            TREE_TYPE *leftMax = findMax(leftChild(current));

            //删除最大值然后替换

            delete(*leftMax);

            tree[current] = *leftMax;

        }else{

            //只有右子树，右子树最小值替换

            TREE_TYPE *rightMin = findMin(rightChild(current));

            temp = *rightMin;

            delete((temp));

            tree[current] = temp;

        }

    }

}

//

// Created by mao on 16-9-18.

//

#ifndef ARRAYBINARYTREE_H

#define ARRAYBINARYTREE_H

#define TREE_SIZE 100

#define ARRAY_SIZE (TREE_SIZE + 1)

typedef int TREE_TYPE;

static TREE_TYPE tree[ARRAY_SIZE] = {0};

unsigned long leftChild(unsigned long current);

unsigned long rightChild(unsigned long current);

void insert(TREE_TYPE value);

TREE_TYPE *find(TREE_TYPE value);

void delete(TREE_TYPE value);

void do_pre_order_traverse(unsigned long current);

TREE_TYPE *findMax(unsigned long current);

TREE_TYPE *findMin(unsigned long current);

#endif //ARRAYBINARYTREE_H

#include <stdio.h>

#include "ArrayBinaryTree.h"

int main()

{

    insert(20);

    insert(12);

    insert(5);

    insert(9);

    insert(16);

    insert(17);

    insert(25);

    insert(28);

    insert(26);

    insert(29);

    do_pre_order_traverse(1);

    delete(25);

    delete(20);

    printf("\n");

    do_pre_order_traverse(1);

    return 1;

}