数据结构----认识树和二叉树

数据结构----认识树和二叉树

树和二叉树是计算机科学中重要的数据结构，它们提供了一种分层的组织方式，并被广泛应用于各个领域。本篇博客将介绍树的概念、结构，以及二叉树的特殊形式，以帮助读者对树和二叉树有更深入的理解。

1. 什么是树？

树是一种非线性的数据结构，由节点组成，呈现出类似于自然界中的树的形状。树的顶部节点称为根节点，根节点可以有零个或多个子节点，每个子节点也可以有零个或多个子节点，依此类推。没有子节点的节点称为叶节点。树中的节点可以有任意多个子节点。

2. 树的结构

在树中，节点之间的关系可以用图论中的边来表示。一个节点可以有零个或多个子节点，子节点与父节点之间的关系称为父子关系。除了根节点外，每个节点都有且只有一个父节点。通过这种方式，我们可以将树看作是节点之间以层次关系组成的层次结构。

3. 二叉树的特殊形式

二叉树是树的一种特殊形式，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的一个重要特点是，每个节点的左子树和右子树本身也是二叉树。二叉树可以是空树，即没有任何节点的二叉树，或者是具有一个根节点和一些子节点的非空树。

4. 树和二叉树的应用

树和二叉树在计算机科学中有广泛的应用。它们被用于构建高效的搜索和排序算法，例如二叉搜索树和红黑树。树和二叉树还被用于构建数据结构，例如堆和哈夫曼树。此外，在数据库和文件系统中，树和二叉树也有着重要的应用。它们为数据的组织和快速搜索提供了有效的手段。

树的基本术语

根结点（Root）：树中的特殊结点，没有父结点，是树的起始点。

结点的度（Degree）：结点拥有的子树的个数。

树的度：树的度是指树中所有结点中度数的最大值。

叶子结点（Leaf Node）：度为0的结点，即没有子结点的结点,也称为终端结点.

内部结点（Internal Node）：度不为0的结点，即至少有一个子结点的结点，也被称为分支结点（Branch Node）

树的深度（Depth of Tree）：指的是树中结点的最大层次数，也就是从根结点到最深层结点的路径的长度。在树结构中，每个结点都位于某一层次上，根结点位于第一层，其子结点位于第二层，依此类推。

二叉树的高度 ：从根结点到最远叶结点所经过的边的数量。

结点的深度：从根结点到该结点所经过的边的数量。

结点的高度：从距离该结点最远的叶结点到该结点所经过的边的数量。

边：连接两个结点的线段，即结点引用（指针）。

双亲结点（Parent Node）：双亲结点指的是某个结点的直接上级结点，即该结点的父结点。在一棵树中,除了根结点外，每个结点都有且仅有一个双亲结点。

兄弟结点（Sibling Node）：兄弟结点指的是具有相同父结点的结点，即位于同一层次的结点。如果两个结点具有相同的双亲结点，它们就是兄弟结点。例如，在一棵二叉树中，同一层次上的左右子结点就是兄弟结点。

子结点（Child Node）：子结点指的是某个结点的直接下级结点，即该结点的子树的根结点。如果一个结点有子结点，那么这个结点就是子结点的双亲结点。

堂兄弟结点（Cousin Node）：堂兄弟结点指的是具有相同祖父结点但是父结点不同的结点。换句话说，堂兄弟结点是具有相同高度但是不在同一个双亲结点下的结点。例如，父结点的兄弟结点的子结点就是堂兄弟结点。

祖父结点（Grandparent Node）：祖父结点指的是某个结点的父结点的父结点，即该结点的双亲结点的双亲结点。祖父结点是结点的祖先结点之一。

后代结点（Descendant Node）：后代结点指的是某个结点的所有子孙结点，包括直接子结点、孙子结点、曾孙结点等等。一个结点的所有后代结点都属于该结点的子树中。

结点的祖先（Ancestor Node）：结点的祖先是指从根结点到该结点路径上的所有结点，包括该结点的父结点、祖父结点、曾祖父结点等等。

结点的子孙（Descendant Node）：结点的子孙是指从该结点开始，通过该结点的所有后代结点。这些后代结点包括直接子结点、孙子结点、曾孙结点等等。

有序树：每个结点的子结点之间有明确的顺序关系。有序树通常用于需要按照特定顺序组织数据的场景，例如文件系统的目录结构。

无序树：结点的子结点之间没有明确的顺序关系。对于每个结点而言，它的子结点是无序的，而子结点之间的顺序不影响树的结构。无序树通常用于不需要特定顺序的数据组织，例如XML文档中的元素之间的关系。

森林：森林是m(m>=0)棵互不相交的树的集合。把根结点删除，树就变成了森林。给森林的各子树加上一个双亲结点，森林就变成了树（树一定是森林，森林不一定是树）。森林是一个树的集合，其中每棵树都是互相独立的，没有共同的结点。森林结构可以由多个根结点的树组成，每棵树都是一颗独立的子树。森林结构常见于需要组织多个独立数据集合的场景，例如数据库中的索引结构。

树结构和线性结构的比较

树结构：

树结构是一对多的关系

每个结点可以有零个或多个子结点

树结构中的第一个结点（根结点）没有前驱结点（双亲结点）

叶子结点（可以有多个）没有后继结点

树可以表示层次化的数据关系，例如家谱、组织结构等。

线性结构：

线性结构是一对一的关系
第一个数据元素无前驱
最后一个数据元素无后继
线性结构可以表示顺序存储或者顺序访问的数据，例如数组、链表、栈、队列等。

二叉树

为什么要研究每个结点只有两个叉的树？

简单性：二叉树的结构相对简单，每个结点最多只有两个子结点，易于理解和实现。任何树都可与二叉树相互转换

高效性：二叉树的结构简单，许多基于二叉树的算法和数据结构具有高效性。例如，二叉搜索树的查找、插入和删除操作的时间复杂度都是O(log n)，非常高效。

​

1. 什么是二叉树？

二叉树是由节点组成的层次结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。树的顶部节点称为根节点，没有子节点的节点称为叶节点。二叉树的一个重要特点是，每个节点的左子树和右子树本身也是二叉树。

2. 二叉树的结构

在C语言中，我们可以使用结构体来表示二叉树节点。一个典型的二叉树节点结构包含以下几个成员：

struct BTNode {
    int data;             // 节点存储的数据
    struct BTNode* left;  // 左子节点指针
    struct BTNode* right; // 右子节点指针
};

3.二叉树的特点

• 每个节点最多有两个子节点：二叉树中的每个节点最多可以有两个子节点，一个是左子节点，另一个是右子节点。这使得二叉树的结构相对简单。

• 子节点的顺序是有序的：当一个节点拥有两个子节点时，通常约定左子节点比右子节点小（或者大，取决于具体的应用场景）。这个约定的顺序可以帮助我们在二叉树中进行快速的搜索和排序操作。

• 类似于递归定义：一个二叉树可以被递归定义为一个根节点加上两个子二叉树。也就是说，每个节点都可以看作是一个二叉树的根节点，它有自己的左子树和右子树。

• 二叉树的遍历方式多样化：二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。这些遍历方式将树的节点按照不同的顺序进行访问，可以用来处理树中的节点。

• 平衡二叉树的特殊性：平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过1。这种平衡性质可以确保在插入和删除节点时，树的高度保持较小，从而保证树的查询和操作效率较高。

满二叉树是一种特殊的二叉树，其中除了最后一层外的每一层都恰好有满的节点数，并且最后一层的节点从左到右连续排列。换句话说，满二叉树是一棵深度为d的二叉树，其中每一层都有2^(d-1)个节点。

满二叉树的节点数可以通过以下公式计算：N = 2^d - 1，其中N表示满二叉树的节点数，d表示满二叉树的深度。例如，深度为3的满二叉树共有2^3 - 1 = 7个节点。

满二叉树具有一些特点：

1. 每个非叶子节点都有两个子节点（左子节点和右子节点）。
2. 深度为d的满二叉树总共有2^d - 1个节点。
3. 由于每个节点都有两个子节点，因此满二叉树的高度为log₂(N + 1)，其中N是节点数。
4. 满二叉树是一种紧凑的二叉树，即在给定节点数的情况下，满二叉树的深度最小。

满二叉树在一些算法和数据结构中有重要的应用，例如堆排序和哈夫曼树。它的特点使得它易于计算和操作，并且在某些情况下可以提供更高效的算法执行。

完全二叉树也是一种特殊的二叉树，它除了最后一层可能不满之外，其他层都是满的，并且最后一层的节点都尽量靠左排列。

完全二叉树的特点包括：

1. 所有层次除了最后一层，都是满的：也就是说，完全二叉树从根节点到倒数第二层的所有层次都是满的，每一层都有2^k个节点，其中k表示层次的索引。
2. 最后一层尽量靠左排列：最后一层从左到右依次添加节点，并且不能有空缺的节点。如果最后一层不满，则只有最右边连续的几个位置可以是空的。
3. 节点数与深度的关系：设完全二叉树深度为d，节点数为N，则有d-1层的节点数为2^{(d-1)-1，最后一层的节点数为N-(2}(d-1)-1)。

完全二叉树在实际应用中具有以下特点和优势：

1. 存储空间利用率较高：相比于一般的二叉树，完全二叉树以紧凑的形式存储，不会出现左右子节点不对齐的情况，从而节省了存储空间。
2. 方便的数据索引：由于完全二叉树的节点位置有特定的规律，可以轻松地通过数组或列表来表示和访问完全二叉树中的节点，进而优化查找和排序算法。
3. 堆的实现：完全二叉树常用于堆的实现，通常用于高效地进行优先级队列相关操作，例如最大堆或最小堆。
4. 算法效率：完全二叉树的结构较为简单，对于一些基于二叉树的算法和操作，其时间复杂度较低，提高了算法效率。

二叉树的存储方式

顺序存储

二叉树的顺序存储是一种将二叉树的节点按照某种顺序依次存储在数组或列表中的方法，以便于对二叉树进行简单而高效的表示和操作。

在顺序存储中，通常采用数组来表示二叉树。具体的存储方式如下：

1. 对于二叉树中的每个节点，可以使用数组中的一个元素来存储它的值。
2. 如果某个节点的索引为i（从1开始），则它的左子节点的索引为2i，右子节点的索引为2i+1。
3. 如果节点的索引为i，则它的父节点的索引为i/2（向下取整）。

这种存储方式的特点包括：

1. 方便的索引和访问：由于节点在数组中的位置有明确的规律，因此可以通过简单的计算就能够找到任意节点的位置，从而方便了对二叉树的遍历和操作。
2. 紧凑的存储结构：相比于链式存储结构，顺序存储使用数组表示二叉树，不需要额外的指针空间，因此存储空间利用率更高。
3. 存储效率高：由于数组的存取效率较高，因此顺序存储方式在一些操作上具有较高的效率，例如快速的节点查找、更新和删除等。

然而，顺序存储也存在一些限制和缺点：

1. 对于非完全二叉树，会造成数组中存在大量的空间浪费。
2. 插入和删除节点可能需要进行数组的扩展或者移动操作，导致时间复杂度较高。
3. 不适用于动态变化的树结构，因为数组的大小通常是固定的。

链式存储

二叉树的链式存储是一种通过节点间的指针链接来表示二叉树的存储方式。在链式存储中，每个节点包含一个数据域和两个指针域，分别指向其左子节点和右子节点（如果存在）。这种存储方式通常使用节点对象或结构体来实现。

具体来说，每个节点包含以下信息：

1. 数据域：用于存储节点的值或数据。
2. 左子节点指针：指向当前节点的左子节点。
3. 右子节点指针：指向当前节点的右子节点。

如果某个节点没有左子节点或右子节点，则相应的指针域可以为空（NULL或nil）。

链式存储的特点包括：

1. 灵活性：相比于顺序存储，链式存储适用于任意形状的二叉树，无需预先确定数组大小。
2. 动态性：链式存储可以动态地添加或删除节点，而不需要移动其他节点，因为节点之间的连接是通过指针来实现的。
3. 空间利用率低：相比于顺序存储，链式存储需要额外的指针空间，可能会占用更多的存储空间。
4. 操作灵活：链式存储在插入、删除和查找等操作上可能比顺序存储更加灵活和高效。

链式存储通常通过树的根节点来访问整棵树，然后通过节点的指针域来遍历树的各个部分。常见的树遍历算法，如前序遍历、中序遍历和后序遍历，都可以通过递归或迭代的方式在链式存储的二叉树上实现。

总的来说，链式存储是一种常见且灵活的二叉树存储方式，适用于各种形状和结构的二叉树，具有动态性和操作灵活性的优势，但可能会占用更多的存储空间。

二叉树的遍历

1. 前序遍历（Preorder Traversal）：
   • 访问顺序：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
   • 应用：可用于创建表达式树、复制树等。
   • 示例：如果树的结构为：根-左-右，则前序遍历的结果为"根-左-右"。
2. 中序遍历（Inorder Traversal）：
   • 访问顺序：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
   • 应用：可用于对二叉搜索树进行排序输出。
   • 示例：如果树的结构为：左-根-右，则中序遍历的结果为"左-根-右"。
3. 后序遍历（Postorder Traversal）：
   • 访问顺序：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
   • 应用：可用于释放二叉树的内存。
   • 示例：如果树的结构为：左-右-根，则后序遍历的结果为"左-右-根"。

这三种遍历方式都是深度优先遍历（Depth-First Traversal）的一种，因为它们都是优先访问节点的子节点，直到达到最深的节点，然后再回溯到上一级节点进行遍历。前中后其实指的就是中间结点的遍历顺序，只要记住前中后序指的就是中间结点的位置就可以了。

代码实现（递归）：

// 二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 前序遍历
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    printf("%d ", root->data);  // 访问根节点
    preorderTraversal(root->left);  // 前序遍历左子树
    preorderTraversal(root->right);  // 前序遍历右子树
}

// 中序遍历
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    inorderTraversal(root->left);  // 中序遍历左子树
    printf("%d ", root->data);  // 访问根节点
    inorderTraversal(root->right);  // 中序遍历右子树
}

// 后序遍历
void postorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    postorderTraversal(root->left);  // 后序遍历左子树
    postorderTraversal(root->right);  // 后序遍历右子树
    printf("%d ", root->data);  // 访问根节点
}

代码实现（迭代）：

// 前序遍历
void PreorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    struct TreeNode* stack[1000];  // 假设二叉树节点数量不超过1000
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        struct TreeNode* node = stack[top--];
        printf("%d ", node->data);  // 访问根节点
        
        // 先将右子节点入栈，再将左子节点入栈，保证左子节点先出栈
        if (node->right != NULL)
            stack[++top] = node->right;
        if (node->left != NULL)
            stack[++top] = node->left;
    }
}

// 中序遍历
void InorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    struct TreeNode* stack[1000];  // 假设二叉树节点数量不超过1000
    int top = -1;
    struct TreeNode* curr = root;
    
    while (curr != NULL || top >= 0) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        curr = stack[top--];
        printf("%d ", curr->data);  // 访问根节点
        curr = curr->right;
    }
}

// 后序遍历
void PostorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;
    
    struct TreeNode* stack[1000];  // 假设二叉树节点数量不超过1000
    int top1 = -1;  // 第一个栈，用于存储遍历顺序为根-右-左
    int top2 = -1;  // 第二个栈，用于将第一个栈的元素倒序输出
    stack[++top1] = root;
    
    while (top1 >= 0) {
        struct TreeNode* node = stack[top1--];
        stack2[++top2] = node;  // 将节点压入第二个栈
        
        // 先将左子节点入栈，再将右子节点入栈，保证右子节点先出栈
        if (node->left != NULL)
            stack[++top1] = node->left;
        if (node->right != NULL)
            stack[++top1] = node->right;
    }
    
    // 输出第二个栈中的节点，即后序遍历结果
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->data);
    }
}

• 访问路径相同，访问结点时机不同

• 每个结点经过三次

  第一次经过时访问 = 先序遍历

  第二次经过时访问 = 中序遍历

  第三次经过时访问 = 后序遍历
  

• 时间复杂度为 O(n) ：所有结点被访问一次，使用 O(n) 时间。

• 空间复杂度为O(n) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2个结点，占用 O(n) 空间。

其他操作：

// 二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点
struct TreeNode* insertNode(struct TreeNode* root, int data) {
    if (root == NULL) {
        // 如果树为空，则创建一个新节点作为根节点
        root = createNode(data);
    } else {
        // 递归插入节点
        if (data < root->data) {
            root->left = insertNode(root->left, data);
        } else {
            root->right = insertNode(root->right, data);
        }
    }
    return root;
}

// 查找节点
struct TreeNode* searchNode(struct TreeNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    } else {
        return searchNode(root->right, data);
    }
}

// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    } else if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // 找到要删除的节点
        if (root->left == NULL && root->right == NULL) {
            // 情况1：删除的节点没有子节点
            free(root);
            root = NULL;
        } else if (root->left == NULL) {
            // 情况2：删除的节点只有一个右子节点
            struct TreeNode* temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL) {
            // 情况3：删除的节点只有一个左子节点
            struct TreeNode* temp = root;
            root = root->left;
            free(temp);
        } else {
            // 情况4：删除的节点有两个子节点
            struct TreeNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}

// 寻找最小节点
struct TreeNode* findMin(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

总结

通过本篇博客，我们介绍了树的概念、结构，以及二叉树的特殊形式。树和二叉树在算法和数据结构中的应用广泛，对于问题的分层处理和组织具有重要意义。

希望本篇博客对读者理解和使用树和二叉树有所帮助。谢谢阅读！