树和二叉树知识总结

标签：总结结点遍历知识二叉树 root 节点指针

文章目录

树
二叉树
树和森林

树

树（Tree）和二叉树（Binary Tree）都是重要的数据结构，它们在计算机科学中被广泛应用。

树的定义

树是一种非线性结构，具有以下特点：

结点之间存在分支关系。
结点之间具有层次关系。

树的基本定义如下：

如果树中的结点数为0，则称为空树。
如果树中的结点数大于0，则有且仅有一个特定的结点称为根结点。
其余结点可以分为m(m>0)个互不相交的有限集合T1, T2, T3, …, Tm，每个集合又是一棵树，称为根结点的子树（SubTree）。
树是n个结点的有限集合。

树的其他表示方法

除了基本定义中提到的分支结构，树还可以使用其他方式表示，例如：

树的广义表（Generalized List）是一种用于表示树形结构的数据结构，也称为泛化表或G-表。
```
      A
    / | \
   B  C  D
  / \
 E   F
```
可以用广义表表示为：[A,[B,[E,F],C,D]

层次表示法：按照树的层次关系将结点排列成一行，通过空格或者其他符号来表示结点之间的层次关系。

树的基本术语

根结点（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)，非常高效。

二叉树的定义

二叉树是 n (n≥0) 个结点的有限集，它或者是空集 (n=0) ,或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点

每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
子树有左右之分,次序不能颠倒。即使只有一颗子树，也要进行区分，说明是左子树还是右子树。
二叉树可以使空集合，根可以有空的左子树或空的右子树。

二叉树的抽象数据类型定义

ADT BinaryTree {
    数据对象 D：具有相同特性的数据类型的集合
    数据关系 R：二叉树中每个结点最多有两个子结点，分别称为左子结点和右子结点
    基本操作：
        BinaryTree()：构造函数，创建一个空的二叉树
        preorderTraversal()：前序遍历二叉树
        inorderTraversal()：中序遍历二叉树
        postorderTraversal()：后序遍历二叉树
        isEmpty()：判断二叉树是否为空，若为空则返回 true，否则返回 false
        size()：返回二叉树中结点的个数
        height()：返回二叉树的高度（最大层数）
        insert(data)：插入一个数据元素到二叉树中
        remove(data)：从二叉树中删除指定的数据元素
        search(data)：在二叉树中查找指定的数据元素，若找到则返回 true，否则返回 false
}

二叉树的性质

在二叉树的第 i 层上至多有 2 i − 1 个节点 ( i ≥ 1 ) 在二叉树的第i层上至多有 2 ^ {i-1}个节点(i \geq 1) 在二叉树的第i层上至多有2i−1个节点(i≥1)
至少有 1 个节点至少有 1 个节点至少有1个节点
深度为 k 的二叉树至多有 2 k − 1 个结点 ( k ≥ 1 ) 深度为k的二叉树至多有 2 ^ k-1个结点(k \geq 1) 深度为k的二叉树至多有2k−1个结点(k≥1)
至少有 k 个节点至少有 k 个节点至少有k个节点
对任何一棵二叉树 T ，如果其叶子数 ( 度为 0 ) 为 n 0 ，度为 2 的结点数为 n 2 ，则 n 0 = n 2 + 1 对任何一棵二叉树T，如果其叶子数(度为0)为n_0，度为2的结点数为n_2，则n_0=n_2+1 对任何一棵二叉树T，如果其叶子数(度为0)为n0，度为2的结点数为n2，则n0=n2+1
即叶子数 = 度为 2 的节点数 + 1 即叶子数=度为2的节点数+1 即叶子数=度为2的节点数+1

证明：

二叉树的边数 = 所有结点（除根结点）和其双亲结点，每个结点（除根结点）都有一个双亲结点，且每条边都连接一个结点和其双亲结点。即

B = n − 1 B = n - 1 B=n−1

二叉树的边数 = 度为1结点 * 1 + 度为2结点 * 2，即

B = n 1 ∗ 1 + n 2 ∗ 2 B =n_1 * 1+n_2*2 B=n1∗1+n2∗2

结点数 = 叶子结点数 + 度为1结点数 + 度为2结点数

n = n 0 + n 1 + n 2 n = n_0+n_1+n_2 n=n0+n1+n2
所以

n 0 + n 1 + n 2 − 1 = n 1 ∗ 1 + n 2 ∗ 2 n_0+n_1+n_2-1=n_1*1+n_2*2 n0+n1+n2−1=n1∗1+n2∗2

推出

n 0 = n 1 − 1 n_0=n_1-1 n0=n1−1

为什么要研究满二叉树和完全二叉树？

在顺序存储下可以复原

满二叉树

每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

也可以说，如果一个二叉树的深度为K，且结点总数是 2^k -1 ，则它就是满二叉树。

也可以说，如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

每一层结点都达到最大数量
叶子结点全部在最底层

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同。

在完全二叉树中，除了最底层结点可能没填满外，其余每层结点数都达到最大值，并且最下面一层的结点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个结点。

叶子结点只可能分布在层次最大的两层上
对任意结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1

完全二叉树的性质

具有 n 个结点的完全二叉树的深度为 [ l o g 2 n ] + 1 , [ x ] 为不大于 x 的为最大整数具有n个结点的完全二叉树的深度为[log_2n]+1,[x]为不大于x的为最大整数具有n个结点的完全二叉树的深度为[log2n]+1,[x]为不大于x的为最大整数

完全二叉树中双亲结点编号和孩子结点编号之间的关系

如果对一棵有n个结点的完全二叉树（深度为 [log2n]+1 的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i (1 ≤ i ≤ n)，有:
(1)如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲是结点[i/2]。
(2)如果 2i > n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
(3)如果 2i + 1 > n，则结点i无右孩子；否则，其右孩子是结点2i + 1。

完满二叉树

完满二叉树（full binary tree）除了叶结点之外，其余所有结点都有两个子结点。
在这里插入图片描述

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构通常利用数组实现。在这种结构中，按照从上到下、从左到右的顺序，依次将二叉树的结点存储在数组中。具体的存储方式如下：

对于二叉树中的任意结点，假设其在数组中的索引为i，则其左孩子结点在数组中的索引为2i + 1，右孩子结点在数组中的索引为2i + 2。
如果某个结点没有左孩子或右孩子，则对应位置的索引上存储空值（通常用特殊值如NULL或者-1表示）。

这种存储结构的优点是可以通过简单的计算即可找到任意结点的父结点、左孩子和右孩子，同时不会浪费额外的存储空间。但缺点是当二叉树不是完全二叉树时会造成一定的空间浪费，因为对于有些结点，数组中会存在多个连续的空值。

这种存储结构适合于完全二叉树或满二叉树，而对于普通的二叉树，可能会导致存储空间的浪费。
在这里插入图片描述

链式存储结构

二叉树的链式存储结构是使用链表来表示二叉树的一种方法。在这种存储结构中，每个结点由数据域和两个指针域组成，分别用来指向该结点的左孩子结点和右孩子结点。这种结构的结点通常被称为二叉树结点。

根据指针域的不同，链式存储结构可以分为两种：

二叉链表（Binary Linked List）：每个结点包含两个指针域，分别指向左孩子结点和右孩子结点。在这种结构中，树的根结点可以通过一个指针来表示，而其他结点则通过指针域连接起来形成树的结构。
三叉链表（Ternary Linked List）：除了包含左右孩子指针之外，每个结点还包含一个指向其父结点的指针。这种结构通常用于需要在树中进行双向遍历或者查找结点的父结点时。

typedef struct BinaryTreeNode{
    int data;
    struct BinaryTreeNode *left,*right;
}BiNode;

struct BinaryTreeNode {
    int data;
    struct BinTreeNode* left;
    struct BinTreeNode* right;
    struct BinTreeNode* parent;
}

点击查看图片来源

在n个结点的二叉链表中，有 n+1 个空指针域

每个结点（除根结点）都和双亲结点有一条连线，则不为空指针域为n - 1

所以空指针数目 = 2n - ( n - 1 ) = n + 1

二叉树的遍历

三种遍历方式

前序遍历：在前序遍历中，先访问根结点，然后依次递归地遍历左子树和右子树。因此，遍历顺序是：根结点 -> 左子树 -> 右子树。
中序遍历：在中序遍历中，先递归地遍历左子树，然后访问根结点，最后再递归地遍历右子树。因此，遍历顺序是：左子树 -> 根结点 -> 右子树。
后序遍历：在后序遍历中，先递归地遍历左子树，然后再递归地遍历右子树，最后才访问根结点。因此，遍历顺序是：左子树 -> 右子树 -> 根结点。

前中后其实指的就是中间结点的遍历顺序，只要记住前中后序指的就是中间结点的位置就可以了。

递归实现

/* 前序遍历 */
void preOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：根结点 -> 左子树 -> 右子树
    arr[(*size)++] = root->val;
    preOrder(root->left, size);
    preOrder(root->right, size);
}

/* 中序遍历 */
void inOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：左子树 -> 根结点 -> 右子树
    inOrder(root->left, size);
    arr[(*size)++] = root->val;
    inOrder(root->right, size);
}

/* 后序遍历 */
void postOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根结点
    postOrder(root->left, size);
    postOrder(root->right, size);
    arr[(*size)++] = root->val;
}

访问路径相同，访问结点时机不同
每个结点经过三次

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

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

第三次经过时访问 = 后序遍历
时间复杂度为 O(n) ：所有结点被访问一次，使用 O(n) 时间。
空间复杂度为O(n) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2个结点，占用 O(n) 空间。

非递归实现

中序遍历基本思想：

建立一个栈
根结点进栈，遍历左子树
根结点出栈，输出根结点，遍历右子树。

int InorderTraverse(BiTreeNode *T) {
    StackNode *S;
    BiTreeNode *p;
    InitStack(&S);
    p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            push(&S, p);
            p = p->left;
        } else {
            Pop(&S, &p);
            printf("%c ", p->data);
            p = p->right;
        }
    }
    return 1;
}

层序遍历

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问结点。

层序遍历本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（breadth-first search, BFS），它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

二叉树的层序遍历

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

将根结点进队；
对不空时循环：从队列中出列一个结点*P,访问它 ;
- 若他有左孩子结点，将左孩子结点入队；
- 若他有右孩子结点，将右孩子结点入队；

typedef struct SqQueue{
    BTNode data[MaxSize];
    int front,rear;
}SqQueue;

void LevelOrderTraversal(BTNode *root) {
    if (root == NULL) return;

    SqQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, root);

    while (!QueueEmpty(&Q)) {
        //声明了一个指针node，用来存储从队列中出队的结点指针。
        BTNode *node;
   		//出队一个结点，并将其存储在 node 指针中
        DeQueue(&Q, &node);
        // 访问结点
        printf("%d ", node->data);

        if (node->left) {
            EnQueue(&Q, node->left);
        }
        if (node->right) {
            EnQueue(&Q, node->right);
        }
    }
}

根据遍历序列确定二叉树

若二叉树中割接点的值均不相同，则二叉树结点的先序序列，中序序列，后序序列都是唯一的。
由二叉树的后序序列和中序序列可以确定唯一的一颗二叉树

由先序，后序序列确定根；由中序序列确定左右子树

二叉树的操作

二叉树的建立

按先序遍历序列建立二叉树的二叉链表

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
}BTNode;

BTNode* ConstructTree(BTNode *root) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }

    root = (BTNode*)malloc(sizeof(BTNode));
    root->data = ch;
    
    root->left = ConstructTree(root->left);
    root->right = ConstructTree(root->right);
    return root;
}

// 在主函数中调用
BTNode *root = NULL;
root = ConstructTree(root);

二叉树的销毁

由于二叉树中的每一个节点都是用我们开辟的空间，故销毁二叉树时需要将每个节点都释放。

先递归到最后一层，然后不断向上释放。

void destroyTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    destroyTree(root->left);
    destroyTree(root->right);
    free(root); // 释放当前节点所占用的内存空间
}

二叉树的复制

int Copy(BiTree T, BiTree *NewT) {
    if (T == NULL) {
        *NewT = NULL;
        return 0;
    } else {
        *NewT = (BiTree)malloc(sizeof(BiTNode)); // 为新结点分配内存
        if (*NewT == NULL) {
            return -1; // 内存分配失败
        }
        (*NewT)->data = T->data;
        Copy(T->lchild, &((*NewT)->lchild)); // 传递左子树的地址
        Copy(T->rchild, &((*NewT)->rchild)); // 传递右子树的地址
    }
    return 0; // 操作成功
}

计算二叉树深度

递归计算左子树的深度记为leftDepth，递归计算右子树的深度为rightDepth，二叉树的深度则为leftDepth与rightDepth的较大者加1

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

计算二叉树结点总数

结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1

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

计算二叉树叶子结点数

叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数

int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

线索二叉树

线索二叉树是一种利用空闲的指针域存放线索（即前驱和后继）信息的二叉树。通过线索化，可以在不增加额外空间的情况下，实现对二叉树的快速遍历。

利用空指针域:

如果某个节点的左孩子为空，则将空的左孩子指针指向该节点的前驱。如果某个节点的右孩子为空，则将空的右孩子指针指向该节点的前驱。

这种改变指向的指针称为线索

线索二叉树的标志域通常用于标识节点的左右指针是指向孩子节点还是线索。

在中序线索二叉树中，通常使用两个标志域来表示左右指针的含义：

左线索标志（ltag）：
- 当 ltag 为 0 时，表示左指针指向的是左孩子节点
- 当 ltag 为 1 时，表示左指针指向的是中序遍历时的前驱节点
右线索标志（rtag）：
- 当 rtag 为 0 时，表示右指针指向的是右孩子节点
- 当 rtag 为 1 时，表示右指针指向的是中序遍历时的后继节点

这样，节点结构为：

typedef struct ThreadNode {
    int data;
    struct ThreadNode* left;
    struct ThreadNode* right;
    int lTag, rTag;
} ThreadNode;

在双向线索化的二叉树中增设一个头结点，该头结点满足以下条件：

ltag 置为 0，表示左孩子指向实际的根节点。
rtag 置为 1，表示右孩子指向遍历序列中的最后一个节点。
遍历序列中的第一个节点的 lc 域指向头结点。
遍历序列中的最后一个节点的**rc**域指向头结点。

树和森林

树的表示法

双亲表示法

通过使用一个数组来表示树中的每个节点，并在数组中记录每个节点的父节点信息。

双亲表示法包含以下几个要素：

节点数组： 使用一个数组来存储树中的所有节点。数组的每个元素表示树中的一个节点。
父节点指针： 对于数组中的每个节点，记录其父节点在数组中的下标。如果一个节点是根节点，则其父节点指针为空（通常表示为 -1 或其他特殊值）。

通过双亲表示法，可以方便地找到每个节点的父节点，但查找子节点或兄弟节点则相对麻烦，需要遍历整个节点数组。这种表示方法适用于树的父子关系频繁变化的情况，但不适用于需要频繁查找子节点或兄弟节点的情况。

#define MAX_SIZE 100 // 树中节点的最大数量

// 节点结构
typedef struct TreeNode {
    int data; // 节点数据
    int parent; // 父节点在数组中的下标
}TreeNode;

// 树的结构
struct Tree {
    TreeNode nodes[MAX_SIZE]; // 节点数组
    int size; // 树中节点数
};

孩子链表

把每个节点的孩子节点排列起来，看成是一个线性表，用单链表存储，则n个节点有n个孩子（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。
child

#define MAX_TREE_SIZE 100

typedef int TElemType;   //树结点的数据类型

typedef struct CTNode{      //孩子结点
	int child;          
	struct CTNode * next;              
}*ChildPtr;

typedef struct{              //表头结构
	TElemType data;
	ChildPtr firstchild;                    
}CTBox;

typedef struct{              //树结构
	CTBox nodes[MAX_TREE_SIZE];    //结点数组
	int  r,n;                     //根节点的位置和结点数
}

e9ef3bc4e5b3612b5d581f856fdc88d

孩子兄弟表示法

每个节点除了存储数据外，还存储了指向其第一个孩子节点和其右兄弟节点的指针。

typedef struct TreeNode {
    int data;                  // 节点数据
    struct TreeNode *firstChild;  // 指向第一个孩子节点的指针
    struct TreeNode *nextSibling; // 指向右兄弟节点的指针
} TreeNode;

在这里插入图片描述

树和二叉树的转换

树转换为二叉树

加线：在兄弟之间加一连线
抹线：对每个节点来说，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根节点为轴心，将整树顺时针转45度

兄弟相连留长子

二叉树转换为树

加线：若p节点是双亲节点的左孩子。则将p的右孩子，右孩子的右孩子…沿分支找到的所有的右孩子，由于p的双亲用线连起来
.抹线：抹掉元二叉树中双亲与右孩子的连线
调整：将节点按层次排列，形成树结构

左孩右右联双亲，去掉原来右孩线