二叉树
定义 二叉树是一个有限的结点集合，这个集或者为空，或者由一个根节点和两颗互不相交的称为左子树和右子树的二叉树组成
区别 与度为2的树的区别： 1.度为2的树至少有一个结点度为2，而二叉树可以不用 2.二叉树严格区分左右子树
满二叉树和完全二叉树 [photo]
非空满二叉树 叶子结点在最下一层 只有度为0和度为2的结点
非空完全二叉树 叶子结点只可能出现在最下面两层 最大层次中的叶子结点都依次排列在该层最左边的位置 若有度为1的结点 只有一个且只有左孩子无右孩子 层序编号，出现编号i的结点是叶子结点或只有左孩子则大于i的结点均为叶子结点 结点总数n为奇数时 n1 = 0 偶数时 n1 = 1
性质 1.$n_0 = n_2 + 1$ （叶子结点数 = 双分支结点数 + 1） $n = n_0 + n_1 + n_2, n - 1 = n_1 + 2n_2$ 所有结点度之和 $= n - 1 = n_1 + 2n_2$ 2.非空二叉树第i层最多有$2^{i-1}$个结点($i \ge 1$) 3.高h的二叉树最多有$2^h - 1$个结点 ($h \ge 1$) 4.完全二叉树 层序编号i的结点：
- 若$2i \le n$ 则此结点为分支结点，否则为叶子结点
- 若n为奇，则每个分支结点都为2分支，n为偶数 编号最大的分支结点为单分支 只有左孩子
- 编号i的结点的左孩子编号2i 右孩子编号2i+1 （若存在的话）
- 除根节点外 结点编号i，父节点编号$\left \lfloor i/2 \right \rfloor$ 5.具有n个结点的完全二叉树高度为$\left \lceil log_{2}{n+1} \right \rceil$ or $\left \lfloor log_{2}{n} \right \rfloor + 1$ 树转换二叉树 1.树中相邻兄弟之间加边 2.对每个结点只保留与长子（对孩子兄弟存储节点来说，其他孩子删除）的边 3.顺时针旋转45°
二叉树转树 1.找到是其父节点的左孩子的结点，把其右孩子，右孩子的右孩子等与此结点的父节点连线 2.删除所有结点与右孩子的连线 3.逆时针转45°
森林转二叉树 1.每棵树转二叉树 2.把后一个二叉树的根节点作为前一个二叉树的右孩子结点连接，持续则得
二叉树转森林 1.把根节点右边的所有根节点-右孩子关系去除，得到很多二叉树 2.还原这些二叉树
存储结构 顺序存储：数组 链式存储
创建二叉树 用括号表达法表示二叉树 A(B,C)表示A的左孩子为B，右孩子为C 递归定义 则对应代码
void CreateBTree(Node *&b, char *str)
{
Node *st[MaxN], *p; /* 定义栈 */
int top = -1, k, j = 0;
char ch;
b = NULL;
ch = str[j];
while (ch)
{
switch (ch)
{
case '(':
st[++top] = p;
k = 1; /* 要添加左孩子 此时的父节点进栈用于下一个default对栈顶添加孩子 */
break;
case ')':
top--; /* 当前栈顶结点处理完毕 */
break;
case ',':
k = 2; /* 添加右孩子 */
break;
default:
p = (Node *)malloc(sizeof(Node));
p->data = ch;
p->lchild = p->rchild = NULL;
if (!b)
{
b = p;
}
else
{
switch (k)
{
case 1:
st[top]->lchild = p;
break;
case 2:
st[top]->rchild = p;
break;
}
}
}
ch = str[++j];
}
}
销毁二叉树
void DestroyBTree(Node *&b)
{
if (b)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
查找结点 递归模型：
Node* FindNode(Node* b,char x)
{
Node *p;
if(!b)
{
return NULL;
}else if (b->data == x)
{
return b;
}else
{
p = FindNode(p->lchild,x);
if(p)
{
return p;
}else{
return FindNode(b->rchild,x);
}
}
}
求高度 自底向上更新
int BTHeight(Node* b)
{
int lchildh,rchildh;
if(!b)return 0;
lchildh = BTHeight(b->lchild);
rchildh = BTHeight(b->rchild);
return max(lchildh,rchildh) + 1;
}
输出
void DispBTree(Node *b)
{
if(b)
{
cout<<b->data;
if(b->lchild || b->rchild)
{
cout<<"(";
DispBTree(b->lchild);
if(b->rchild)
{
cout<<",";
}
DispBTree(b->rchild);
cout<<")";
}
}
}
前-中-后序遍历-层次遍历
void PreOrder(Node *b)
{
if(b)
{
cout<<b->data;
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void InOrder(Node *b)
{
if(b)
{
InOrder(b->lchild);
cout<<b->data;
InOrder(b->rchild);
}
}
void PostOrder(Node* b)
{
if(b)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
cout<<b->data;
}
}
void LevelOrder(Node *b)
{
Node* p;
queue<Node*> q;
q.emplace(b);
while(!q.empty())
{
p = q.front();q.pop();
cout<<p->data;
if(p->lchild)q.emplace(p->lchild);
if(p->rchild)q.emplace(p->rchild);
}
}
非递归遍历 1.先序遍历 考虑一个栈，取出栈顶结点的时候将其data打印，则出栈顺序为 根-左-右 由于先序遍历的递归特性，出栈完一个结点 其默认是子树或树的一个根节点 先序遍历的根已经打印 此时需要将其左右子节点压栈 伪代码如下：
if (当前b树不空)
{
根结点b进栈;
while (栈不空)
{
出栈结点p并访问之;
若p结点有右孩子，将其右孩子进栈；
若p结点有左孩子，将其左孩子进栈；
}
}
方法2： 考虑首先打印当前访问的结点。给出一个工作指针p，其初始指向该树的根节点，每次访问该结点将其打印和压栈(用于后续逐层向上访问右孩子)，并将其更新为左孩子（先序遍历的顺序所决定的） 当p为空时 代表左孩子已经打印完成，此时从最左下角的结点开始逐层向上打印右孩子 即 根-左-右 的顺序 也就是说，对于一个栈，当取出一个结点p时，可能其还有左孩子 对每个结点进行 先打印完自己和左孩子 然后逐层向上打印右孩子的过程 代码如下：
void PreOrder2(BTNode *b)
{
BTNode *p;
SqStack *st; // 定义一个顺序栈指针st
InitStack(st); // 初始化栈st
p = b;
while (!StackEmpty(st) || p != NULL)
{
while (p != NULL) // 访问结点p及其所有左下结点并进栈
{
printf("%c "，p->data); // 访问结点p
Push(st，p); // 结点p进栈
p = p->lchild; // 移动到左孩子
}
// 以下考虑栈顶结点
if (!StackEmpty(st)) // 若栈不空
{
Pop(st，p); // 出栈结点p
p = p->rchild; // 转向处理其右子树
}
}
printf("\n");
DestroyStack(st); // 销毁栈
}
2.中序遍历 与先序遍历的方法2类似，先把p以及p的左孩子迭代压栈，然后取出一个栈顶节点p，此时p->left==nullptr,所以根据中序遍历我们打印p->data,然后访问其右结点同理，将其赋值为p，以对其进行递归定义下的中序遍历 代码如下
void InOrder1(BTNode *b)
{
BTNode *p;
SqStack *st; // 定义一个顺序栈指针st
InitStack(st); // 初始化栈st
p = b;
while (!StackEmpty(st) || p != NULL)
{
while (p != NULL) // 扫描结点p的所有左下结点并进栈
{
Push(st，p); // 结点p进栈
p = p->lchild; // 移动到左孩子
}
// 以下考虑栈顶结点
if (!StackEmpty(st)) // 若栈不空
{
Pop(st，p); // 出栈结点p，访问结点p
printf("%c "，p->data);
p = p->rchild; // 转向处理其右子树
}
}
printf("\n");
DestroyStack(st); // 销毁栈
}
3.后序遍历 与中序遍历的方法类似，定义一个工作指针p指向当前正在处理的结点，和一个r结点表示刚刚打印完的结点，可以知道若p->rchild==r,则表示当前结点p->data可以打印了。 从p指向根节点出发，一直将p的左子树循环压栈，直到左子树为空，取出此结点，此时根据左-右-根的后序遍历的定义可以知道，应该处理此结点p的右子树了，当右子树为空，或右子树是刚刚打印过的结点，则可以将此取出的栈顶节点打印了。若右子树未访问过 则工作指针指向其右子树，由于要压栈 所以不能再出栈了 因此需要定义一个标志位flag表示要出栈还是入栈 代码如下：
void PostOrder1(BTNode *b) // 后序非递归遍历算法
{
BTNode *p， *r;
bool flag;
SqStack *st; // 定义一个顺序栈指针st
InitStack(st); // 初始化栈st
p = b;
do
{
while (p != NULL) // 扫描结点p的所有左下结点并进栈
{
Push(st，p); // 结点p进栈
p = p->lchild; // 移动到左孩子
}
r = NULL; // r指向刚刚访问的结点，初始时为空
flag = true; // flag为真表示正在处理栈顶结点
while (!StackEmpty(st) && flag)
{
GetTop(st，p); // 取出当前的栈顶结点p
if (p->rchild == r) // 若结点p的右孩子为空或者为刚访问结点 { printf("%c "，p->data); //访问结点p
Pop(st，p);
r = p; // r指向刚访问过的结点
}
else
{
p = p->rchild; // 转向处理其右子树
flag = false; // 表示当前不是处理栈顶结点
}
} while (!StackEmpty(st)); // 栈不空循环
printf("\n");
DestroyStack(st); // 销毁栈
}
用先，中序或中，后序 构造一个二叉树 定理1:给定先序序列和中序序列 可以唯一确定一颗二叉树 定理2:给定后序序列和中序序列 可以唯一确定一颗二叉树 证明：用数学归纳法 n=0时结论成立。 假设结点数
ahhhhhh