Featured image of post 二叉树
数据结构

二叉树

二叉树

n个结点的有限集合，可以是空数，也可以是由一个根节点和两个互不相交的左子树和右子树组成，子树本身又是一棵二叉树

  • 有序树
  • 递归定义

特殊二叉树概述

满二叉树

高度为h，含有$2^h-1$个结点的二叉树

  • 只有最后一层有叶子结点
  • 不存在度为1的结点
  • 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，如果存在父节点则为[i/2]

完全二叉树

当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

image-20221024141513067
  • 只有最后两层可能有叶子结点，且$i>[n/2]$，$i\leq[n/2]$则为分支结点
  • 最多只有一个度为1的结点，如果有两个以上，说明编号就没法一一对应，就不是完全二叉树
  • 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，如果存在父节点则为[i/2]

二叉排序树

可以为空树，其：

  • 左子树上所有结点关键字都小于根节点的关键字
  • 右子树的所有结点关键字都大于根节点的关键字 image-20221024142141321

平衡二叉树

书上任一结点的左子树和右子树的深度之差不超过1

image-20221024142259450

平衡二叉树其有更高的搜索效率

image-20211108191118703

常考性质

  1. 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则n0=n2+1

    • 设结点总数为n，则n=n0+n1+n2
    • n=n1+2n2+1
    • n0+n2一定为奇数

  2. 具有n(n>0)个结点的完全二叉树的高度h为$\lceil log_2(n+1) \rceil $或$\lfloor log_2(n) \rfloor +1$

    • 高为h的满二叉树共有2h-1个结点

  3. 完全二叉树最多有一个度为1的结点，即n1=0或1

  4. 若完全二叉树有偶数个结点，则必有n1=1，n0=k，n2=k-1

  5. 若完全二叉树有奇数个结点，则必有n1=0，n0=k，n2=k-1

顺序存储

1
2
3
4
5
6

#define Maxsize 100
typedef struct TreeNode{
    Elemetype data;
    bool isempty;
}TreeNode;
TreeNode t[Maxsize]; //依照从上至下从左到右的次序存储完全二叉树的各个节点

初始化时所有节点都标记为空isempty=true

非完全二叉树要使用以上逻辑判断则需要把二叉树的结点编号与完全二叉树对应起来

最坏情况：高度为h且只有h个结点的光棍树，也至少需要2h-1个存储单元

顺序存储只适合完全二叉树

链式存储

1
2
3
4

typedef struct BiTNode{
    ElemType data;
    struct BiTnode *left,*right;
}BiTNode,*BiTree;
  • n个结点的二叉链表共有n+1个空链域

初始化

1

BiTree root =NULL;

插入

1
2
3
4
5

root =(BiTree)malloc(sizeof(BiTNode));
root->data=1;
root->left=NULL;
root->right= NULL;
//插入根结点

1
2
3
4
5
6

//插入新结点
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=x;
p->left=NULL;
p->right=NULL;
root->left=p;

*三叉链表：多一个父节点指针

1
2
3
4
5

typedef struct BiTNode{
	ElemType data;
    struct BiTNode *left,*right;
    struct BiTNode *parent;
}BiTNode,*BiTree;

image-20211108195122160

二叉树遍历

先序遍历

  • 根-左-右

  • 分支节点逐层展开法：先初步写出初始的三结点次序，再递归进行填补空缺。

image-20211108200144337

  • 以此方法遍历算数表达式对应的分析树得出的序列称为前缀表达式
1
2
3
4
5
6
7

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);//根
        PreOrder(T->left);//左
        PreOrder(T->right);//右
    }
}

中序遍历

  • 左-根-右
  • 以此方法遍历算数表达式对应的分析树得出的序列称为中缀表达式（在合适的地方加入界限符即可转换为算术表达式）

其代码与前序遍历类似

后序遍历

  • 左-右-根
  • 以此方法遍历算数表达式对应的分析树得出的序列称为后缀表达式

其代码与前序遍历类似

三种遍历空间复杂度为O(h),h为树高

层序遍历

使用一个辅助队列：

  1. 根节点入队
  2. 若队列非空，队头结点出队，访问该节点，并将其左右孩子插入队尾
  3. 重复2直到队列非空
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

typedef struct BiTNode{
    char data;
    struct BiTNode *left,*right;
}BiTNode,*BiTree;
typedef struct _LinkNode{
    struct _LinkNode *next;
    BiTNode *data;
}*LinkNode;
typedef struct{
    LinkNode front,rear;
}*LinkQueue;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q,p); //队头结点出队
        visit(p);  //访问p结点
        if(p->left!=NULL) 
            EnQueue(Q,p->left); //左孩子存在，入队
        if(p->right!=NULL)
            EnQueue(Q,p->right) //右孩子存在，入队
    }
}

构造二叉树

如果只给出前/中/后/层的一种，不能唯一确定一棵二叉树

image-20221024152522932

前序+中序遍历序列

image-20211108204852452

  • 仍然是递归的思想

后序+中序

image-20211108204829279

层序+中序

image-20211108204800510

线索二叉树

以中序遍历寻找p结点前驱后继：

从根节点出发，重新进行中序遍历，指针q记录当前结点，指针pre记录上一个被访问的结点

  • 当q==p时，pre为前驱
  • 当pre==p时，q为后继

image-20211109143738996

于是诞生了线索二叉树(以下以中序为例)

image-20211109143953239

存储结构

1
2
3
4
5

typedef struct TreadNode{
    ElemType data;
    struct ThreadNode *left,*right;
    int ltag,rtag; //用于指明left，right指针是指向孩子还是前驱后继
}TreadNode,*ThreadTree;

image-20211109144557445

image-20211109144846656

二叉树的线索化

image-20211109145046316

1

TreadNode *pre=NULL; //全局变量pre指向当前访问结点的前驱

1
2
3
4
5
6
7
8
9

void CreateInTread(TreadTree T){
    pre=NULL;
    if(T!=NULL){
        InTread(T); //中序遍历处理T
        if(pre->right==NULL){
            pre->rtag=1;//处理最后一个节点
        }
    }
}

1
2
3
4
5
6
7
8

//中序遍历代码段
void InTread(TreadTree T){
    if(T!=NULL){
    	InTread(T->left);
        visit(T); //线索化
        InTread(T->right);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void visit(ThreadNode *q){
	if(q->left==NULL){
		q->left=pre;
		q->ltag=1;
	}
	if(pre!=NULL&&pre->right==NULL){
		pre->right=q;
        pre->rtag=1;
	}
    pre=q;
}

先序线索化与中序线索化类似，在递归遍历时需要加上tag判断。image-20211109151601507

后序线索化同理

线索二叉树寻找前驱/后继

中序

找p结点的后继next：

  1. 若p->rtag==1，next = p->rchild
  2. 若p->rtag==0，寻找p右子树中最左下的结点
1
2
3
4
5
6
7
8

//找到以P为根的子树中第一个被中序遍历的节点
ThreadNode *FirstNode(ThreadNode *p){
    //循环找到最左下角的结点
    while(p->ltag==0){
        p=p->left;
    }
    return p;
}

1
2
3
4
5
6

//在中序线索二叉树中找到结点p的后继节点
ThreadNode *NextNode(ThreadNode *p){
    //寻找右子树最左下节点
    if(p->rtag==0) return FirstNode(p->right);
    else return p->right;
}

1
2
3
4
5
6

//利用线索二叉树实现的非递归中序遍历算法，空间复杂度为O(1);
void Inorder(ThreadNode *T){
	for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){
        visit(p);
    }
}

找前驱pre：

  1. 若p->ltag==1，next = p->lchild
  2. 若p->ltag==0，寻找p左子树中最右下的结点
1
2
3
4
5

//找到以P为根的子树中，最后一个被中序遍历的结点
TreadNode *LastNode(ThreadNode *p){
    while(p->rtag==0) p=p->right;
    return p;
}

1
2
3
4
5

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    if(p->rtag==0) return LastNode(p->left);
    else return p->left;
}

1
2
3
4
5
6

//逆向中序遍历
void RevInorder(ThreadNode *T){
    for(ThreadNode *p=LastNode(T);p!=NULL;p=PreNode(p)){
        visit(p);
    }
}

先序

基于三叉链表实现

找p结点后继next：

  1. 若p->rtag==1，next = p->rchild
  2. 若p->rtag==0，
    • 若p有左孩子，则后继为左孩子
    • 若p没有左孩子，则后继为右孩子

image-20211110085427592

若p为根结点则其没有先序前驱

后序

前驱pre：

  1. 若p->ltag==1，pre = p->lchild
  2. 若p->ltag==0:
    • 若p有右孩子，则前驱为右孩子
    • 若p没有右孩子，则前驱为左孩子

后继next：

基于三叉链表实现

image-20221024154501009

如果p是根节点，则p没有后序后继，且后续线索二叉树需要栈的支持

树的存储结构

树是一种递归定义的数据结构

双亲表示法

image-20211110092359891

1
2
3
4
5
6
7
8
9

#define Maxsize 100
typedef struct{
    ElemType data;
    int parent;//双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[Maxsize];
    int n;//结点数
}PTree;
  • 优点：查找指定节点双亲很方便
  • 缺点：查指定结点的孩子只能从头遍历

孩子表示法(顺序+链式)

  • 顺序存储各个节点，每个节点保存孩子链表头指针
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct CTNode{
    int child;
    struct CTNode *next;
};
typedef struct{
    ElemType data;
    struct CTNode *firstChild;
}CTBox;
typedef struct{
    CTBox nodes[Max];
    int n,r;
}CTree;

孩子兄弟表示法(链式)

1
2
3
4

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

转换

  • 树与二叉树的转换：左孩子右兄弟法，即每个结点的左指针指向该节点的孩子，右指针指向该节点的兄弟

image-20211110095439330

  • 二叉树与森林的转换是唯一的

  • 简便转化画法：兄弟之间连线，每个节点只保留第一个孩子的连线，树根为轴心，顺时针旋转45°

  • 非终端结点引出的层的节点中必然有一个右指针域为空的结点，且该节点在引出层的最右侧(在原森林中看)

  • 所有右指针域为空的结点数=根节点+非终端结点数

© 2020 - 2023 Manticore的小站
总有些事情高于其他
Built with Hugo
主题 Stack 由 Jimmy 设计
本站访客数人次 总访问量次 本文阅读量次