C语言--数据结构：树_数据结构c语言树

一、树的的概念及结构 

树的相关概念

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林。

树的概念不用记，清楚加粗的和了解其它的即可。

树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
 struct Node* leftChild1; // 第一个孩子结点
 struct Node* rightBrother; // 指向其下一个兄弟结点
 DataType data; // 结点中的数据
};

二、二叉树的概念和结构

二叉树是一种特殊的树状数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。这些子节点分别位于父节点的左侧和右侧。

二叉树的特点包括：

• 每个节点最多有两个子节点，分别为左子节点和右子节点。
• 左子节点和右子节点的顺序是有意义的，不同的顺序可能导致不同的树结构。
• 每个节点最多只有一个父节点，除了根节点外。
• 二叉树可以是空的，即不包含任何节点。
• 二叉树可以是递归定义的，即每个节点本身也是一个二叉树。

二叉树在计算机科学和算法中具有广泛的应用，例如在搜索、排序和存储等方面。常见的二叉树类型包括二叉搜索树、平衡二叉树、满二叉树等。

1.满二叉树：

• 满二叉树是一种特殊的二叉树，其中除了叶子节点之外，每个节点都有两个子节点。
• 如果一个二叉树的高度为h，并且它的每一层都恰好有2^k个节点（其中0 <= k <= h-1），则它就是一棵满二叉树。
• 满二叉树的特点是每个非叶子节点都有两个子节点，且所有的叶子节点都在同一层上。

2.完全二叉树：

• 完全二叉树是一种二叉树，除了最后一层外，每一层的节点都按照从左到右的顺序填满。
• 在最后一层，所有的节点都尽量靠左排列。
• 如果按照从上到下、从左到右的顺序对树中的所有节点进行编号，并且这个编号和对应的满二叉树的编号一致，那么这棵二叉树就是一棵完全二叉树。

二叉树具有许多重要的性质，下面是其中一些常见的性质：

1. 节点数量关系：

   • 在高度为h的二叉树中，最少有h个节点，最多有2^h - 1个节点。
   • 如果二叉树中叶子节点的数量为n0，度为2的节点（即具有两个子节点）的数量为n2，则n0 = n2 + 1。

2. 高度与节点数量关系：

   • 对于n个节点的二叉树，最小高度为log2(n+1)，向下取整。
   • 对于高度为h的二叉树，最少有h个节点，最多有2^h - 1个节点。

3. 度为k的节点数量：

   • 在二叉树中，度为k的节点数量最多为2^(k-1)。

4. 满二叉树和完全二叉树的性质：

   • 满二叉树的高度为h，节点数量为2^h - 1。
   • 完全二叉树的高度为h，如果节点数量为n，则最少有h个节点，最多有2^h - 1个节点，且最后一层从左向右依次填满。

5. 节点访问顺序：

   • 前序遍历：根-左-右
   • 中序遍历：左-根-右
   • 后序遍历：左-右-根
   • 层序遍历：从上到下，从左到右依次访问每个节点。

在这两种类型的二叉树中，满二叉树更加严格，因为它的每个节点都有两个子节点，并且所有的叶子节点都在同一层。而完全二叉树在填充节点方面更加灵活，只要保证除了最后一层，其他层都是满的，并且最后一层的节点尽可能靠左排列即可。

我们也可以用数组表示树，存放顺序从上往下，从左往右。

父子存储的下标位置规律：
leftchild  = parent * 2+1
rightchild = parent * 2+2
parent = (child - 1) / 2
如果用数组找，父亲和孩子，就用以上公式。由于整形/2的小数向下取整，所以左孩子和有孩子求父亲都是这个公式。

即顺序表的实现：

typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

树是一种重要的数据结构，具有许多有用的性质和操作。通过理解树的基本概念、性质和常见操作，我们可以更好地应用树结构解决实际问题，并为算法和数据处理提供更高效的解决方案。希望本文能够帮助您更好地理解和利用树这一强大的数据结构。

而堆是一种完全二叉树。明天我会讲解堆来实现一个二叉树