树, 树的遍历, 树的数据结构

admin管理员组

文章数量:1794759

树, 树的遍历, 树的数据结构

数组,链表,树,图是我们平常接触最基础的数据结构,而且他数据结构基本都是通过这几个数据结构组合使用的结果,例如我们经常提到的 MySQL 索引使用的 B+ 树就是多叉树和链表的结合题, 而这几种基本的数据结构,如果不使用指针其实根本没有办法感受这几种数据结构的原理,所以这里就是用 C 语言来实现几种简单的数据结构.

树

数据结构中的树其实非常简单,就是类似金字塔从树干到树的下层.

上图就是一个简单的二叉树的结构,我们可以用 c 语言简单写一个小如何表示.

代码语言：c代码运行次数：0运行复制

struct Tree{
    int value;
    Tree *left;
    Tree *right;
}*tree;

二叉树的遍历

二叉树遍历分为层序遍历和深度遍历,对应就是深度搜索和广度搜索,其中深度搜索有包含前序遍历后序遍历和中序遍历,就是遍历根节点的顺序不同,这里只写一个前序遍历.

show me the code

前序遍历

代码语言：c代码运行次数：0运行复制

void frontedSearch(tree node){
    if (node == NULL){
        return ;
    }
    printf("%d\n  ", node->value);
    frontedSearch(node->left);
    frontedSearch(node->right);
}

代码较为简单就是两个递归的事情.

层序遍历

层序遍历需要使用队列, 由于 c 语言没有现有的队列,因此我们使用 c++里的 queue 头文件

代码语言：c++复制

void BranchSearch(tree node){
    if (node == NULL){
        return ;
    }
    queue<*Tree> q;
    q.push(node);
    while(!q.empty()){
        tree q1 = q.pop();
        printf("%d\n", q1->value);
        if(q1->left != NULL){
            q.push(q1->left);
        }
        if(q1->right != NULL){
            q.push(q1->right);
        }
    }
}

树的变形

树的数据结构中除了二叉树,还有很多其他的树,以及在一些开发过程中我们希望使用的往往是具有某些特性的树,从而使得树发挥最大的作用.

二叉查找树

二叉查找树是一种特定的二叉树,一棵树节点的左子树小于节点,右节点是大于当前节点的值.

二叉查找树基本操作也就是那种增删查之类的.

show me the code

代码语言：c代码运行次数：0运行复制

<!--查找操作-->
tree find(tree node, int data){
    tree p = node;
    while (p != NULL){
        if (data < p->value){
            p = p -> left;
        }else if(data > p->value){
            p = p -> right;
        }else{
            return p;
        }
    }
    return NULL;
}

<!--删除操作-->
// 删除操作也比较简单,就是讲二叉树右节点最小值顶替当前位置即可
void delete(tree node, int data){
    // 当前节点
    tree p = node;
    // 父节点
    tree father = NULL;
    // 查找需要删除的节点和其父节点
    while(p != NULL && p->value != data){
        father = p;
        if (data > p->value) p = p->right;
        p = p->left;
    }
    if (p == NULL) return ;
    
    // 如果需要删除的节点没有子节点
    if(p -> left == NULL && p-> right == NULL){
        if(father == NULL) node = NULL;
        if(father -> left == p) father->left = NULL;
        father->right = NULL;
    }
    // 如果删除的节点只有一个子节点
    if(p -> left == NULL && p -> right != NULL){
        if (father == NUL) {
            node = p->right;
        }
        if (father->left == p) father->left = p->right;
        father->right = p->right;
    }
    if(p -> left != NULL && p -> right == NULL){
        if (father == NULL) {
            node = p->left;
        }
        if (father->left == p) father->left = p->left;
        father->right = p->left;
    }
    if(p -> left != NULL && p -> right != NULL){
        tree minNode = p -> right;
        tree fatherMin = p;
        while(minNode->left != NULL){
            fatherMin = minNode;
            minNode = minNode -> left;
        }
        p->value = minNode -> value;
        fatherMin -> left = NULL;
    }
    
}

上述删除操作为了逻辑清晰有部分代码重复.

平衡二叉树和递归树

另外两种比较常见的二叉树就是平衡二叉树,其中最知名的就是红黑树,关于红黑树的操作较为复杂,这里就不写代码实现了,而递归树就是我们使用递归的时候逻辑图,虽然实际上的是通过每个函数的栈地址不断跳转实现,但是其中实现远离可以类似一个树状结构.

关于树的变形其实还有很多,今天只是最简单的一部分,后续结合我们操作的话一个是结合对应算法操作,另外就是实现一下对应数据结构的操作代码.

本文标签： 树树的遍历树的数据结构