树
树的定义
- 树(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层是满的,但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
************************************
C++代码实现
#include<iostream>
#include<queue>
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
************************************
python代码实现
'''案例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); // 递归线索化右子树
}
}
树和森林
树的存储结构
- 双亲表示法
– 以一组连续空间存储树的结点,同时在结点中附设一个指针,存放双亲结点在链表中的位置。
– 特点:找双亲容易,找孩子难 - 孩子链表表示法
– 每个结点有多个指针域,分别指向其子树的根。 - 树的二叉链表(孩子-兄弟)存储表示法 `cpp
/*—-树的存储结构->二叉链表表示法—-*/
typedef struct CSNode {
ElemType data;
struct CSNode* firstchild, * nextsibling;
}CSNode, * CSTree; “`
将树转化为二叉树
- 加线:在兄弟之间加一连线
- 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的连线
- 旋转:以树的根结点为轴心,将整棵树顺时针转45°
树转换成的二叉树其右子树一定为空
将二叉树转换成树
- 加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与p的双亲用线连起来
- 抹线:抹掉原二叉树中双亲与右孩子之间的连线
- 调整:将结点按层次排列,形成树结构
树的先序遍历与二叉树先序遍历相同
树的后序遍历相当于对应二叉树的中序遍历
正文完