数据结构——树和二叉树
树
树的定义
树（Tree）是n（n≥0）个结点的有限集，它或为空树（n = 0）；或为非空树，对于非空树T：
有且仅有一个称之为根的结点；
除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
树是n个结点的有限集
树的其他表示方式
树的概念
每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
树的基本术语
根：即根结点(没有前驱)
叶子：即终端结点(没有后继)
节点：即树的数据元素
节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
分支节点：即度不为0的结点（也称为内部结点）
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
树的种类
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
二叉树：每个节点最多含有两个子树的树称为二叉树；
完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
常见应用场景
xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
路由协议就是使用了树的算法
mysql数据库索引
文件系统的目录结构
所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构
二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
有且仅有一个称之为根的结点；
除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
基本特点
结点的度小于等于2
有序树（子树有序，不能颠倒）
二叉树的性质
在二叉树的第i层上至多有2^(i-1)个结点
深度为k的二叉树至多有2^(k-1)个结点
对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）
具有n个结点的完全二叉树的深度必为[log2n]＋1
对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。
二叉树节点表示
案例ly01.py
二叉树遍历
深度优先，一般用递归
先序(Preorder)
中序(Inorder)
后序(Postorder)
广度优先，一般用队列
满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
满足等比数列公式，具有如下性质
满二叉树的结点数一定是奇数个
第i层上的结点数为：2^i-1
层数为k的满二叉树的叶子结点个数（最后一层）: 2^k-1
国外（国际）定义：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)）
度为0或者2，不存在度为1的结点
满二叉树和完全二叉树的区别
满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 
#include
#include
using namespace std;
#define OVERFLOW -2
#define OK 1
#define NULL 0
#define ERROR -1
#define MAXSIZE 100
typedef int Status;
typedef char TelemType;
/*------------------二叉树顺序存储----------------*/
/*
适于存满二叉树和完全二叉树
*/
// typedef TelemType SqBiTree[MAXSIZE];
// SqBiTree bt; // 包含100存放TelemType类型数据的数组
/*-----------------二叉树链式存储------------------*/
/*
二叉链表
*/
typedef struct BiTNode {
TelemType data; // 结点数据域
struct BiTNode* lchild, * rchild; // 左右子树指针
int flag; // 后序遍历标志位
}BiTNode, * BiTree;
typedef BiTree SElemType;
typedef struct {
BiTNode* link;
int tag; // 后序遍历标志位
}BElemType;
// 顺序栈结构体
typedef struct {
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
// 顺序栈初始化
Status InitStack(SqStack& S) {
S.base = new SElemType[MAXSIZE];
if (!S.base) return OVERFLOW;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
// 判断顺序栈是否为空
bool StackEmpty(SqStack S) {
if (S.top == S.base) return true;
else return false;
}
// 判断是否为满栈
bool StackFull(SqStack S) {
if (S.top - S.base >= S.stacksize)
return true;
else return false;
}
// 入栈
Status Push(SqStack& S, BiTree e) {
if (StackFull(S)) // 满栈
return ERROR;
*S.top++ = e;
// *S.top = e;
// S.top ++;
return OK;
}
// 出栈
Status Pop(SqStack& S, BiTree& e) {
if (StackEmpty(S)) // 栈空
return ERROR;
e = *--S.top;
// S.top --;
// e = *S.top;
return OK;
}
/*
# 遍历规则
- 若二叉树为空树，则空操作
- DLR-先序遍历，先根再左再右
- LDR-中序遍历，先左再根再右
- LRD-后序遍历，先左再右再根
*/
/*--------先序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
访问根结点 (D)
中序遍历左子树 (L)
中序遍历右子树 (R)
*/
void PreOrder(BiTree T) {
if (T) {
cout << T->data;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
// 非递归算法
void PreOrder_1(BiTree T) {
SqStack S;
InitStack(S);
BiTree p = T;
while (p || !StackEmpty(S)) {
// p非空且栈非空
if (p) {
/*
输出元素
保存入栈
p = p->lchild
*/
cout << p->data;
Push(S, p);
p = p->lchild;
}
else {
/*
出栈到p
p = p->rchild
*/
Pop(S, p);
p = p->rchild;
}
}
}
/*--------中序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
中序遍历左子树 (L)
访问根结点 (D)
中序遍历右子树 (R)
*/
void InOrder(BiTree T) {
if (T) {
InOrder(T->lchild);
cout << T->data;
InOrder(T->rchild);
}
}
// 非递归算法
void InOrder_1(BiTree T) {
BiTree p = T;
SqStack S;
InitStack(S);
while (p || !StackEmpty(S)) {
if (p) {
/*
保存--入栈
p = p->lchild
*/
Push(S, p);
p = p->lchild;
}
else {
/*
出栈到p
输出p->data
p = p->rchild
*/
Pop(S, p);
cout << p->data;
p = p->rchild;
}
}
}
/*
/*--------后序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
中序遍历左子树 (L)
中序遍历右子树 (R)
访问根结点 (D)
*/
void PostOrder(BiTree T) {
if (T) {
PostOrder(T->lchild);
PostOrder(T->rchild);
cout << T->data;
}
}
// 非递归算法
void PostOrder_1(BiTree T) {
/*
此函数应将数据类型改为"结点+标志位"，即上面代码中BElemType类型
但由于修改类型后，需重新改写栈相关函数，故将标志位作为结构体BiTNode参数
*/
BiTree p = T;
SqStack S;
// BElemType w;
InitStack(S);
while (p || !StackEmpty(S)) {
if (p) {
/*
保存--入栈 flag = 1（结构体 p,flag）
p = p->lchild
*/
// w.link = p;
// Push(S,w);
Push(S, p);
p->flag = 1;
// w.tag = 1;
p = p->lchild;
}
else {
/*
出栈到p
switch(flag){
case '1':
入栈 flag = 2
p = p->rchild
case '2'
输出 p->data
p = NULL
}
保存--入栈
p = p->rchild;
*/
// Pop(S, w);
Pop(S, p);
// p = w.link;
switch (p->flag) {
case 1:
p->flag = 2;
// w.tag = 2;
Push(S, p);
p = p->rchild;
break;
case 2:
cout << p->data;
// 强制置空
p = NULL;
break;
}
}
}
}
// 求二叉树叶子结点的个数
int CountLeaf(BiTree T) {
// 先序遍历
// 此处必须为static类型，递归会调用自身，只赋一次值
static int count = 0;
if (T) {
if (!T->lchild && !T->rchild)
count++;
CountLeaf(T->lchild);
CountLeaf(T->rchild);
}
return count;
}
// 求二叉树深度
/*
1. 求左二叉树深度
2. 求右二叉树深度
3. 取最大值加1
*/
int Depth(BiTree T) {
// 后序遍历
int dl, dr, d;
if (!T)
d = 0;
else {
dl = Depth(T->lchild);
dr = Depth(T->rchild);
d = 1 + (dl > dr ? dl : dr);
}
return d;
}
// 复制二叉树
BiTree Copy(BiTree T) {
BiTree t, newl, newr;
if (!T) {
t = NULL;
return t;
}
else {
if (!T->lchild)
newl = NULL;
else
newl = Copy(T->lchild);
if (!T->rchild)
newr = NULL;
else
newr = Copy(T->rchild);
t = new BiTNode;
t->data = T->data;
t->lchild = newl;
t->rchild = newr;
}
return t;
}
// 先序创建二叉树
Status CreateBiTree(BiTree& T) {
char ch;
cin >> ch;
if (ch == '#') T = NULL;
else {
if (!(T = new BiTNode)) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
int main() {
// 测试
BiTree T, t;
int n;
CreateBiTree(T);
// 递归遍历
cout << "先序遍历为：" << endl;
PreOrder(T);
cout << endl << "中序遍历为：" << endl;
InOrder(T);
cout << endl << "后序遍历为： " << endl;
PostOrder(T);
cout << endl;
// 叶子结点个数测试
cout << "叶子结点个数为: " << CountLeaf(T) << endl;
// 求树深度测试
cout << "树的深度为：" << Depth(T) << endl;
// 复制测试
t = Copy(T);
cout << "t 的先序遍历为： " << endl;
PreOrder(t);
cout << endl;
/*
// 非递归遍历
cout << "先序遍历为：" << endl;
PreOrder_1(T);
cout << endl;
cout << "中序遍历为：" << endl;
InOrder_1(T);
cout << endl;
cout << "后序遍历为：" << endl;
PostOrder_1(T);
cout << endl;
*/
return 0;
}
ab##c##
先序遍历为：
abc
中序遍历为：
bac
后序遍历为：
bca
叶子结点个数为: 2
树的深度为：2
t 的先序遍历为：
abc
'''案例ly01.py'''
class Node(object):
'''节点类'''
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem;
self.lchild = lchild
self.rchild = rchild
class Tree(object):
'''树类'''
def __init__(self, root=None):
self.root = root
def add(self, elem):
'''为树添加节点'''
node = Node(elem)
# 如果树是空的，则对根节点赋值
if self.root == None:
self.root = node
else:
queue = []
queue.append(self.root)
# 对已有的节点进行层次遍历
while queue:
# 弹出队列的第一个元素
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
elif cur.rchild == None:
cur.rchild = node
return
else:
# 如果左右子树都不为空，加入队列继续判断
queue.append(cur.lchild)
queue.append(cur.rchild)
def preorder(self, root):
'''递归实现先序遍历'''
if root == None:
return
print(root.elem)
self.preorder(root.lchild)
self.preorder(root.rchild)
def inorder(self, root):
'''递归实现中序遍历'''
if root == None:
return
self.inorder(root.lchild)
print(root.elem)
self.inorder(root.rchild)
def postorder(self, root):
'''递归实现后序遍历'''
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print(root.elem)
def breadth_travel(self, root):
'''利用队列实现树的层次遍历'''
if root == None:
return
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print(node.elem)
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
if __name__ == '__main__':
t = Tree()
for i in range(10):
t.add(i)
t.preorder(t.root)
print('*' * 20)
t.inorder(t.root)
print('*' * 20)
t.postorder(t.root)
print('*' * 20)
t.breadth_travel(t.root)
0
1
3
7
8
4
9
2
5
6
********************
7
3
8
1
9
4
0
5
2
6
********************
7
8
3
9
4
1
5
6
2
0
********************
0
1
2
3
4
5
6
7
8
9
[Finished in 0.1s]
线索二叉树
对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
n 个结点的二叉链表中必定存在 n+1 个空链域，因此可利用这些空链域来存放结点的前驱和后继信息。
二叉链表加一头结点，lchild 域的指针指向二叉树的根结点，rchild 域的指针指向中序遍历时访问的最后一个结点。
二叉树中序序列中第一个结点的lchild 域的指针和最后一个结点rchild 域的指针均指向头结点。
/*---------二叉树的二叉线索存储表示---------*/
typedef int ElemType;
typedef enum PointerTag {Link, Thread}; // Link==0:指针，Thread==1:线索
typedef struct BiThrNode {
ElemType data; // 数据域
struct BiThrNode* lchild, * rchild; // 左右孩子指针
PointerTag LTag, Rtag; // 左右标志
}BiThrNode, * BiThrTree;
线索二叉树的术语
线索：指向结点前驱和后继的指针
线索链表：加上线索二叉链表
线索二叉树：加上线索的二叉树（图形式样）
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程
/*----------以结点p为根的子树中序线索化---------*/
void InThreading(BiThrTree p, BiThrNode *&pre) {
if (p) {
InThreading(p->lchild, pre); // 递归线索化左子树
if (!p->lchild) {
p->LTag = Thread; // 前驱线索化
p->lchild = pre; // p的左孩子指针指向pre(前驱)
}
if (!pre->rchild) {
// 前驱无右孩子
pre->RTag = Thread; // 后继线索
pre->rchild = p; // 前驱右孩子指向后继
}
pre = p;
InThreading(p->rchild, pre); // 递归线索化右子树
}
}
树和森林
树的存储结构
双亲表示法
以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。
特点：找双亲容易，找孩子难
孩子链表表示法
每个结点有多个指针域，分别指向其子树的根。
树的二叉链表(孩子-兄弟）存储表示法
/*----树的存储结构->二叉链表表示法----*/
typedef struct CSNode {
ElemType data;
struct CSNode* firstchild, * nextsibling;
}CSNode, * CSTree;
将树转化为二叉树
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的连线
旋转：以树的根结点为轴心，将整棵树顺时针转45°
树转换成的二叉树其右子树一定为空
将二叉树转换成树
加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列,形成树结构
树的先序遍历与二叉树先序遍历相同树的后序遍历相当于对应二叉树的中序遍历