数据结构_树和二叉树
树
数据的逻辑结构中的非线性结构的树
- 树的定义（循坏定义）：
（1）有且仅有一个根结点
（2）除根结点外为m个互不相交的树，称为子树。 - 树的表示
- 树的基本术语
结点：树中的一个独立单位。包含一个数据元素及若干指向其子树的分支。
结点的度：结点拥有的子树数目
树的度：树内各结点的度的最大值
叶子（终端结点）：度为0的结点
双亲和孩子：结点的子树被称为孩子，相应的该结点称为孩子的双亲
兄弟：同一个双亲的结点之间互称为兄弟
祖先：根结点到改结点的路劲上所有的结点（双亲的双亲的双亲。。）
子孙：对应祖先，从该结点为根的所有子树的任一结点被称为它的子孙
层次：从根开始定义，根为第一层，根的孩子为第二层（类似辈分）
堂兄弟：同一层次
树的深度：树的最大层次
森林：m棵互不相交的树的集合
二叉树
二叉树时特殊的树，根结点的度至多为2，被称为左子树和右子树。
二叉树的基本知识
- 二叉树的性质
结点与孩子、双亲、兄弟和堂兄弟之间的对应关系。序号为从根结点开始，从左到右的顺序。
性质的证明：
（1）由二叉树的定义可知，结点的度数至多为2。第 1 层有1个根结点，那么第二层就为2^1,类推总结得结论
（2）每一层得最多数目可知（满二叉树就是每一层的结点数都为最大值）
（3）因为总结点数n=n0+n1+n2(度为0，1，2的结点数之和)；也等于根结点和每一个结点对应的度数之和（一个结点若度数为0，那么它的孩子数为零，若为1，那么它的孩子结点数为1，若为2，那么孩子数目为2。孩子的总数加上根结点）即n=1+n1+2*n2。俩式子相等，结果为n0=n2+1
- 二叉树的分类
满二叉树：深度为k，且结点数为2^(i+1)-1 （二叉树的每一层结点数为最大值）
完全二叉树：叶子结点只能在层数最大的两层出现（即若其右分支的子孙的最大层次为i，那么其左子树的最大层次必为i+1）
二叉树的存储结构
1.顺序存储
根据结点在树中的序号将其顺序存储入一个数组。该存储方式只适用于满二叉树。
#define MAX 100
//数据元素（更改数据元素，修改基本元素结构体和接口的实现即可）
typedef struct item {
//数据项
int data;
bool operator==(const item& a) {
return data == a.data;
}
}Item;
typedef Item Btree[MAX];
Btree T;
2.链式存储
由二叉树的定义可知，一个结点包含一个数据域、一个左指针（指向左子树）和一个右指针，并有一个指针指向根结点。
#pragma once
#include<stdbool.h>
#include<stdio.h>
//数据元素（更改数据元素，修改基本元素结构体和接口的实现即可）
typedef struct item {
//数据项
int data;
bool operator==(const item& a) {
return data == a.data;
}
}Item;
typedef struct node {
Item data;
struct node* Lnode, * Rnode;
}BTnode, * BTree;
二叉树的遍历
理论
遍历二叉树就是按照某条搜索路径巡防树中的每个结点，使得每个结点被有且仅访问一次。它时实质是将非线性结构的树转化为一个线性序列。
- 前序遍历
（1）操作：先遍历根结点，再遍历左子树，最后右子树。
（2）如图的遍历结果为：A B C D E F G H
- 中序遍历
（1）操作：先遍历左子树，再遍历根结点，最后右子树。
（2）如图的遍历结果为：B D C E A F H G
- 后序遍历
（1）操作：先遍历左子树，再遍历右子树，最后根结点
（2）如图的遍历结果为：D E C B H G F A
注：由前序遍历和后序遍历不可唯一确定一颗二叉树，因为（根左右和左右根）只有左子树（右子树）时根据遍历结果无法判断它是左子树还是右子树。
例如下图中的两棵树的前序和后序遍历结果相同。
4. 层次遍历
从第一层开始，从左到右依次遍历
实现思路和函数代码
代码实现的是中序遍历，前序和后序实现差异不大。
- 中序遍历的递归实现
由定义可知遍历的操作是嵌套的，所以采用递归算法实现。
如中序遍历的规矩是，左根右，那么将根结点的左子树和右子树看作以根结点左右孩子为根结点的树，反复嵌套。
//中序遍历的递归实现
void Inorder_traverse(BTree T) {
if (T) {
Inorder_traverse(T->Lnode);//左子树
T->Data.printf(); //输出根的值
Inorder_traverse(T->Rnode);//右子树
}
}
- 中序遍历的非递归实现
非递归实现需要借助栈这个数据结构，如有需要可以查看本专栏的栈知识: 数据结构_栈和队列.
//中序遍历的非递归实现
void Inorder_traverse1(BTree T) {
//栈的初始化
Lkstack S;
Lkstackinit(S);
BTree p = T;
BTnode* q = new BTnode; //保存回溯点
while (p || S) {
if (p) { //结点不为空入栈
Item e;
e.n = *p;
Push(S,e);
p = p->Lnode; //左子树，直到左子树为空
}
else { //左子树为空，回溯其双亲结点并输出，然后遍历其右子树
Item e;
Pop(S, e);
*q = e.n;
q->Data.printf(); 在这里插入代码片
p = q->Rnode;
}
}
Lkstackfree(S);
}
- 层次遍历的实现
层次遍历的实现需要借助队列，相关内容可以查看：数据结构_栈和队列.
//层次遍历
二叉树的线索化
理论
之前说二叉树的存储结构的链式存储结构知道，二叉树右左右两个指针分别指向左右孩子，由性质知道，满二叉树第i层结点数为2^(i-1)，如果它是最后一层，那么将这些结点的左右指针全部浪费。为了更好的利用资源，所以在这为空的左右指针中存储一些有用的信息（通常为该结点在前、中和后序遍历序列的前后驱结点）。这些指向前后驱结点的指针被称为线索，二叉树被称为线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。
代码实现
//线索化
BTree pre=NULL;
void Inorder_threading(BTree T) {
if (T) {
Inorder_threading(T->Lnode); //左子树
if (!T->Lnode) {
T->Ltag = 1;
T->Lnode = pre;
}
else
T->Ltag = 0; //根
if (pre) {
if (!pre->Rnode) {
pre->Rtag = 1;
pre->Rnode = T;
}
else
pre->Rtag = 0;
}
pre = T;
Inorder_threading(T->Rnode); //右子树
}
}
//遍历线索化二叉树
void Inorder_threadBTree(const BTree T) {
BTree p = T;
while(p) {
while (p->Ltag == 0) //遍历到最左结点
p = p->Lnode;
p->Data.printf();
while (p->Rtag == 1&& p->Rnode) { //左子树遍历完后，右子树不存在，后继结点存在，转向后继结点。
p = p->Rnode; p->Data.printf();
}
//右子树存在
p = p->Rnode;
}
}
完整的代码（二叉树遍历和线索）
代码
头文件 BTree.h
#pragma once
#include<stdbool.h>
#include<stdio.h>
#define MAX 100
//二叉树数据元素（更改数据元素，修改基本元素结构体和接口的实现即可）
typedef struct item1 {
//数据项
int data;
bool operator==(const item1& a) {
return data == a.data;
}
void printf() {
fprintf(stdout,"%c", data);
}
}Item1;
//二叉树结点
typedef struct node {
Item1 Data;
struct node* Lnode, * Rnode;
int Ltag, Rtag;
}BTnode, * BTree;
///
/// 栈的实现
///
//栈数据元素（更改数据元素，修改基本元素结构体和接口的实现即可）
typedef struct item {
//数据项
BTnode n;
bool operator==(const item& a) {
return n.Data.data == a.n.Data.data;
}
void printf() {
fprintf(stdout, "%c", n.Data.data);
}
}Item;
typedef struct Stack {
Item e;
struct Stack* next;
}Stack, * Lkstack;
//栈初始化
bool Lkstackinit(Lkstack& L);
//入栈
bool Push(Lkstack& L, Item e);
//出栈
bool Pop(Lkstack& L, Item& e);
//栈取值
bool GetItem(const Lkstack L, Item& e);
///
/// 队列的实现
///
///
typedef struct {
Item* base;
int front;
int rear;
}Queue;
//初始化
bool QueueInit(Queue& q);
//求队列长度
int Queuelen(const Queue q);
//入队
bool QueueEn(Queue& q, Item e);
//出队
bool QueueOut(Queue& q, Item& e);
//取头元素
bool GetItem(const Queue q, Item& e);
主函数
#include<stdio.h>
#include<stdlib.h>
#include"Btree.h"
///--------------------------------------------
/// 栈操作的接口实现
/// -------------------------------------------
//栈初始化
bool Lkstackinit(Lkstack& L) {
L = NULL;
return true;
}
//入栈
bool Push(Lkstack& L, Item e) {
Lkstack p = new Stack;
p->e = e;
p->next = L;
L = p;
return true;
}
//出栈
bool Pop(Lkstack& L, Item& e) {
if (!L)
return false;
e = L->e;
Lkstack p = L;
L = L->next;
delete p;
return true;
}
//栈取值
bool GetItem(const Lkstack L, Item& e) {
if (!L)
return false;
e = L->e;
return true;
}
//栈释放
void Lkstackfree(Lkstack& L) {
Lkstack p = NULL;
while (L) {
p = L->next;
delete L;
L = p;
}
}
///--------------------------------------------
/// 队列的操作实现接口
/// -------------------------------------------
//初始化
bool QueueInit(Queue& q) {
q.base = new Item[MAX];
if (!q.base)
return false;
q.front = q.rear = 0;
return true;
}
//求队列长度
int Queuelen(const Queue q) {
return (q.rear-q.front)%MAX;
}
//入队
bool QueueEn(Queue& q, Item e) {
if ((q.rear + 1) % MAX == q.front)
return false;
q.base[q.rear] = e;
q.rear = (q.rear + 1) % MAX;
return true;
}
//出队
bool QueueOut(Queue& q, Item& e) {
if (q.front==q.rear)
return false;
e=q.base[q.front];
q.front = (q.front + 1) % MAX;
return true;
}
//取头元素
bool GetItem(const Queue q, Item& e) {
if (q.front == q.rear)
return false;
e = q.base[q.front];
return true;
}
//释放队列
void Sqqueuefree(Queue& q) {
if (q.base) {
free(q.base);
}
}
///--------------------------------------------
/// 遍历操作
/// -------------------------------------------
//先序遍历创建树
//printf("请输入前序遍历的二叉树序列：（‘#’为空）\n");
void Creat_BTree(BTree &T) {
char ch;
ch = getchar();
if (ch == '#') T = NULL;
else if (ch == '\n');
else {
T = new BTnode;
T->Data.data = ch;
Creat_BTree(T->Lnode);
Creat_BTree(T->Rnode);
}
}
//前序遍历的递归实现
void Forder_traverse(const BTree T) {
if (T) {
T->Data.printf();
Forder_traverse(T->Lnode);
Forder_traverse(T->Rnode);
}
}
//中序遍历的递归实现
void Inorder_traverse(const BTree T) {
if (T) {
Inorder_traverse(T->Lnode);
T->Data.printf();
Inorder_traverse(T->Rnode);
}
}
//中序遍历的非递归实现
void Inorder_traverse1(const BTree T) {
Lkstack S;
Lkstackinit(S);
BTree p = T;
BTnode* q = new BTnode;
while (p || S) {
if (p) {
Item e;
e.n = *p;
Push(S,e);
p = p->Lnode;
}
else {
Item e;
Pop(S, e);
*q = e.n;
q->Data.printf();
p = q->Rnode;
}
}
Lkstackfree(S);
}
//后序遍历的递归实现
void Rorder_traverse(const BTree T) {
if (T) {
Rorder_traverse(T->Lnode);
Rorder_traverse(T->Rnode);
T->Data.printf();
}
}
//层次遍历
void level_traverse(const BTree T) {
Queue q; // 队列初始化
QueueInit(q);
if (T != NULL) { //根结点入队列
Item e1;
e1.n = *T;
QueueEn(q, e1);
Item e;
while (QueueOut(q, e)) { //结点出队列，并将左右孩子加入队列
BTree p = new BTnode;
*p = e.n;
p->Data.printf();
if (p->Lnode != NULL) {
Item e;
e.n = *(p->Lnode);
QueueEn(q, e);
}
if (p->Rnode != NULL) {
Item e;
e.n = *(p->Rnode);
QueueEn(q, e);
}
free(p);
}
}
Sqqueuefree(q);
}
///--------------------------------------------
/// 线索二叉树
/// -------------------------------------------
//线索化
BTree pre=NULL;
void Inorder_threading(BTree T) {
if (T) {
Inorder_threading(T->Lnode); //左子树
if (!T->Lnode) {
T->Ltag = 1;
T->Lnode = pre;
}
else
T->Ltag = 0; //根
if (pre) {
if (!pre->Rnode) {
pre->Rtag = 1;
pre->Rnode = T;
}
else
pre->Rtag = 0;
}
pre = T;
Inorder_threading(T->Rnode); //右子树
}
}
//遍历线索化二叉树
void Inorder_threadBTree(const BTree T) {
BTree p = T;
while(p) {
while (p->Ltag == 0)
p = p->Lnode;
p->Data.printf();
while (p->Rtag == 1&& p->Rnode) {
p = p->Rnode; p->Data.printf();
}
p = p->Rnode;
}
}
int main(int argc, char argv[]) {
BTree T;
printf("请输入前序遍历的二叉树序列：（‘#’为空）\n");
Creat_BTree(T);
printf("\n前序遍历的二叉树序列为：\n");
Forder_traverse(T);
printf("\n\n中序遍历的二叉树序列为：\n");
Inorder_traverse(T);
printf("\n非递归中序遍历的二叉树序列为：\n");
Inorder_traverse1(T);
printf("\n\n后序遍历的二叉树序列为：\n");
Rorder_traverse(T);
printf("\n\n层次遍历的二叉树序列为：\n");
level_traverse(T);
printf("\n\n对二叉树中序线索化");
Inorder_threading(T);
printf("\n中序线索化遍历二叉树序列为：\n");
Inorder_threadBTree(T);
return 0;
}
运行截图