引入

我们介绍了什么是二叉树、以及二叉树一些与众不同的特点，例如只能有两个孩子，两个孩子还分为左子树和右子树，那么今天我们来看看特殊的二叉树。

斜树

¡¡™
顾名思义，斜树一定要倾斜。也就是说，一棵树

• 只有左子树
• 只有右子树

这样就不是斜树了。

引入

前面，我们从只能表示父母的双亲表示法，升级到了能同时表示双亲和孩子的双亲父母表示法，在学习孩子兄弟表示法之前，我们先来看看二叉树是什么。

二叉树

树形数据结构有很多种树，但二叉树是使用范围最广的，也最具有代表意义，所以学习树，我们不能不提二叉树。
对于二叉树（Binary Tree），你应该知道

• 二叉树是 n($n \geq 0$)个结点的有限集合
• 如果集合为空，我们就说这是一个空二叉树
• 如果不是空，那就是由两棵互不相交的二叉树组成
• 我们称这两棵树分别是根的左子树和右子树。

这个定义，是一个递归的形式

• 树有一个根
• 根下有两棵树，左子树、右子树
• 两个棵树各自有一个根
• 两个根又都有左子树和右子树。

引入

前面，我们介绍了双亲表示法，每个结点中出了节点的值，还保存了parent的信息。今天我们换个角度，用孩子表示法来看看如何构建树的存储结构。

想一想

现在双亲表示发的问题在哪？

• 只能体现双亲信息和该结点信息
• 没有孩子的信息
• 增加节点内的结构只能增加部分孩子信息，如3个、5个
• 如果某个子节点大量孩子加入，会造成内存空间浪费

想达到什么效果？

• 能体现孩子的信息
• 孩子无论增加多少，都可以只浪费一定的内存空间
• 如果能再包含双亲的信息就更好了！

我们看着这张图，然后想，能不能将链表和顺序存储结构结合起来

引入

前面，我们学习了树的一些基础内容，今天我们就来看看，树有哪些存储结构。说到存储结构我们会想到线性表中的顺序存储结构和链式存储结构，那么树会怎么设计自己的存储结构呢？我们一起来看一看~

树的存储结构

要存储树，用简单的顺序存储结构和链式存储结构都不行。因为树中有双亲、孩子、兄弟这些概念，我们不能用简单的顺序、链式存储结构表达树中各个结点的情况。所以，根据不同的角度，我们有三种存储结构表示一棵树

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

双亲表示法

双亲表示法，顾名思义，就是以双亲作为索引的关键词的一种存储方式。

• 我们先划出一段连续存储空间，类似数组，存储每一个结点
• 在每个结点中，附设一个指示其双亲结点在数组中位置的元素
• 也就是说，每个结点直到自己和自己的双亲

#define MAXTREE 100

struct pt{
int data;  // 结点的数据
int parent;  //每个结点父母的位置，也就是数组下标
};

struct tree{
struct pt pointer[MAXTREE];  //100个包含 pt 结构体的数组
int r;  //根的位置，一般是 0，也就是数组第一个元素
int n;  //结点数目
}

引入

之前我们讲的都是线性表，它们有可以是顺序存储结构或者链式存储结构的数组、链表、栈、队列。我们之前讨论的线性结构都是一对一的。那什么不是一对一呢？例如妈妈的两个孩子，一个妈妈对应了两个孩子，这种一对多的数据结构，我们称之为树。当然了，以后还会有多对多的概念，今天我们先了解一下树的概念。

树的定义

树（Tree）是 n ($n\geq0$) 个结点的有限集。n=0 时，我们称之为空树。
在任意一棵非空树中：

• 有且仅有一个特定的称之为根（Root）的结点。
• 当 n>1 时，其余结点可分为 m($m\geq0$)个互补相交的有限集
• 有限集 T1、T2、….、Tm，其中每一个集合本身又是一棵树
• 我们称由这些有限集合构成的树，为根的子树（SubTree）。

上面的图中

• **根：**A 结点是这棵树的根
• **结点：**每一个圈都是一个结点
• **子树：**B、C、D、E、F、G、H都是子树

引入

未完待续…

引入

未完待续…

引入

未完待续…

引入

未完待续…

引入

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

简单思想

• 将大问题化简称小问题
• 8X8二维数组的任意一个位置
• 一行一行来检查，符合要求的就把0改成1
• 要求就是一列不能有1，一行不能有1，斜着不能有1
• 一行一行的递归是一部分、检查行列斜有没有棋子1是一部分
• 递归下去，然后回溯回来，就能将所有的情况列出来了。