二叉树的增加,删除

二叉树的增加:
插入数据x，从根节点开始，不断比较节点与x的大小;
若x小于节点，下一次比较x与节点的左子树，反之，比较x与节点的右子树;
直到遇到一个空的节点，插入数据.
二叉树的删除分三种情况:

  1. 删除的节点为叶子节点: 直接删除;
  2. 删除节点为单子节点: 则子节点继承(替代)位置;
  3. 删除节点为双子节点:
    1. 找左右节点树中最接近节点值的节点(删除节点的左子树找最右值 or 右子树找最左值);
    2. 清除选中节点的原有联系;
    3. 替换所要删除节点的位置关系;
#include "stdlib.h"
#include "stdio.h"
#include "string.h"

typedef int element_type;

typedef struct tree_node {
    element_type element;
    struct tree_node *left_child, *right_child;
    //struct tree_node *parent;
} tree_node_t;

tree_node_t *tree_node_insert_child(tree_node_t* node, element_type element)
{
    if (node == NULL) {
        return NULL;
    }

    tree_node_t* new_node;

    while (1) 
    {
        if (element > node->element) {
            if (node->right_child) {
                node = node->right_child;
            }
            else {
                new_node = (tree_node_t *)malloc(sizeof(tree_node_t));
                new_node->element = element;
                new_node->left_child = NULL;
                new_node->right_child = NULL;
                node->right_child = new_node;
                printf("add %d as %d is right child\n", new_node->element, node->element);
                return new_node;
            }
        }
        else if (element < node->element) {
            if (node->left_child) {
                node = node->left_child;
            }
            else {
                new_node = (tree_node_t *)malloc(sizeof(tree_node_t));
                new_node->element = element;
                new_node->left_child = NULL;
                new_node->right_child = NULL;
                node->left_child = new_node;
                printf("add %d as %d is left child\n", new_node->element, node->element);
                return new_node;
            }
        }
        else {
            /* equal */
            printf("%d has exist at tree\n", node->element);
            return node;
        }
    }
}

tree_node_t *tree_node_delete_left_child(tree_node_t* node)
{
    if (node == NULL || node->left_child == NULL) {
        return node;
    }

    tree_node_t* del_node = node->left_child;

    if (del_node->left_child && del_node->right_child) {
        //find rightest child of del node's left side, or leftest child of del node's right side
        tree_node_t* near_node = del_node->right_child;
        tree_node_t* near_node_parent = del_node;
        while (near_node->left_child) {
            near_node_parent = near_node;
            near_node = near_node->left_child;
        }
        if (near_node_parent != del_node)
        {
            /* clear near node's parent */
            if (near_node->right_child) {
                //if near_node has right child, add to his parent
                near_node_parent->left_child = near_node->right_child;
            }
            else {
                near_node_parent->left_child = NULL;
            }
            /* near node place as del node */
            near_node->right_child = del_node->right_child;
            near_node->left_child = del_node->left_child;
            node->left_child = near_node;
        }
        else {
            //near_node->right_child keep
            near_node->left_child = del_node->left_child;
            node->left_child = near_node;
        }
    }
    else if (del_node->left_child) {
        node->left_child = del_node->left_child;        
    }
    else if (del_node->right_child) {
        node->left_child = del_node->right_child;
    }
    else {
        node->left_child = NULL;
    }

    free(del_node);
    return node;
}

tree_node_t *tree_node_delete_right_child(tree_node_t* node)
{
    if (node == NULL || node->right_child == NULL) {
        return node;
    }

    tree_node_t* del_node = node->right_child;

    if (del_node->left_child && del_node->right_child) {
        //find rightest child of del node's left side, or leftest child of del node's right side
        tree_node_t* near_node = del_node->left_child;
        tree_node_t* near_node_parent = del_node;
        while (near_node->right_child) {
            near_node_parent = near_node;
            near_node = near_node->right_child;
        }
        if (near_node_parent != del_node)
        {
            /* clear near node's parent */
            if (near_node->left_child) {
                //if near_node has right child, add to his parent
                near_node_parent->right_child = near_node->left_child;
            }
            else {
                near_node_parent->right_child = NULL;
            }
            /* near node place as del node */
            near_node->right_child = del_node->right_child;
            near_node->left_child = del_node->left_child;
            node->right_child = near_node;
        }
        else {
            //near_node->left_child keep
            near_node->right_child = del_node->right_child;
            node->right_child = near_node;
        }
    }
    else if (del_node->left_child) {
        node->right_child = del_node->left_child;        
    }
    else if (del_node->right_child) {
        node->right_child = del_node->right_child;
    }
    else {
        node->right_child = NULL;
    }

    free(del_node);
    return node;
}

tree_node_t *creat_tree()
{
    tree_node_t *node;
    element_type element;

    scanf("%d", &element);
    node = (tree_node_t *)malloc(sizeof(tree_node_t));
    node->element = element;
    node->left_child = NULL;
    node->right_child = NULL;

    printf("creat root %d\n", element);

    while(1) {
        scanf("%d", &element);
        if (element == 0) break;
        tree_node_insert_child(node, element);
    }

    return node;
}

#define MAX(a, b) ((a) > (b)? (a): (b))
int get_tree_depth(tree_node_t *root)
{
    if (root == NULL) return 0;
    int left_depth = get_tree_depth(root->left_child);
    int right_depth = get_tree_depth(root->right_child);
    return MAX(left_depth,right_depth) + 1;//child depth + cur depth 1
}

static int print_pos_x;
static int print_tree_high;

#define ELMENT_PRINT_SPACE  (8)
#define ELMENT_PRINT_OFFSET(m,l)  (((m) - (l)) / 2)
#define ELMENT_PRINT_MAX_DEPTH  (6)
#define CALC_PRINT_ELMENT_TAKE_PLACE(l,x) ((1 << (l - 1)) * x + x)
#define ELMENT_PRINT_MAX_DEPTH_SPACE  CALC_PRINT_ELMENT_TAKE_PLACE(ELMENT_PRINT_MAX_DEPTH, ELMENT_PRINT_SPACE)
char print_buffer[ELMENT_PRINT_MAX_DEPTH][ELMENT_PRINT_MAX_DEPTH_SPACE];

void print_core_tree(tree_node_t* node, int level)
{
    if (node == NULL) {
        print_pos_x += ELMENT_PRINT_SPACE * (print_tree_high - level) ;
        return;
    }

    print_core_tree(node->left_child, level + 1);
    char str_element[10];
    sprintf(str_element, "%8d", node->element);
    int len = strlen(str_element);
    memcpy(&print_buffer[level][print_pos_x + ELMENT_PRINT_OFFSET(ELMENT_PRINT_SPACE, len)], str_element, len);
    print_pos_x += ELMENT_PRINT_SPACE;
    print_core_tree(node->right_child, level + 1);
}

void print_tree(tree_node_t* root)
{
    if (root == NULL) return;

    int i,j;
    print_pos_x = ELMENT_PRINT_SPACE / 2;
    print_tree_high = get_tree_depth(root);
    if (print_tree_high > ELMENT_PRINT_MAX_DEPTH) {
        printf("warning: only support %d depth\n", ELMENT_PRINT_MAX_DEPTH);
    }

    for (i = 0; i < ELMENT_PRINT_MAX_DEPTH; i++)
    {
        for (j = 0; j < ELMENT_PRINT_MAX_DEPTH_SPACE; j++)
        {
            print_buffer[i][j] = 0x7f;    
        }
    }
    print_core_tree(root, 0);

    for (i = 0; i < print_pos_x; i++) printf("=");
    printf("\n");
    for (i = 0; i < print_tree_high; i++)
    {
        for (j = 0; j < print_pos_x; j++)
        {
            if (print_buffer[i][j] == 0x7f) printf(" ");
            else printf("%c", print_buffer[i][j]);            
        }
        printf("\n");
    }
    for (i = 0; i < print_pos_x; i++) printf("=");
    printf("\n");
}

int main(int argc, char* argv[])
{
    tree_node_t *root;
    root = creat_tree();
    print_tree(root);
    tree_node_delete_left_child(root);
    print_tree(root);
    tree_node_delete_right_child(root);
    print_tree(root);
    getchar();
}

运行结果图


prefix2suffix.jpg
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容