树和二叉树（C语言）

目录

一. 树的定义

Tip：如何判断树与非树？

二.树的一些概念

Tip：自己的祖先可以包含自己，所以最近公共祖先可以是自己。如上图中节点f和节点k的最近公共祖先我们认为是f，而并非a。

 Tip：树结构实现的孩子兄弟表示法：

Tip：树在Linux中会用来做目录树结构

 四.二叉树

1.二叉树的基本概念与性质

Tip：二叉树中有两种特殊的二叉树

2.二叉树的性质（比较重要）

---

一. 树的定义

        有一个特殊的结点，称为根结点，根节点没有前驱结点
        除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集          合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以            有0个或  多个后继。因此，树是递归定义的

Tip：如何判断树与非树？

树是不能有回路的。否则递归会死循环，譬如上图第一个树，A可以递归到C递归到D，然后又A->C->D，就死循环了。

二.树的一些概念

 

 注意兄弟节点和堂兄弟节点的区别。兄弟节点是有相同父节点的节点，堂兄弟节点则是双亲在同一层的节点。

Tip：自己的祖先可以包含自己，所以最近公共祖先可以是自己。如上图中节点f和节点k的最近公共祖先我们认为是f，而并非a。

学这些概念的目的是为了方便描述，也为了能以后看懂题目要求。

三.树结构的实现（现在还不是二叉树）

树结构的实现会比较难，因为不知道每个节点有多少个子节点，我们可以定义一个

 Tip：树结构实现的孩子兄弟表示法：

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

 

 兄弟孩子表示法不关心每个节点有多少孩子，父节点只需要指向第一个孩子，其余的孩子用兄弟指针连接起来。

Tip：树在Linux中会用来做目录树结构

 四.二叉树

 树的意义其实并不大，重要的是树中的一种特殊情况——二叉树。

1.二叉树的基本概念与性质

  二叉树是度为2的树，注意度为2不代表每个节点都有两个孩子，而是最多有两个孩子

Tip：二叉树中有两种特殊的二叉树

   完全二叉树：前n-1层都是满的，最后一层可以不满，但是最后一层从左往右连续。

   满二叉树可以用链表或数组实现

   

2.二叉树的性质

 第三点性质比较重要