树和二叉树

1:前言：

** 树对于和我一样的刚开始学数据结构的小伙伴们来说，是首次接触到的非线性的数据结构，因此它比起前面所学习到的栈和队列来说，难度上会稍加难一些，同时与树有关的知识点比起之前学过的数据结构来说也会更多一些。学习树也是为了后来学习搜索二叉树**做铺垫。

在对数据结构-二叉树有了一个初步的接触之后，整理出来了树和二叉树的一些基本知识，希望能够帮助小伙伴们对树有个更好的初步认识！

1:树的概念及结构

 1.1:树的概念

        树是一种**非线性的**数据结构，它是由n(n>=0)个节点组成的一个具有层次关系的集合，**而我们之所以把这种结构成为树，是因为它看起来像一棵倒挂的树，即它是根朝上，叶朝下的。**

** 有一个特殊的节点没有前驱节点，称为根节点。**

学好树首先我们要了解与树有关的各个称谓.

接下来，就让我们一起认识认识树中的各个名称吧.

节点的度：度指的是一个节点它下面的子树的个数。F的度为3。

树的度 ** ：树的度指的是，在这一棵树中所有节点中最大的度，此棵树的度为6**(A的度为6)

节点的层次：默认根是第一层，接下来是第二层，第三层，依此类推。

树的高度或深度：即此树能达到的最大的层数，此树高度为4.

叶节点或终端节点：顾名思义，叶就是一棵树的尾，因此B,C,H,I,P,Q,K,等都是叶节点。

非终端节点或分枝节点：度不为0的节点。

**兄弟节点，孩子节点==子节点，双亲节点==父节点，节点的祖先，子孙(上图所有节点都是A的子孙)**等概念就不在此一一赘述，根据字面意思理解即可。

这里所指出来的这三点是满足成为一棵“树”所需要的条件。

接下来，小伙伴们判断一下这棵“树”，它到底算不算一颗树呢？

是的，它显然不满足刚刚所提出来的那几个条件，所以它不算是一颗树，只能勉强的算是一个图。

1.2 树的表示：

顺序存储：

顺序存储采用一段连续的存储空间，因为书中节点的数据关系是一对多的逻辑关系，所以不仅要存储数据元素，还要存储它们之间的逻辑关系，顺序存储有双亲表示法，孩子表示法和兄弟孩子表示法等。这里就介绍较为常用的孩子兄弟表示法，以及双亲表示法。

以下图为例分别讲述三种存储方法

(1)孩子兄弟表示法：

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

优缺点：

(2)双亲表示法：除了存储数据元素，还要存储其双亲节点的存储位置下标，其中-1表示不存在。每个节点都有两个域：数据域data和双亲域parent，其中A无双亲，因此双亲域为-1。A的下标为0，B,C,D的双亲节点是节点A，因此B,C,D的双亲域为0.其他的节点也依此类推。

优缺点：双亲表示法只记录了每个节点的双亲，无法直接得到该节点的孩子。

2:二叉树的概念和结构：

  ** 2.1:二叉树的概念：**

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

      **  二叉树的特点：**

         （1）二叉树每个节点最多有两棵子树，即二叉树不存在度大于2的节点。

         （2）二叉树的子树有左右之分，其次序不能颠倒。

二叉树在数据结构中的存储方式往往是这样的：

特殊二叉树：

         （1）满二叉树：一个二叉树，如果每一层的节点数都达到这一层的最大值，这棵树就被称为满二叉树。也就是说如果一个二叉树层数为n，节点数为（2^n)-1,则称他为满二叉树。

         （2）完全二叉树：完全二叉树是一种效率很高的数据结构，完全二叉树是由满二叉树引出的，对于一个深度为n，节点数为k的二叉树，当且仅当它的每个编号与深度为n的满二叉树中编号从1到k的节点对应时，称为完全二叉树。这里我们把完全二叉树当作满二叉树的一种特殊情况。

二叉树的性质：
（1）若规定根节点层数为1，则此二叉树第i层最多有2^(i-1)个节点，若二叉树层数为h，则整个二叉树最多含有(2^h)-1个节点。

（2）对于任何一棵二叉树，如果其度为0的节点数为n0，度为2的节点数为n2，则存在关系：n0=n2+1;

(3)若一个满二叉树的节点为k，根节点的层数为1，则该满二叉树的深度为h=log n.

2.2:二叉树存储方式：

（1）顺序存储：

     顺序结构存储就是指用**数组来存储**，一般**使用数组只适合表示完全二叉树**，是因为不是完全二叉树的话会造成内存的浪费。**二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。**（如下图所示）。

（2）链式存储：

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

          对此我们这样创建一个链表所用到的结构体。

​
typedef struct Tree {
    char data;                  //指向当前节点的数值域
    struct Tree* left, * right; // 指向当前节点的左右子节点
}tree;

​

然后，在此处我们手动建立一颗有五个节点的树。五个节点分别是A,B,C,D,E。下面是节点A的创建方法。

int main()
{
    tree* A = (tree*)malloc(sizeof(tree));
    assert(A);
    //此处assert()函数的作用是防止因malloc函数未成功给结点A分配内存而导致的程序报错无法正常运行。
    A->data = 'A';
    A->left = NULL;
    A->right = NULL;

接下来B,C,D,E节点的创建方法均与A相同，在此就不再一一列出。

    A->left = B; A->right = C;
    B->left = D; C->right = E;
    //然后我们将这棵树的五个结点相互连接起来
    //当然此处的关系并不唯一

最后我们建造起的这棵树的样子是这样的：

2.3 二叉树链式结构的遍历：

     **遍历**是指按照某种搜索路线，依次对二叉树中**每个节点均做一次且仅做一次访问**，遍历是二叉树上最重要的运算之一，是在二叉树上进行其他运算的基础。

  ** 遍历**树的方式有三种：

前序遍历/中序遍历/后序遍历：

NLR (前序遍历)：访问根节点的操作放在左子树和右子树之前。

LNR (中序遍历)：访问根节点的操作放在左子树和右子树的操作之间。

LRN (后序遍历):访问根节点的操作放在访问左子树和右子树之后。（注意这三种方法中指的均是左右子树而非左右子节点）。

   知道了大致的方法之后，我们这里不妨**先以后序遍历(后根遍历)做个示范**：

    **上面这张图片各个节点旁边的编号表示的就是这个节点被访问的先后次序，可能会有小伙伴问了：这个D节点明明处于最下面，为什么它要比在最上面的节点A还先被访问呢？   **

** 那么我们就按照刚刚给出的方法，来依次遍历这一棵树，让我们一起来试试吧！**

    首先我们先从A节点开始看(**并不访问**)，由于后序遍历先遍历左子树，所以我们找到了A节点的左子树 (这里指的是节点B,D,E所构成的树)，在这棵树里面B为根节点，在这棵树中再根据    左右根   的顺序，由于**D为左子树并且没有了后序的子树，E为右子树并且也没有后序的子树**，所以我们首先访问D节点(左)(编号为1)，再访问E节点(右)编号为2，最后访问B节点(根)(编号为3)，到此我们已经对A的左子树完成了遍历，根据后序遍历的方法，我们在左子树之后要遍历右子树。

   在A的右子树中，C为根节点，F,G分别是左右节点，并且**在F,G之后没有新的子树可以遍历**，所以我们接着访问F(左子树)编号为4，紧接着是G(右子树)编号为5，最后是C(根节点)编号为6，**至此A的右子树也遍历完了**，所以最后遍历A(根节点)编号为7.

  至此我们已经得出了这棵树的后序遍历的结果,(**依次按DEB FGCA遍历**)，我们心中也对上面提出的问题有了答案。

这棵树的前序遍历的结果是：A BDECFG。

           中序遍历的结果是：**DBE A FCG。**

 

   除了前中后序遍历以外，二叉树还有一种遍历方式--**层序遍历**，层序遍历是指：从二叉树的根节点出发，先访问第一层，接着是第二层，**从上到下从左往右依次遍历二叉树中的所有节点**，这种方法就称作为层序遍历。

所给的这棵树，层序遍历的结果是(ABCDEFG).

2.3.2 二叉树遍历的代码实现：

** 说了这么多，目的都是为了能更好的理解二叉树的遍历的代码实现，那么二叉树的遍历要用一种什么样的方法来实现呢？让我们一起来看看吧！**

我们对于二叉树的前中后序遍历一般用的是递归这一方法，具体的解释如下：

前序遍历：

​
void Preordertree(tree* root) {       //根 左 右
    if (root == NULL) {               //一直往下遍历直到访问到二叉树的尾端节点
        printf("NULL ");              
        return;
    }
    printf("%c ", root->data);        //如果不是尾端节点的话，因为是前序遍历，所以直接打印根节 
                                        点
    Preordertree(root->left);         //再遍历左子树
    Preordertree(root->right);        //再遍历右子树
}

​

依旧是对于我们前面手动创建的这样一棵树，我们来看一下前序遍历后输出的结果。

我们在第90行执行了Preordertree，并把根节点A传了进去，我们可以看到最后的结果为ABDCE

中序遍历：

void Inordertree(tree* root) {
    if (root == NULL) {                  
        printf("NULL ");
        return;
    }
    Inordertree(root->left);        //中序遍历先进左子树，再访问根节点，最后进右子树
    printf("%c ", root->data);      
    Inordertree(root->right);
}

结果为：

至于后序遍历的话，只需要改变访问根节点相对于访问左右子树的位置即可，小伙伴们可以自己用编译器练习练习！

2.4 二叉树的节点数：

  接下来我们要说一下**如何计算一棵二叉树的总节点数**，我们首先想到的一种方法肯定是**从根节点一直遍历到叶节点**，设置一个用来计数的全局变量，最后就能得到全部的节点数，但是如果在此我想用**递归**这一算法来实现这一过程的画要怎么写代码呢？

 其实很简单，只需要一句话就可以实现，这就是递归的奇妙之处：

int Treesize(tree* root) {
    //这里采用了分治的思想，分治就是指将一棵完整的二叉树分割成一个个最小的二叉树
    //而每棵最小的二叉树都包括三个部分，分别是左右节点和这棵最小二叉树的根节点，最后所有的这些相加结果就得到了这棵二叉树的总结点数。
    return root == NULL ?0: Treesize(root->left) + Treesize(root->right) + 1;
}

2.5 二叉树的叶子节点数：

 同样的，二叉树的叶子节点数我们也可以从根节点开始遍历，同样设置一个用来计数的变量，但是我们同样也可以使用递归，因为**这棵二叉树的总叶子节点数就等于节点A的左子树和右子树中的叶子节点数的总和。**

int Leafsize(tree* root) {
    if (root == NULL) {
        return 0;
    }

    //判断是叶子节点的要求是左右节点均为空。
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    //返回的是左右子树的叶子节点的总和。
    return Leafsize(root->left) + Leafsize(root->right);
}

 至此，今天我想要跟各位小伙伴分享的二叉树知识点已经全部在上面了。  

 博主是一位大一的蒟蒻，刚开始接触数据结构和算法，希望能得到各位巨佬的指点（orz）！

 ![](https://img-blog.csdnimg.cn/f94029cc25944d8aa0bf06cdd62c0fb4.png)



代码学习需要的是持之以恒，更需要对一些重要知识点进行反复的学习，打磨。

**在从今往后学习数据结构以及算法的过程中，我也会不断地将自己的所学所感分享给大家，这篇文章写来不易，希望能获得各位小伙伴的点赞和关注，后续一定会有更精彩的内容！ **