当前位置：首页 > news >正文

数据结构—第五章树与二叉树

news 2025/8/30 7:57:44

（一）树的基本概念

基本术语：

兄弟：有相同双亲
堂兄弟：双亲不同，在同一层的结点
树的度：树中结点最大度数（孩子个数）
分支节点：度大于0的结点

（二）二叉树

二叉树的定义及其主要特征

特殊的二叉树：

满二叉树：每层都含有最多的结点
完全二叉树：除了最底层右端连续的结点可以不存在
二叉排序树：左子树小于根节点编号，右子树大于根节点编号
平衡二叉树：左子树与右子树高度差≤1
正则二叉树：树中只有度为0或2的结点

性质：

二叉树的子树有左右之分，其次序不能任意颠倒
n0=n2+1，度为0的结点个数=度为2的结点个数+1
n1=1/0，度为1的结点个数只可能是1或0

二叉树的顺序存储结构和链式存储结构

顺序存储：用一组连续的单元依次自上而下、自左至右存储完全二叉树上的结点（完全二叉树），普通的树通常只能添加一些并不存在的结点，让其与二叉树上的结点对照

链式存储：二叉链表至少包含3个域：数据域data，左指针域lchild，右指针域rchild

typedef struct BiTNde{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

二叉树的遍历

先序遍历、中序遍历、后序遍历，即visit(T)写在哪一行

// 先序遍历
void Order（BiTree T){if(T!=NULL){visit(T);Order(T->lchild);Order(T->rchild);}
}

层次遍历：自上而下、从左至右逐层遍历，代码用队列

void LevelOrder(BiTree T){InitQueue(q);BiTree p;EnQueue(q,T);while(!IsEmpty(q)){DeQueue(q,p);visit(p);if(p->lchild!=NULL)EnQueue(q,p->lchild);if(p->rchild!=NULL)EnQueue(q,p->rchild);}
}

先/前序序列：|根|左子树的先序序列|右子树的先序序列|

中序序列：|左子树的中序序列|根|右子树的中序序列|

后续序列：|左子树的后序序列|右子树的后序序列|根|

先序序列、后序序列、层序序列两两组合，无法唯一确认一棵树

线索二叉树的基本概念和构造

lchild	ltag	data	rtag	rchild

ltag/rtag：0表示指示结点孩子，1表示只是结点的前驱/后继

// 中序线索二叉树
void InThread(ThreadTree &p,ThreadTree &pre){		// pre表示前驱结点if(p!=NULL){InThread(p->lchild,pre);			// 线索化左子树if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;								// 标记当前结点即最后一次访问的结点InThread(p->rchild,pre);			// 线索化右子树}
}
void CreateInThread(ThreadTree T){ThreadTree pre=NULL;if(T!=NULL){InThread(T,pre);pre->rchild=NULL;pre->rtag=1;}
}

中序线索二叉树的遍历

// 求二叉树在中序序列下的第一个结点，即最左端的结点
ThreadNode *Firstnode(ThreadNode *p){while(p->ltag==0)p=p->lchild;return p;
}
// 求结点p的在中序序列下的后继
ThreadNode *Nextnode(ThreadNode *p){if(p->rtag==0)return Firstnode(p->rchild);else reurn p->rchild;
}
// 不含头结点的中序遍历算法
void Inorder(ThradNode *T){for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))visit(p);
}

（三）树、森林

树的存储结构

1.双亲表示法：根节点下标为0，其伪指针域为-1

#define MAX_TREE_SIZE 100
typedef struct{			// 描述一个结点ElemType data;int parent;			// 记录双亲小标
}PTNode;
typedef struct{			// 描述整个树PTNode nodes[MAX_TREE_SIZE];int n;				// 结点数
}PTree;

2.孩子表示法：每个结点的孩子结点视为一个链表

/*
0 R -> 1 -> 2 ->3
1 A -> 4 -> 5
2 B
3 C ->6
...
*/

3.孩子兄弟表示法（也称二叉树表示法）

每个节点包括：结点值、指向结点第一个孩子的指针、指向结点下一个兄弟结点的指针

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

森林与二叉树的转换

1.树转换为二叉树：每个结点的左指针指向它的第一个孩子，右指针指向它在树中相邻右兄弟（左孩子右兄弟）

2.森林转换为二叉树：森林中各棵树的根也可视为兄弟关系

树和森林的遍历

树的遍历：

先根遍历：先遍历根，再遍历子树
后根遍历：先遍历子树（同亲一层的话从左至右），再遍历根

森林的遍历：

先序遍历：先遍历根，再遍历子树，遍历完一棵树后遍历下一棵树
中序遍历：先遍历子树，再遍历根

树的后根遍历 / 森林的中序遍历对应于二叉树的中序遍历。

（四）树与二叉树的应用

哈夫曼树和哈夫曼编码

哈夫曼树定义：

结点的带权路径长度：从树的根到一个结点的路径长度与该结点上权值的乘积
树的带权路径长度WPL：所有叶节点的带权路径长度之和
哈夫曼树（最优二叉树）：带权路径长度（WPL）最小的二叉树

哈夫曼树性质：

每次选取两棵根节点权值最小的树
共构造n-1个结点，因此哈夫曼树结点总数为2n-1

哈夫曼编码定义：

固定长度编码：每个字符用等长的二进制位表示
可变长度编码：每个字符用不等长的二进制位表示
非常有效的数据压缩编码，权值为它出现的频度或次数

并查集及其应用

通常用树的双亲表示法作为并查集的存储结构

#define SIZE 100
int S[Size];
void Initial(int S[]){for(int i=0;i<SIZE;i++)S[i]=-1;
}
// Find操作
int Find(int S[],int x){while(S[x]>=0)x=S[x];return x;
}
// Union操作
void Union(int S[],int Root1,int Root2){Root1=Find(Root1),Root2=Find(Root2);			// 先找到两个根节点if(Root1==Root2&&Roo1!=-1)return;			// 因为用双亲表示法，根指向-1S[Root1]=Root2;
}
// 改进的Find操作
int Find(int S[],int x){int root=x;while(S[root]>=0)root=S[root];while(x!=root){			// 压缩路径int t=S[x];S[x]=root;x=t;}return root;
}
// 改进的Union操作
void Union(int S[],int Root1,int Root2){Root1=Find(Root1),Root2=Find(Root2);			// 先找到两个根节点if(Root1==Root2&&Roo1!=-1)return;if(S[Root2]>S[Root1]){			// 小树合并到大树，这里树根都是负数S[Root1]+=S[Root2];S[Root2]=Root1;}else{S[Root2]+=S[Root1];S[Root1]=Root2;}
}

不是很能看懂王道的代码，平时算法写的并查集代码：

int Find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
void Union(int u,int v){u=Find(u),v=Find(v);if(u==v)return;fa[u]=v;
}

小试牛刀：hdu3635、食物链、虫子的生活

堆及其应用

堆的本质是「完全二叉树」，堆只约束父与子的关系，不约束左右子节点的大小关系（如大根堆中，左子节点可大于或小于右子节点）

类型	堆序性规则	结构特点
大根堆（Max Heap）	任意父节点的数值 ≥ 其左右子节点的数值	根节点是整个堆的最大值
小根堆（Min Heap）	任意父节点的数值 ≤ 其左右子节点的数值	根节点是整个堆的最小值

堆的核心操作围绕 “维护堆序性” 展开，主要包括插入和 删除堆顶，两者的时间复杂度均为 O(log n)

插入操作：将新节点加入堆的末尾，再 “向上调整”