数据结构入门——06树

数据结构入门——06树

引用

CSDN

1.

https://blog.csdn.net/m0_56989421/article/details/141174674

本文是一篇关于数据结构中树和二叉树的入门教程，内容涵盖了树的基本概念、表示方法、二叉树的定义、性质、存储结构以及遍历方法等。文章结构清晰，从基础概念到具体实现逐步展开，适合初学者学习。

1. 树

树（Tree）是一种非线性数据结构，它是n（n≥0）个节点的有限集合，它满足两个条件：

• 有且仅有一个特定的称为根（Root）的节点；
• 其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。树的表示方法：树形表示法、目录表示法。

• 一个节点的子树的个数称为该节点的度数。
• 一棵树的度数是指该树中节点的最大度数。
• 度数为零的节点称为树叶或终端节点。
• 度数不为零的节点称为分支节点。
• 除根节点外的分支节点称为内部节点。

森林：

• 若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为有序树。
• m（m≥0）棵互不相交的树的集合称为森林。
• 树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

2. 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

2.1 兄弟表示法

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};

2.2 双亲表示法

3. 二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树特点

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

3.1 特殊的二叉树

3.1.1 满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

3.1.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。最后一层是连续的，前面的k-1层为满的。满二叉树是一种特殊的完全二叉树。完全二叉树度为1 的，最多有一个。

3.2 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.(等比数列求和1+2+2^2+...+2^h)
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1.
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN.

3.3 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

3.3.1 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

在数组中: 父亲下标为i,左孩子下标为2i+1,右孩子下标为2i+2.

孩子下标为i,父亲下标为(i-1)/2.(不论是左还是右，下标都为整数)

3.3.2 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。

// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* pLeft; // 指向当前节点左孩子
    struct BinTreeNode* pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode比特就业课
{
    struct BinTreeNode* pParent; // 指向当前节点的双亲
    struct BinTreeNode* pLeft; // 指向当前节点左孩子
    struct BinTreeNode* pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};

4. 二叉树链式结构的实现

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

4.1 二叉树链式结构的遍历

• 前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名，为深度优先。

1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——根->左子树->右子树。
2. LNR：中序遍历(Inorder Traversal)——左子树->根->右子树。
3. LRN：后序遍历(Postorder Traversal)——左子树->右子树->根。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

• 层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。为广度优先。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
}BTNode;
BTNode* BuyBTNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    node->data = x;
    node->left = node->right = NULL;
    return node;
}
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyBTNode(1);
    BTNode* node2 = BuyBTNode(2);
    BTNode* node3 = BuyBTNode(3);
    BTNode* node4 = BuyBTNode(4);
    BTNode* node5 = BuyBTNode(5);
    BTNode* node6 = BuyBTNode(6);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}

上述代码创建一个二叉树，如下图所示

4.1.1 前序遍历(A->B->D->NULL->C->F->G)

void PrevOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
![](https://wy-static.wenxiaobai.com/chat-rag-image/328218003240007086)
        return;
    }
    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

4.1.2 中序遍历（D->B->NULL->A->F->C->G）

void InOrder(BTNode* root) {
    if (root == NULL){
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

4.1.3 后序遍历 (D->NULL->B->F->G->C->A)

void PosOrder(BTNode* root) {
    if (root == NULL){
        printf("NULL ");
        return;
    }
    PosOrder(root->left);
    PosOrder(root->right);
    printf("%d ", root->data);
}

4.1.4 二叉树的结点个数

int BTreeSize(BTNode* root) {
    return root == NULL ? 0 :
        BTreeSize(root->left) 
        + BTreeSize(root->right) + 1;
}

4.1.5 第k层的节点的个数，k >= 1

int BTreeKLevelSize(BTNode* root, int k)
{
    assert(k >= 1);
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BTreeKLevelSize(root->left, k - 1)
        + BTreeKLevelSize(root->right, k - 1);
}

4.1.6 求二叉树的深度

int BTreeDepth(BTNode* root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BTreeDepth(root->left);
    int rightDepth = BTreeDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

4.1.7 二叉树查找值为x的结点

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;
    BTNode* ret1 = BTreeFind(root->left, x);
    if (ret1)
        return ret1;
    //return BTreeFind(root->right, x);
    BTNode* ret2 = BTreeFind(root->right, x);
    if (ret2)
        return ret2;
    return NULL;
}

4.1.8 二叉树销毁

void BTreeDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BTreeDestory(root->left);
    BTreeDestory(root->right);
    free(root);
}

4.1.9 层序遍历(需要队列进行入队和出队)

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
    {
        QueuePush(&q, root);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%d ", front->data);
        if (front->left)
        {
            QueuePush(&q, front->left);
        }
        if (front->right)
        {
            QueuePush(&q, front->right);
        }
    }
    printf("\n");
    QueueDestory(&q);
}

4.1.10 判断二叉树是否是完全二叉树

// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
            break;
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        // 空后面出到非空，那么说明不是完全二叉树
        if (front)
        {
            QueueDestory(&q);
            return false;
        }
    }
    QueueDestory(&q);
    return true;
}