【C语言】树

╰+哭是因爲堅強的太久メ 2022-06-10 03:06 116阅读 0赞

1、链表的遍历指的是按顺序依次处理链表里面的每个节点  
2、遍历过程中不应该加入/删除新节点，所以在加入或删除的时候应该先将记录指针设置为空  
3、如果线性链式物理结构里每个节点可以找到多个其他节点，它就是树  
4、树状链式物理结构里的节点可以分很多层，不同层之间符合线性规律（任意两层都符合某个顺序）  
5、树的最上面层只有一个节点，叫做树的根节点  
6、可以使用根节点代表整颗树  
7、如果两节点之间存在直接的联系，就说明他们之间是父子关系，其靠近根节点的叫父节点，另外一个叫子节点  
8、任何一个节点只能有一个父节点，可以有多个子节点（根节点没有父节点）  
9、如果每个节点最多只能有两个子节点，这种树叫做二叉树  
10、二叉树是最简单的数，任何一颗树都可以转换成二叉树  
11、二叉树里每个节点的两个子节点有左右之分  
12、二叉树里的每个节点都可以看作是一个二叉树  
13、节点A的左子节点代表的二叉树叫做子节点A三左子树，右边的叫右左子树  
14、树的遍历指按顺序依次处理树里的每个节点  
25、树里的绝大部分操作是通过遍历结实现的  
26、树的遍历通常用递归来实现  
17、遍历树的时候一定先遍历左子树后遍历右  
18、根据根节点处理的时机不同把树分3种：

>     先处理跟节点的叫前序遍历
    >     中间处理根节点的叫中序遍历
    >     最后处理根节点的叫后序遍历
    
    text1-1.h
    /* * 树演示 * */
    #ifndef __TEXT_1_1_H__
    #define __TEXT_3_1_H__
    struct node;//结构体声明
    //这里的两个结构体顺序不能交换，
    typedef struct {
        struct node *p_node;
    } tree;
    
    typedef struct node {
        int num;//根
        tree left;//左
        tree right;//右
    } node;
    
    //初始化函数
    void tree_init(tree *);
    //树的清理函数（后序遍历方式）
    void tree_deinit(tree *);
    //在有序二叉树中查找某个数字的位置
    tree *tree_search(const tree *, int);
    //向有序二叉树加入数字
    void tree_insert(tree *, int);
    //以中序遍历方式处理各节点,从小到大显示
    void tree_miter(const tree *, void (*p_func)(int));
    //前序遍历函数
    void tree_fiter(const tree *, void (*p_func)(int)); 
    //后序遍历
    void tree_liter(const tree *, void (*p_func)(int));
    //从有序二叉树删除一个数字
    //删除一个数字，先要找到这个数的位置->然后判断这个数下面有没有子树，若没有，
    void tree_remove(tree *, int);
    
    int tree_height(const tree *);
    #endif //__TEXT_1_1_H_
    
    
    --------------------------------------------------------------------------------
    text1.c
    
    /* * 树演示 * */
    #include <stdlib.h>
    #include "text1-1.h"
    //初始化函数
    void tree_init(tree *p_tree) {
        p_tree->p_node = NULL;
    }
    //树的清理函数（后序遍历方式）
    void tree_deinit(tree *p_tree) {
        if(!(p_tree->p_node)) {
       //叶子节点是空的，说明到最头了
            return;
        }
        tree_deinit(&(p_tree->p_node->left));//除看叶子是空，其他的都是p_tree->p_node->left
        tree_deinit(&(p_tree->p_node->right));//.......
        free(p_tree->p_node);
        p_tree->p_node = NULL;
    }
    
    //在有序二叉树中查找某个数字的位置
    tree *tree_search(const tree *p_tree, int num) {
        if(!(p_tree->p_node)) {
       //最后返回的都是这里，如果找不到要着的，说明没有这个数，及这个树的地址被返回
                return (tree *)p_tree;
        }
        if(p_tree->p_node->num == num) {
       //如果在根
            return (tree *)p_tree;
        }
        else if(p_tree->p_node->num > num )  {
       //在左子树，左边的都比根小
            return tree_search(&(p_tree->p_node->left), num);
        }
        else{
       //在右子树找，右边的都比跟大
            return tree_search(&(p_tree->p_node->right), num);
        }
    }
    
    //向有序二叉树加入数字
    void tree_insert(tree *p_tree, int num) {
        node *p_node = NULL;
        tree *p_tmp = tree_search(p_tree, num);//每个数的位置都是唯一的
        if(p_tmp->p_node) {
       //如过这个位置有内容
            return;
        }
        p_node = (node *)malloc(sizeof(node));
        if(p_node) {
       //插入新节点就是把它当作根节点来插入
            p_node->num = num;
            p_node->left.p_node = NULL;
            p_node->right.p_node = NULL;
            p_tmp->p_node = p_node;
        }
    }
    
    //以中序遍历方式处理各节点,从小到大显示
    void tree_miter(const tree *p_tree, void (*p_func)(int)) {
       //函数指针
        if(!(p_tree->p_node)) {
            return;
        }
        tree_miter(&(p_tree->p_node->left), p_func);
        p_func(p_tree->p_node->num);
        tree_miter(&(p_tree->p_node->right), p_func);
    }
    
    //前序遍历函数
    void tree_fiter(const tree *p_tree, void (*p_func)(int)) {
       //函数指针
        if(!(p_tree->p_node)) {
            return;
        }
        p_func(p_tree->p_node->num);
        tree_miter(&(p_tree->p_node->left), p_func);
        tree_miter(&(p_tree->p_node->right), p_func);
    }
    
    //后序遍历
    void tree_liter(const tree *p_tree, void (*p_func)(int)) {
       //函数指针
        if(!(p_tree->p_node)) {
            return;
        }
        tree_miter(&(p_tree->p_node->left), p_func);
        tree_miter(&(p_tree->p_node->right), p_func);
        p_func(p_tree->p_node->num);
    }
    
    //从有序二叉树删除一个数字
    //删除一个数字，先要找到这个数的位置->然后判断这个数下面有没有子树，若没有，
    void tree_remove(tree *p_tree, int num) {
        node *p_node = NULL; //用于记录 ？？？？？
        tree *p_tmp = tree_search(p_tree, num);//p_tmp是要删除的那个点的位置
        if(!(p_tmp->p_node)) {
            return;
        }
        p_node = p_tmp->p_node;
    
        if(!(p_node->left.p_node)) {
            //左子树不存在的情况下用右子树的根替换要删除的节点
            p_tmp->p_node = p_node->right.p_node;
        }
        else if(!(p_node->right.p_node)) {
            //右子树不存在的情况用左子树的跟节点替换要删除的节点
            p_tmp->p_node = p_node->left.p_node;
        }
        else {
            //左右子树都存在的要将他们合并成一颗树，然后用合并后的树的根节点替换被删除的节点
            tree *p_tmp1 = tree_search(&(p_node->left), p_node->right.p_node->num);
            p_tmp1->p_node = p_node->right.p_node;//将右子树放在所找到的地方
            p_tmp->p_node = p_node->left.p_node;//然后把左子树的跟加在要删除的节点上
        }
    
        free(p_node);
        p_node = NULL;
    }
    
    //计算树的高度
    int tree_height(const tree *p_tree) {
        int lheight = 0, rheight = 0;
        if(!(p_tree->p_node)) {
            return 0;        
        }
        lheight = tree_height(&(p_tree->p_node->left));//计算所有左子数
        rheight = tree_height(&(p_tree->p_node->right));
        return (lheight >= rheight ? lheight : rheight) + 1;
    }
    
    
    
    --------------------------------------------------------------------------------
    text2.c
    /* * 树测试 * */
    #include <stdio.h>
    #include "text1-1.h"
    void print_cb(int num) {
        printf("%d ", num);
    }
    int main() {
        tree tr = {
       0};
        tree_init(&tr);
       printf("%p \n", tree_search(&tr,30));
        tree_insert(&tr,50);
        tree_insert(&tr,30);
        tree_insert(&tr,80);
        tree_insert(&tr,10);
        tree_insert(&tr,40);
        tree_insert(&tr,65);
        tree_insert(&tr,90);
        tree_insert(&tr,57);
        tree_insert(&tr,73);
        tree_insert(&tr,60);
    
        printf("高度是：%d\n", tree_height(&tr));
    
        tree_remove(&tr, 65);
        tree_remove(&tr, 50);
    
        printf("高度是：%d\n", tree_height(&tr));
    
        tree_miter(&tr, print_cb);
        printf("\n");
        tree_fiter(&tr, print_cb);
        printf("\n");
        tree_liter(&tr, print_cb);
        printf("\n");
        tree_deinit(&tr);
        return 0;
    }