初识树（c语言）

序列文章

初识树（C语言）：http://t.csdnimg.cn/eqFmT

二叉树的基本概念（C语言）：http://t.csdnimg.cn/AkwTC

大小堆的实现（C语言）：http://t.csdnimg.cn/yoXVC

看了就会的堆排序（C语言）：http://t.csdnimg.cn/EWzgM

top K问题（借你五分钟）：http://t.csdnimg.cn/1YLT8

堆的相关时间复杂度计算（C语言）：http://t.csdnimg.cn/OSAr4

二叉树的前、中、后序遍历的实现：http://t.csdnimg.cn/xNHrs

计算二叉树结点个数、叶子结点个数的代码实现：http://t.csdnimg.cn/kiBpd

二叉树查找值为x的结点、树的高度、第k层结点个数的代码实现：http://t.csdnimg.cn/BcFEW

二叉树的创建、销毁、层序遍历、层序遍历进阶的代码实现： http://t.csdnimg.cn/Qlxu0

二叉树的OJ练习（一）：http://t.csdnimg.cn/jhOWW

二叉树的OJ练习（二） ：http://t.csdnimg.cn/sl7kl

<你想看的我这里都有😎 >

树

定义：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，当n=0时，称为空树。

任意一颗非空树都应满足：

1. 有且只有一个根结点，即图中的A结点
2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树，每棵子树的根结点有且只有一个前驱，可以有0个或多个后继结点，因此，树是递归定义的。

树与非树

树形结构中，子树之间不能有交集，否则就不是树形结构

树的相关概念

结点的度：一个结点含有的子树的个数称为该结点的度；如上图：A的度为6

叶/终端结点：度为0的结点称为叶结点（下面没有）；如上图：B、C、H、I...等节点为叶结点

非终端/分支结点：度不为0的结点（下面还有）；如上图：D、E、F、G...等节点为分支结点

双亲/父结点：一个结点有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点

孩子/子结点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子结点

兄弟结点：具有相同父结点的节点互称为兄弟结点；如上图：B、C是兄弟结点

树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

结点的层次：根为第1层，根的下一层为第2层，以此类推；

树的高/深度：树中结点的最大层次；如上图：树的高度为4

堂兄弟结点：同层除兄弟结点外，其它结点都是堂兄弟结点；如上图：H、I互为堂兄弟结点

子孙：以某节点为根的子树中任一节点都称为该节点的子孙；如上图：所有结点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

有/无序树：根据树中任意节点的子结点之间有无顺序关系，将树分为有序树和无序树

路径和路径长度：两个结点之间的边称为路径，两个结点之间边的总合称为路径长度

上述内容不建议背诵，根据后续练习常看常理解即可

树的存储表示

      在构建树的结构时， 除了要保存节点的值域外，还需要保存节点与节点之间的关系。实际应用中，存在多种树的表示方式，如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。其中 最常用且灵活性较高的是孩子兄弟表示法（也称为二叉树链表存储），我们这里就简单的了解一下它是如何表示树的：

大致代码

typedef int DataType;
//左孩子右兄弟表示法
struct TreeNode
{
    DataType val; //结点中的数据域
    struct TreeNode* leftChild; //第一个孩子结点
    struct TreeNode* rightBrother; //指向其下一个兄弟结点
};
//模拟查找树的根节点下的每一个孩子
void find()
{
    struct TreeNode* child = A->leftChild;
    while(child)
    {
        child = child ->rightBrother;
    }
}

详细代码

#include <stdio.h>
#include <stdlib.h>
// 定义树节点结构
typedef struct TreeNode {
    char data;
    struct TreeNode* first_child;   // 指向第一个孩子节点
    struct TreeNode* next_sibling;  // 指向下一个兄弟节点
} TreeNode;
// 创建树节点函数
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->first_child = NULL;
    newNode->next_sibling = NULL;
    return newNode;
}
int main() {
  // 创建树结构，以示例中的图为例：
  /*
         A
        / \
       B   C  
      / \   
     D   E 
  */
  TreeNode* root = createNode('A');
  root->first_child = createNode('B');
  root->first_child->next_sibling= createNode('C');
  root->first_child -> first_child= createNode('D');
  root -> first_child -> first_chil d- > next_sibli ng= creat eNod e( 'E' );
  return 0;
}

实际应用（Linux文件系统的目录树）：

~over~