树与二叉树 —— 十分钟吊打数据结构

这里就又需要思考递归的含义，递归是当前问题和子问题的集合，这里的树是根和n个子树构成，而每个子树的结构又是如此，开始逐渐套娃，直到遇到“叶子”结束。

注意，树与非树的区别就在于：

1. ==树结构的子树是互不相交的（带回路的结构叫图）==
2. ==除了根节点外，其余节点有且仅有一个父节点==
3. ==一颗有N个节点的数有N-1条边==
   

基本术语🤔

不理解这些基本概念后面没法玩儿捏，还是得知道怎么去描述：

1. 结点的度：结点的子树个数；
2. 树的度：树的所有结点中最大的度数；
3. 父结点：有子树的结点是其子树的根节点的父结点；
4. 子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点；
5. 兄弟（姐妹）结点：具有同一个父结点的各结点彼此是兄弟结点（还有堂兄弟（姐妹）节点，自己意会就行懒得打字）；
6. 祖先结点：沿树根到某一结点路径上的所有结点
7. 子孙结点：某一结点的子树中的所有结点
8. 结点的层次：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
9. 森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示🤔

树要进行表示可不好表示，因为有一个大问题——==子节点个数不确定==。

这里树必然是一个链式结构，每个节点都有存的值以及指向孩子的指针，现在我们所使用的结构大多为顺序表，有人会用数组来搞（下标为孩子个数），也可以使用C++语法的 vector 来进行操作，但这些都只能算是中规中矩，这里介绍一种很优秀的表示方法可以不用关心度的多少和空间的消耗：孩子&兄弟表示法。

typedef int datatype;
struct node
{
struct node* first;//第一个孩子节点
struct node* next;//指向下一个兄弟节点
datatype data;//数据域
}