【数据结构】_在任意一棵二叉树中,树叶的数目比度数为2的数目多1

树

树的概念

树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件：
​有且仅有一个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树 （Subtree）。

表示方法 ：树形表示法、目录表示法。

树的相关的概念

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

一个节点的子树之根节点称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点，叶节点没有子节点。

树的边数及高度

一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为有序树。一般的树是有序树。m（m≥0）棵互不相交的树的集合称为森林。

树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

树的逻辑结构

树的逻辑结构 ：树中任何节点都可以有零个或多个直接后继节点（子节点），但至多只有一个直接前趋节点（父节点），根节点没有前趋节点，叶节点没有后继节点。

二叉树的概念

二叉树的定义 ： 二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

二叉树的特性

二叉树第i（i≥1）层上的节点最多为2i-1个。
深度为k（k≥1）的二叉树最多有2k－1个节点。
在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。
总节点数为各类节点之和：n = n0 + n1 + n2
总节点数为所有子节点数加一：n = n1 + 2*n2 + 1
故得：n0 = n2 + 1 ;

满二叉树 ：深度为k（k≥1）时有2k－1个节点的二叉树。

完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。

二叉树的存储

顺序存储结构 ：完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。
设完全二叉树的节点数为n，某节点编号为i。
①当i＞1（不是根节点）时，有父节点，其编号为i/2；
②当2i≤n时，有左孩子，其编号为2i ,否则没有左孩子，本身是叶节点；
③当2i＋1≤n时，有右孩子，其编号为2i+1 ,否则没有右孩子；
④当i为奇数且不为1时，有左兄弟，其编号为i-1,否则没有左兄弟；
⑤当i为偶数且小于n时，有右兄弟，其编号为i＋1,否则没有右兄弟；

二叉树的存储

方式1：顺序存储，浪费内存空间

方法2：链式存储（实际开发是使用的方式）

#define datatype int
typedef struct node{
   
    datatype data;
    struct node *lchild,*rchild;
}bitree_t;
1
2
3
4
5
6

完全二叉树的创建

什么是递归

递归：在函数内部调用自己，递归函数的设计主要就是要考虑清空结束条件
eg:求n！的递归实现

#include <stdio.h>

// n! = n*(n-1)*(n-2).....*2*1;

// fact(5) = 5*fact(4)
// fact(4) = 4*fact(3)
// fact(3) = 3*fact(2)
// fact(2) = 2*fact(1)
// fact(1) = 1

// fact(5) = 5*4*3*2*1
int fact(int n)
{
   
    if(n==1)
        return 1;
    return n*fact(n-1);
}
int main(int argc,const char * argv[])
{
   
    int num=1;
    num = fact(5);
    printf("num = %d\n",num);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

使用递归创建完全二叉树

#include "bitree.h"

// n节点的个数
// i节点的编号，i>=1
// 当i＞1（不是根节点）时，有父节点，其编号为i/2;
// 当2*i≤n时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点;
// 当2*i＋1≤n时，有右孩子，其编号为2*i+1 ,否则没有右孩子；
bitree_t* BiTreeCompleteCreate(int n, datatype i)
{
   
    bitree_t* root;
    // 分配节点的内存
    root = (bitree_t*)malloc(sizeof(*root));
    if (root == NULL) {
   
        printf("malloc node memory error");
        return NULL;
    }

    // 将i放到节点的数据域中
    root->data = i;

    if (2 * i <= n) {
   
        // 有左孩子
        root->lchild = BiTreeCompleteCreate(n, 2 * i);
    } else {
   
        // 没有左孩子
        root->lchild = NULL;
    }

    if (2 * i + 1 <= n) {
   
        // 有右孩子
        root->rchild = BiTreeCompleteCreate(n, 2 * i + 1);
    } else {
   
        // 没有右孩子
        root->rchild = NULL;
    }

    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

二叉树的遍历

广度优先遍历（BFS）

思想：广度优先遍历是通过队列来实现的，先让根节点入队，然后再让根节点出队，出队之后打印这个节点的值，判断有没有左孩子如果有左孩子，让左孩子入队。再判断有没有右孩子，如果有右孩子让右孩子入队。让左孩子出队，打印左孩子的值，判断它有没有左右孩子，如果有左右孩子，入队。判断右孩子有没有左右孩子，如果有就入队。以此类推。将整个二叉树遍历结束为止。

深度优先遍历(DFS)

由于二叉树的递归性质，遍历算法也是递归的。三种基本的遍历算法如下 ：
先序：
先访问树根，再访问左子树，最后访问右子树（根左右）；
中序：
先访问左子树，再访问树根，最后访问右子树（左根右）；
后序：
先访问左子树，再访问右子树&#