目录
在非空二叉树中，第i层上至多有2^(i-1)个结点 （i>=1）
对任何一棵二叉树，若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1
树
树的定义
- 结点之间有分支，具有层次关系的非线性结构
- 树是n（n>=0）个结点的有限集合T，若n=0时称为空树；
有且只有一个特殊的称为树的根结点
若n>1时，其余的结点被分为m个互不相交的子集，其中每个子集本身又是一棵树，称其为根的子树 - 树明显是一个递归的定义
- 根结点：非空树中无前驱结点的结点
- 结点的度、树的度：结点所拥有的子树的棵树称为结点的度。树中结点度的最大值称为树的度
- 叶子结点、非叶子结点：树中度为0的结点称为叶子结点（终端结点） 度不为0的结点称为非叶子结点（非终端结点或分支结点） 除根结点外，分支结点又称为内部结点
- 一个结点的子树的根称为该结点的孩子结点或子结点；相应地，该结点是其孩子结点的双亲结点；同一双亲结点的所有子结点互称为兄弟结点
- 层次;规定树中根结点的层次为1，其中结点的层次等于其双亲结点的层次加1
若某结点在第l(l≧1)层，则其子结点在第l+1层。
双亲结点在同一层上的所有结点互称为堂兄弟结点 - 从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。
结点p的层次路径上的所有结点（p除外）称为p的祖先(ancester) 。
以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent) - 树的深度：树中结点的最大层次值，又称为树的高度
- 有序树和无序树：对于一棵树，若其中每一个结点的子树从左至右具有一定的次序，则该树为有序树，否则称为无序树
- 森林：m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林（给森林中的各子树加上一个双亲结点，森林就变成了树）
- 树可以用嵌套集合的形式表示，也可以用广义表的形式表示
二叉树的定义
- 二叉树是n（n>=0）个结点的有限集合。若n=0时称为空树
若n>0时，有且只有一个特殊的称为树的根结点
若n>1时，其余的结点被分成为两个互不相交的子集T1,T2.分别称为左右子树，并且左、右子树又都是二叉树
二叉树的定义是递归的
- 特点：①每个结点最多有俩孩子；②二叉树有左右之分，其次序不能颠倒；③二叉树可以是空集合，根可以有空的左子树或空的右子树；
案例引入
数据压缩问题
将数据文件转换成由0.1组成的二进制串，称之为编码
利用二叉树求解表达式的值
若表达式为“第一操作数 运算符 第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式
二叉树的性质
在非空二叉树中，第i层上至多有2^(i-1)个结点 （i>=1）
至少有1个结点
深度为k的二叉树至多有2^k -1个结点 （k>=1)
深度为k的二叉树至少有k个结点
对任何一棵二叉树，若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1
总边数为B，则B = n-1 (n为结点数) B = n2*2+n1
则n = n2*2+n1+1 = n2+n1+n0 故n0=n2+1
完全二叉树
满二叉树 (深度为k且有2^k -1个结点)
- 满二叉树的特点
①每一层上的结点数总是最大结点数（每层都满）
②满二叉树的所有的分支结点都有左、右子树
③叶子结点全部在最底层
- 对满二叉树的结点进行连续编号，从根结点开始，按“从上而下，自左至右”的原则进行
- 满二叉树在同样深度的二叉树中结点个数最多
- 满二叉树在同样深度的二叉树中叶子结点个数最多
完全二叉树
- 如果深度为k,n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树
- 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一颗完全二叉树
- 特点：①叶子只可能分布在层次最大的两层上； ②对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1
- 满二叉树一定是完全二叉树
二叉树的存储结构
顺序存储结构
按满二叉树的结点层次编号，依次存放二叉树中的数据元素
二叉树顺序存储的类型定义
//二叉树顺序存储表示
#define MAXTSIZE 100
Typedef TElemType SqBiTree[MAXTSIZE];
SqBiTree bt;空结点在顺序存储中表示为0或空
顺序存储的缺点
深度为k的且只有k个结点的单支树需要长度为2^k-1的一维数组
浪费空间 ；适合存储满二叉树和完全二叉树
链式存储结构
二叉链表存储结构(有头指针)
typedef struct BiNode{
TElemType data;
struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;在n个结点的二叉链表中，有n+1个空指针域
三叉链表存储结构(有头指针)，主要找前驱
typedef struct TriTNode{
TElemType data;
struct TriNode *lchild,*parent,*rchild; //左右孩子指针，及前驱结点
}TriNode,*TriTree;遍历二叉树 O(n)
- 遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O(n)
DLR——先(根)序遍历
LDR——中(根)序遍历
LRD——后(根)序遍历 (根结点必在后序序列尾部)
- 由二叉树的先序序列和中序序列，或由后序序列和中序序列可以确定唯一一棵二叉树
递归遍历
时间效率 O(n) //每个结点只访问一次
空间效率 O(n) //栈占用的最大辅助空间
先序遍历二叉树
Status PreOrderTraverse(BiTree T){
if(T == NULL) return OK; //空二叉树
else{
cout<<T -> data; //访问根结点
PreOrderTraverse(T -> lchild); //递归遍历左子树
PreOrderTraverse(T -> rchild); //递归遍历右子树
}
}中序遍历二叉树
Status InOrderTraverse(BiTree T){
if(T == NULL) return OK; //空二叉树
else{
InOrderTraverse(T -> lchild); //递归遍历左子树
cout<<T -> data; //访问根结点
InOrderTraverse(T -> rchild); //递归遍历右子树
}
}后序遍历二叉树
Status PostOrderTraverse(BiTree T){
if(T == NULL) return OK; //空二叉树
else{
PostOrderTraverse(T -> lchild); //递归遍历左子树
PostOrderTraverse(T -> rchild); //递归遍历右子树
cout<<T -> data; //访问根结点
}
}非递归算法
中序遍历
①建立一个栈；
②根结点进栈，遍历左子树；直到左子树为空
③根结点出栈，输出根结点，遍历右子树
void InOrderTraverse(BiTree T){
InitStack(S); p=T;
q = new BiTNode;
while(p || !StackEmpty(S)){
if(p){ //p非空
Push(S,p); //根指针进栈,但不访问
p = p->lchild; //根指针进栈，遍历左子树
}else{
Pop(S,q); //退栈
cout << q->data; //访问根结点
p = q->rchild; //遍历右子树
}
}
}层次遍历
对于一棵二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点；每个结点仅仅访问一次
算法设计思路
①将根结点进队
②队不空时循环：从队列中出队一个结点p，访问它；
若它有左孩子结点，将左孩子结点进队；
若它有右孩子结点，将右孩子结点进队；
使用循环队列类型定义
typedef struct{
BTNode data[MaxSize]; //存放队中元素
int front,rear; //队头和队尾指针
}SqQueue; //顺序循环队列类型二叉树层次遍历算法
void LevelOrder(BTNode *b){
BTNode *p; SqQueue *qu;
InitQueue(qu); //初始化队列
enQueue(qu,b); //根结点指针进入队列
while(!QueueEmpty(qu)){ //队不为空，则循环
deQueue(qu,p); //出队结点p
cout << p->data; //访问结点p
if(p -> lchild != NULL)
enQueue(qu,p->lchild); //有左孩子时将其入队
if(p -> rchild != NULL)
enQueue(qu,p->rchild); //有右孩子时将其入队
}
}二叉树遍历算法的应用
按先序遍历的算法建立二叉链表
- 从键盘输入二叉树的结点信息（包括空结点，空结点的位置同样是先序遍历时的位置，图中的结点必须要有两个子结点），从而确定二叉树的具体存储结构
- 在建立二叉树的过程中按二叉树先序方式建立
void CreateBiTree(BiTree &T){
//按先序次序输入二叉树中节点的值，创建二叉链表表示的二叉树T
cin >> ch;
if(ch == '#') T=NULL; //递归结束，创空树
else{
T = new BiTNode; //生成根结点
T -> data = ch; //根结点数据域置为ch
CreateBiTree(T -> lchild); //递归创建左子树
CreateBiTree(T -> rchild); //递归创建右子树
}
}
复制二叉树
void Copy(BiTree T, BiTree &NewT){
if(T == NULL){
newT = NULL;
return;
}
else{
NewT = new BiTNode;
NewT -> data = T -> data; //复制根结点
Copy(T->lchild, NewT->lchild); //递归复制左子树
Copy(T->rchild, NewT->rchild); //递归复制左子树
}
}计算二叉树的深度
int Depth(BiTree T){
if(T == NULL) return 0; //如果是空树，深度为0，递归结束
else{
m = Depth(T -> lchild); //递归计算左子树的深度记为m
n = Depth(T -> rchild); //递归计算左子树的深度记为n
if(m > n) return(m+1); //二叉树的深度为m与n的较大者加1
else return(n+1);
}
}统计二叉树中结点的个数
int NodeCount(BiTree T){
//统计二叉树T中结点的个数
if(T == NULL) return 0; //如果是空树，则结点个数为0，递归结束
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}统计二叉树中叶子结点的个数
int LeadCount(BiTree T){
if(T == NULL) return 0; //如果是空树，返回0
if(T->lchild == NULL && T->rchild == NULL)
return 1; //如果是叶子结点返回1
else return LeafCount(T->lchild)+LeafCount(T->rchild);
}线索二叉树
- 二叉树的线索化就是按照某种遍历次序使二叉树成为线索二叉树的过程
- 线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程
- 设一棵二叉树有n个结点，则有n-1条边；而n个结点共有2n个指针域（Lchild和Rchild）,显然有n+1个空闲指针域未用
- 指向结点前驱和后继的指针叫做线索
为了避免D结点的前驱和I结点的后继悬空，则增设一个头结点。Itag = 0,lchild指向根结点，rtag= 0，rchild指向遍历序列中最后一个结点。数据域置为空
遍历序列中第一个结点的lchild域和最后一个结点的rchild域均指向头结点
//二叉树的二叉线索存储表示
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild; //左右孩子指针
int LTag,RTag; //左右标志
}BiThrNode,*BiThrTree;以结点p为根的子树中序线索化
void InThreading(BiThrTree p){
//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
if(p){
InThreading(p->lchild); //左子树递归线索化
if(!p -> lchild){ //p的左子树为空
p -> LTag = 1; //给p加上做线索
p -> lchild = pre; //p的左孩子指针指向前驱
}
else p->LTag = 0;
if(!pre -> rchild){ //pre的右孩子为空
pre -> RTag = 1; //给pre加上右线索
pre -> rchild = p; //pre的右孩子指针指向p（后继）
}
else p->RTag = 0;
pre = p; //把pre指向刚访问过的结点p
InThreading(p -> rchild); //右子树递归线索化
}
}带头结点的二叉树中序线索化
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
Thrt = new BiThrNode; //建头结点
Thrt -> LTag = 0; //头结点有左孩子，若树非空，则其左孩子为树根
Thrt -> RTag = 1; //头结点的右孩子指针为右线索
Thrt -> rchild = Thrt; //初始化时右指针指向自己
if(!T) Thrt->lchild = Thrt; //若树为空，则左指针也指向自己
else{
Thrt -> lchild = T;
pre = Thrt; //右结点的左孩子指向根,pre初值指向头结点
InThreading(T);
pre -> rchild = Thrt; //上述算法结束之后，pre为最右结点，pre的右线索指向头结点
pre -> RTag = 1;
Thrt -> rchild = pre; //头结点的右线索指向pre
}
}遍历中序线索二叉树 时O(n) 空O(1)
void InOrderTraverse_Thr(BiThrTree T){
//T指向头结点，头结点的左链lchild指向根结点
//中序遍历二叉线索树T的非递归算法
p = T->lchild; //p指向根结点
while(p != T){ //空树或遍历结束时，p == T
while(p -> LTag == 0) p = p->lchild;
cout << p-> data;
while(p -> RTag == 1 && p -> rchild != T){
p = p->rchild;
cout << p-> data;
}
p = p -> rchild;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/83253.html
