树和二叉树的基本概念-数据结构

树的基本概念

树（Tree）是一种非常常见的数据结构，它是由节点（Node）组成的集合，这些节点之间通过边（Edge）相连。树的每个节点有一个称为父节点的节点，除了根节点（Root Node）外，每个节点都有一个或多个称为子节点的节点。根节点是树的顶部节点，它没有父节点。而叶子节点（Leaf Node）是没有子节点的节点。

空树：结点数为0的树

非空树的特性：

1、有且只有一个根结点

2、没有后继的结点称为"叶子结点"或者是"终端结点"

3、有后继的结点称为"分支结点"或者是"非终端结点"

4、 除根节点外，任何一个结点都有且只有一个前驱

5、每个结点可以有0个或多个后继

树是n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：

1、有且仅有一个特定的称为根的结点

2、当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T~1~,T~2~,...,Tm，其中每个集合本身又是一棵树，并且称为根节点的子树。

结点之间的关系描述

祖先结点：一个节点的祖先是沿着从该节点到根节点的路径的所有节点。例如，节点 B 的祖先包括节点 A。

子孙结点：一个节点的子孙节点是沿着从该节点到叶子节点的路径的所有节点。

双亲节点（父节点）：每个节点都有一个父节点，除了根节点外。父节点指向其子节点。如上图所示，节点 A 是节点 B 的父节点，而节点 B 是节点 A 的子节点。

孩子节点：一个节点的后代是沿着从根节点到该节点的路径的所有节点。例如，节点 B 的后代包括节点 E、F、K 和 L。

兄弟节点：有相同父节点的节点之间称为兄弟节点。例如，在节点 B 和节点 C 之间存在兄弟关系，它们都是节点 A 的子节点。

堂兄弟节点：两个节点的堂兄弟节点是它们的父节点的子节点之间的节点，但它们不是兄弟节点。换句话说，堂兄弟节点具有相同的深度，但不共享同一个父节点。

两个节点之间的路径是指连接这两个节点的边的集合。在树结构中，这个路径是唯一的，因为任意两个节点之间都只有一条路径，路径只能从上到下。路径的长度是指这条路径上边的数量，或者等价为节点之间的距离。

结点、树的属性描述

结点的层次（深度）-->从上往下数，默认从1开始

结点的高度 -->从下往上数

树的高度（深度） -->总共多少层

结点的度 -->有几个孩子（分支）

树的度 -->各结点的度的最大值

有序树/无序树

有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换（族谱）

无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换（各省会排序）

树/森林

森林：森林是m(m>0)棵互不相交的树的集合。m可为0，称为空森林。

树的常见性质

1、结点数=总度数+1

2、度为m的树、m叉树的区别

3、度为m的树，第i层至多有m^i-1^个结点(i>.=1)。m叉树第i层至多有m^i-1^个结点(i>.=1)。

4、高度为h的m叉树至多的结点个数为： $$ \frac{m^h-1}{m-1} $$ 等比数列求和公式： $$ a+aq+aq^2+...+aq^n-1=\frac{a(1-q^n)}{1-q} $$

5、高度为h的m叉树至少有h个结点。高度为h、度为m的树至少有h+m-1个结点。

6、具有n个结点的m叉树的最小高度为 $$ log_m(n(m-1)+1) $$ 高度最小的情况（所有节点都有m个孩子） $$ \frac{m^{h-1}-1}{m-1}<n\le\frac{m^h-1}{m-1} $$

$$ m^{h-1}<n(m-1)+1\le m^h $$

$$ h-1<log_m(n(m-1)+1)\le h $$

$$ h(min)=log_m(n(m-1)+1) $$

二叉树的基本概念

二叉树是n(n>=0)个节点的有限集合。

1、可能是空二叉树，即n=0。

2、或者是由一个根结点或两个互不相交的被称为根的左子树和右子树组成。左子树和右子树有分别是一棵二叉树。

特点：

1、每个节点至多只有两棵子树。

2、左右子树不能颠倒（二叉树是有序树）。

二叉树的五种状态：

1、空二叉树

2、只有左子树

3、只有右子树

4、只有根节点

5、左右子树都有

几种特殊的二叉树

二叉排序树

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树，都可以称为二叉排序树。二叉排序树可用于元素的排序、搜索。

1、左子树上所有结点的关键字均小于根节点的关键字

2、右子树上所有结点的关键字均大于根节点的关键字

3、左子树和右子树又各是一颗二叉排序树

平衡二叉树

树上任一结点的左子树和右子树的深度之差不差过1。平衡二叉树能有更高的搜索效率。

二叉树常用性质

1、设非空二叉树中度为0、1和2的结点个数分别为n~0~、n~1~和n~2~，则n~0~=n~2~+1（叶子结点比二分支结点多一个）

假设树中结点总数为n，则n=n~0~+n~1~+n~2~，n=n~1~+2n~2~+1（树的结点数=总度数+1），两式相减得n~0~=n~2~+1

2、二叉树第i层至多有2^i-1^个结点（i>.=i）【m叉树第i层至多有m^i-1^个结点（i>.=1）】

3、高度为h的二叉树至多有2^h^-1个节点（满二叉树）【高度为h的m叉树至多有m^h^-1/m-1个结点】

完全二叉树的常考性质

1、具有n个（n>0）结点的完全二叉树的高度h为 $$ \lceil log_2(n+1) \rceil或\lfloor log_2n \rfloor+1 $$ 高度为h的满二叉树共有2^h^-1个结点，高度为h-1的满二叉树共有2^h-1^-1个结点。则： $$ 2^{h-1}-1<n\le2^h-1 $$

$$ 2^{h-1}<n+1\le2^h $$

$$ h-1<log_2(n+1)\le h $$

$$ h=\lceil log_2(n+1) \rceil $$

高度为h-1的满二叉树共有2^h-1^-1个结点，高度为h的完全二叉树至少有2^h-1^个节点，至多有2^h^-1个结点。则： $$ 2^{h-1}\le n<2^h $$

$$ h-1\le log_2n<h $$

$$ h=\lfloor log_2n \rfloor+1 $$

2、对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为n~0~、n~1~和n~2~。

完全二叉树最多只有一个度为1的结点，即n~1~=0或1。n~0~=n~2~+1（叶子结点比二分支结点多一个）,可得n~0~+n~2~一定是奇数。

若完全二叉树有2k个（偶数）结点，则必有n~1~=1，n~0~=k，n~2~=k-1

若完全二叉树有2k-1个（奇数）结点，则必有n~1~=0，n~0~=k，n~2~=k-1

二叉树存储结构

二叉树的存储结构分为顺序存储和链式存储

二叉树的顺序存储

定义一个长度为MaxSize的数组t，按照从上到下，从左到右的顺序依次存储完全二叉树中的各个结点。可以让数组的第一个位置空缺，保证数组下标和结点编号一致。在初始化时所有结点标记为空。

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100 //预定义最大串长为100
typedef char ElemType;

// 使用 typedef 定义结构体类型
typedef struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty; //结点是否为空
} TreeNode;

// 初始化树节点数组
bool InitTree(TreeNode T[]) {
    for (int i = 0; i < MaxSize; i++) {
        T[i].isEmpty = true;
    }
    return true; // 返回初始化成功
}

int main() {
    TreeNode t[MaxSize]; // 树节点数组
    if (InitTree(t)) { // 调用初始化函数
        printf("Tree initialized successfully.\n");
    } else {
        printf("Failed to initialize tree.\n");
    }
    return 0;
}

查看结点i的左孩子（2i），查看结点i的右孩子（2i+1），i所在的父节点（i/2）

i所在的层次 $$ \lceil log_2(n+1) \rceil或\lfloor log_2n \rfloor+1 $$ 缺点：如果不是完全二叉树，依然按照层序将各结点顺序存储，那么将无法从结点编号反映出结点间的逻辑关系。

在二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。

最坏的情况：高度为h且只有h个结点的单支树（所有结点只有右孩子），也至少需要2^h^-1个存储单元。所以二叉树的顺序存储结构，只适合存储完全二叉树。

二叉树的链式存储

n个节点的二叉链表共有n+1个空链域（空链域可用于构造线索二叉树）

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
} BiTNode,*BiTree;

使用链式存储的方式可以方便的找到某个结点的左右孩子，但是如果想找到某个结点的父节点，就只能从根结点开始遍历寻找，或者是加入父结点指针。可以将此链表称为三叉链表。

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
    struct BiTNode *parent; //父结点指针
} BiTNode,*BiTree;