树
数据结构的树存储结构，常用于存储逻辑关系为 "一对多" 的数据。
度：对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）
层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。
深度：一棵树的深度（高度）是树中结点所在的最大的层次
二叉树
二叉树是一种特定的树结构，是n(n>=0)个结点的有限集合，该集合为空集(空二叉树)或者由一个根结点和两个互不相交的、分别称为根结点左子树和右子树构成。
image.png
二叉树的特点
1.每个结点最多有两棵子树，即二叉树中不存在度大于2的结点
2.左子树和右子树有有序的，不能互相颠倒
3.即使树中某结点只有一棵子树，也要区分是左子树还是右子树
二叉树的性质
1.在二叉树的第i层上最多有i^2 个结点
2.深度为k的二叉树最多有2^k-1个结点
3.对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则存在n0=n2+1
4.具有n个结点的完全二叉树深度为[log2(n)]+1
5.对含有n个结点的完全二叉树，如果按照从上到下且从左到右进行1至n的编号，则对完全二叉树任意一个编号为i的结点有如下特性：
若i=1，则该结点是二叉树的根，没有双亲，否则编号为[i/2]的结点为双亲结点
若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子
若2i+1>n，则该结点没有右孩子，否则，编号为2i+1的结点为其右孩子
二叉树的存储
1.顺序存储
二叉树的顺序存储指的是使用顺序表来存储二叉树。
image.png
按照层序的顺序把二叉树的各个结点依次存入顺序表中，可以发现，在完全二叉树的情况下，顺序表的存储空间得到最大程度的使用。
但不是完全二叉树
image.png
代码：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 15 // 存储空间初始分配量
#define MAX_TREE_SIZE 15 // 二叉树的最大结点数
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int CElemType; // 树结点的数据类型，目前暂定为整型
typedef CElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点
CElemType Nil = 0; //设整型以0为空 或者以 INT_MAX(65535)
typedef struct {
//结点层
int level;
//本层的序号(按照满二叉树给定序号规则)
int order;
}Position;
// visit
Status visit(CElemType c){
printf("%d ",c);
return OK;
}
// 构造空二叉树T,因为T是固定数组,不会改变.
Status InitBiTree(SqBiTree T){
for(int i = 0; i < MAXSIZE; i++) {
T[i] = Nil;
}
return OK;
}
// 按层序次序输入二叉树中的结点值(字符型或整型),构造顺序存储的二叉树T
Status CreateBiTree(SqBiTree T){
int i = 0;
//printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE);
while(i < 10) {
T[i] = i+1;
//结点不为空并且没有双亲结点
if(i!=0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
return printError("出现无双亲的非根结点\n", ERROR);
}
i++;
}
return OK;
}
//清空二叉树
//在顺序存储结构中, 两个函数完全一样的结果
#define ClearBiTree InitBiTree
//判断二叉树是否为空
Status BiTreeEmpty(SqBiTree T){
//根结点为空,则二叉树为空
if (T[0] == Nil)
return TRUE;
return FALSE;
}
//获取二叉树的深度
int BiTreeDepth(SqBiTree T){
int i;
for(i = MAXSIZE-1; i >= 0; i--) {
if(T[i] != Nil) {
break;
}
}
//左斜树序号为 1-2-4-8
//左斜树索引为 0-1-3-7
int j = 0;
while(powl(2, j)-1 < i) {
j++;
}
return j;
}
//返回处于位置e(层,本层序号)的结点值
CElemType Value(SqBiTree T,Position e){
/*
Position.level -> 结点层.表示第几层;
Position.order -> 本层的序号(按照满二叉树给定序号规则)
*/
//层数从1开始
int depth = e.level-1;
//某一层开端的索引
int levelStart = powl(2, depth)-1;
//序号从1开始
int order = e.order-1;
return T[levelStart+order];
}
/*
获取二叉树跟结点的值
初始条件: 二叉树T存在
操作结果: 当T不空,用e返回T的根, 返回OK; 否则返回ERROR
*/
Status Root(SqBiTree T,CElemType *e){
if(BiTreeEmpty(T)) {
return printError("二叉树为空", ERROR);
}
*e = T[0];
return OK;
}
/*
给处于位置e的结点赋值
初始条件: 二叉树存在,e是T中某个结点的位置
操作结果: 给处于位置e的结点赋值Value;
*/
Status Assign(SqBiTree T,Position e,CElemType value){
//找到位置e的具体索引
int index = powl(2, e.level-1)+(e.order-2);
//如果结点双亲为空
if(value!=Nil && T[(index+1)/2]==Nil) {
return printError("结点双亲为空", ERROR);
}
//双亲赋空值，但是有叶子结点
if(value==Nil && (T[index*2+1]!=Nil || T[index*2+2]!= Nil)) {
return printError("双亲赋空但是孩子有值", ERROR);
}
T[index] = value;
return OK;
}
/*
获取e的双亲;
初始条件: 二叉树存在,e是T中的某一个结点
操作结果: 若e是T的非根结点, 则返回它的双亲,否则返回"空"
*/
CElemType Parent(SqBiTree T, CElemType e){
for(int i = 1; i < MAXSIZE; i++) {
if(T[i] == e) {
return T[(i+1)/2-1];
}
}
//没有找到
return Nil;
}
//获取某个结点的左孩子
CElemType LeftChild(SqBiTree T,CElemType e){
for (int i = 0; i < MAXSIZE; i++) {
if(T[i] == e) {
if(i*2+1 >= MAXSIZE) {
return Nil;
}
return T[i*2+1];
}
}
return Nil;
}
//获取某个结点的右孩子
CElemType RightChild(SqBiTree T,CElemType e){
for (int i = 0; i < MAXSIZE; i++) {
if(T[i] == e) {
if(i*2+2 >= MAXSIZE) {
return Nil;
}
return T[i*2+2];
}
}
return Nil;
}
//获取结点的左兄弟
CElemType LeftSibling(SqBiTree T,CElemType e) {
//从1开始，0为根结点，没有左兄弟
for(int i = 1; i < MAXSIZE; i++) {
//右结点的索引为偶数
if(T[i] == e && i%2==0) {
return T[i-1];
}
}
return Nil;
}
//获取结点的右兄弟
CElemType RightSibling(SqBiTree T,CElemType e)
{
for(int i=1;i<MAX_TREE_SIZE;i++)
//左结点的索引为奇数
if(T[i]==e&&i%2==1)
return T[i+1];
return Nil;
}
#pragma mark -- 二叉树的遍历
//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T){
//找到二叉树的最后一个非空结点
int i = MAXSIZE-1;
while(i >= 0 && T[i] != Nil) {
i--;
}
for(int j = 0; j <= i; j++) {
if(T[j] != Nil) {
visit(T[j]);
}
}
printf("\n");
}
//前序遍历二叉树
void PreTraverse(SqBiTree T,int e){
visit(T[e]);
if((e*2+1)<MAXSIZE && T[e*2+1] != Nil) {
PreTraverse(T, e*2+1);
}
if((e*2+2)<MAXSIZE && T[e*2+2] != Nil) {
PreTraverse(T, e*2+2);
}
}
Status PreOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
PreTraverse(T, 0);
}
printf("\n");
return OK;
}
//中序遍历
void InTraverse(SqBiTree T, int e){
// 左子树不空
if ((e*2+1)<MAXSIZE && T[2*e+1] != Nil)
InTraverse(T, 2*e+1);
visit(T[e]);
// 右子树不空
if ((e*2+2)<MAXSIZE && T[2*e+2] != Nil)
InTraverse(T, 2*e+2);
}
Status InOrderTraverse(SqBiTree T){
// 树不空
if (!BiTreeEmpty(T)) {
InTraverse(T, 0);
}
printf("\n");
return OK;
}
//后序遍历
void PostTraverse(SqBiTree T,int e)
{ // 左子树不空
if((e*2+1)<MAXSIZE && T[2*e+1]!=Nil)
PostTraverse(T,2*e+1);
// 右子树不空
if((e*2+2)<MAXSIZE && T[2*e+2]!=Nil)
PostTraverse(T,2*e+2);
visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) //树不空
PostTraverse(T,0);
printf("\n");
return OK;
}
链式存储
image.png
//'#'为结束符表示当前结点的双亲结点没有左孩子或者右孩子，如上图所示二叉树转换为字符串为"ABDH#K###E##CFI###G#J##"
CElemType Nil = '#';
typedef struct BiTNode {
CElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 构造空二叉树T
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
// 销毁二叉树
void DestroyBiTree(BiTree *T){
if(*T) {
DestroyBiTree(&(*T)->lchild);
DestroyBiTree(&(*T)->rchild);
free(*T);
*T = NULL;
}
}
#define ClearBiTree DestroyBiTree
// 创建二叉树
void CreateBiTree(BiTree *T, char* str, int* index){
CElemType ch = str[(*index)++];
if(ch == Nil) {
*T = NULL;
}else {
//创建新的结点
*T = (BiTree)malloc(sizeof(struct BiTNode));
//是否创建成功
if(!*T) {
exit(0);
}
//结点赋值
(*T)->data = ch;
//创建当前结点的左子树
CreateBiTree(&(*T)->lchild, str, index);
//创建当前结点的右子树
CreateBiTree(&(*T)->rchild, str, index);
}
}
// 二叉树T是否为空;
Status BiTreeEmpty(BiTree T){
if(T) {
return FALSE;
}else {
return TRUE;
}
}
// 二叉树T的深度
int BiTreeDepth(BiTree T){
if(!T) {
return 0;
}
int i = 0;
int j = 0;
//分别计算出左子树的深度和右子树的深度，取较深的一边+1
i = BiTreeDepth(T->lchild);
j = BiTreeDepth(T->rchild);
return i>j?i+1:j+1;
}
// 二叉树T的根
CElemType Root(BiTree T){
if (BiTreeEmpty(T))
return Nil;
return T->data;
}
// 返回p所指向的结点值;
CElemType Value(BiTree p){
return p->data;
}
// 给p所指结点赋值为value;
void Assign(BiTree p,CElemType value)
{
p->data=value;
}
二叉树的遍历
前序遍历
//前序递归遍历T
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
// 显示结点数据，可以更改为其它对结点操作
printf("%c",T->data);
//再先序遍历左子树
PreOrderTraverse(T->lchild);
//最后先序遍历右子树
PreOrderTraverse(T->rchild);
}
非递归-1
image.png
树是一种重复的结构，在遍历的过程中，我们需要不停地回溯，因此选择采用栈思想。
前序遍历的顺序为中-左-右。
image.png
void PreOrderTraverse_1(BiTree T) {
if(!T) return;
int depth = BiTreeDepth(T);
BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
int top = -1;
//根入栈
stack[++top] = T;
while(top>-1) {
//根出栈，打印根结点的值
BiTree cur = stack[top];
top--;
printf("%c",cur->data);
//右孩子入栈
if(cur->rchild) {
stack[++top] = cur->rchild;
}
//左孩子入栈
if(cur->lchild) {
stack[++top] = cur->lchild;
}
}
free(stack);
}
非递归-2
1.找到当前二叉树的最左结点，在此过程中依次打印结点的值并入栈
2.栈顶结点出栈，栈顶结点有右孩子，则当前二叉树变为栈顶结点的右子树，重复步骤1，否则一直出栈直到栈为空
void PreOrderTraverse_2(BiTree T) {
if(!T) return;
int depth = BiTreeDepth(T);
BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
int top = -1;
BiTree cur = T;
while(cur || top>-1) {
if (cur) {
//找到最左结点
printf("%c",cur->data);
stack[++top] = cur;
cur = cur->lchild;
}else {
//指向右孩子，重复遍历
cur = stack[top];
top--;
cur = cur->rchild;
}
}
}
中序遍历
//递归
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
//中序遍历左子树
InOrderTraverse(T->lchild);
//显示结点数据，可以更改为其它对结点操作
printf("%c",T->data);
//最后中序遍历右子树
InOrderTraverse(T->rchild);
}
//非递归
//和前序类似，前序是中-左-右，在入栈的过程中进行打印，中序为左-中-右
void InOrderTraverse_1(BiTree T) {
if(!T) return;
int depth = BiTreeDepth(T);
BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
int top = -1;
BiTree cur = T;
while(cur || top>-1) {
if(cur) {
stack[++top] = cur;
cur = cur->lchild;
}else {
cur = stack[top];
top--;
printf("%c",cur->data);
cur = cur->rchild;
}
}
}
后序遍历
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
//先后序遍历左子树
PostOrderTraverse(T->lchild);
/再后序遍历右子树
PostOrderTraverse(T->rchild);
//显示结点数据，可以更改为其它对结点操作
printf("%c",T->data);
}
//非递归-1
//后序遍历的顺序为左-右-中 ，我们需要一个额外的lastVisit指针来记录最后一次访问的结点
//找到最左结点，并且入栈
//栈顶结点没有右孩子或者右孩子已经被访问过，才能将栈顶结点弹出并打印，否则，以栈顶结点的右子树开始重新遍历
void PostOrderTraverse_1(BiTree T) {
if(!T) return;
int depth = BiTreeDepth(T);
BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
int top = -1;
BiTree cur = T, lastVisit = NULL;
while(cur || top>-1) {
if(cur) {
//找到最左侧结点
stack[++top] = cur;
cur = cur->lchild;
}else {
cur = stack[top];
//如果没有右孩子或者右孩子已经被访问过，则需要出栈并打印
if(!cur->rchild || lastVisit == cur->rchild) {
printf("%c",cur->data);
top--;
lastVisit = cur;
cur = NULL;
}else {
//有右孩子并且没有被访问过，开始访问右子树
cur = cur->rchild;
}
}
}
}
//非递归-2
//在非递归解法1中，压栈顺序为右-左，因为后序遍历的顺序为左-右-中，
//因对前序遍历的非递归解法1加以改造，改变入栈的顺序为左-右，在出栈的时候不是打印而是用另外一个新栈来进行入栈操作
void PostOrderTraverse_2(BiTree T) {
if(!T) return;
int depth = BiTreeDepth(T);
BiTree* stack = (BiTree*)malloc(sizeof(BiTree)*depth);
BiTree* outStack = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
int top = -1;
int outTop = -1;
stack[++top] = T;
while(top>-1) {
BiTree topNode = stack[top];
top--;
outStack[++outTop] = topNode;
if(topNode->lchild) {
stack[++top] = topNode->lchild;
}
if(topNode->rchild) {
stack[++top] = topNode->rchild;
}
}
while(outTop>-1) {
BiTree topNode = outStack[outTop--];
printf("%c",topNode->data);
}
}
层序遍历
链式存储不是连续的内存空间，不能直接进行遍历。可以利用队列来进行遍历。
image.png
void LevelOrderTraverse(BiTree T) {
if(!T) return;
BiTree *queue = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
int prior = 0;
int rear = 0;
queue[rear++] = T;
while(prior != rear) {
BiTree head = queue[prior++];
printf("%c",head->data);
if(head->lchild) {
queue[rear++] = head->lchild;
}
if(head->rchild) {
queue[rear++] = head->rchild;
}
}
}
网友评论