定义
特点
- 每个节点最多有两棵子树,所以二叉树中不存在度大于2的节点。
- 左子树和右子树是有区别的,次序不能颠倒。
- 即使某个节点只有1个子节点,也是有左右之分的。
![](https://pic1.imgdb.cn/item/634aa34316f2c2beb18f3be4.jpg)
特殊的二叉树:
- 斜树:正如上图的树1和树2,向一边斜的二叉树。
- 满二叉树:叶子节点都在最后一层,也就是说,非叶子节点都有左右子树
-
完全二叉树:
对一棵具有n个节点的二叉树按层序编号,如果编号为 i(1<=i<=n)的节点与同样深度的满二叉树中编号为 i的节点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树,如下图所示
就是说,这样 1开始,从左向右,从上至下的编号,如果所有有子节点的节点 i满足:
左儿子 j:$ j = 2 * i$ ,右儿子 k: $ k = 2 * i + 1$,那么它就是一棵完全二叉树
- 完全二叉树不一定是满二叉树
- 满二叉树一定是完全二叉树
- 手写的堆就是一棵完全二叉树
性质
- 二叉树第 i层最多有\(2^{i-1}\)个节点。
- 深度为 k的二叉树最多有\(2^k-1\)个节点。(1 + 2 + 4 + 8 + ··· + \(2^{k - 1}\))
- 有 n个节点的完全二叉树的深度为 \(|log_2n| + 1\) ,\(|x|\)代表对x向下取整。证明略。
- 从1开始,将完全二叉树从左到右,从上至下,依次标号(如上图),那么对于节点 i,左儿子 j:$ j = 2 * i$ ,右儿子 k: $ k = 2 * i + 1$。
存储结构
顺序存储结构
就是刚刚的性质4,存储的是完全二叉树。(也可以不是)
用数组模拟,下标代表树的标号。
主要的应用:线段树,堆
链式存储结构
又名二叉链表,即在结构体中定义两个指针,分别指向它的左儿子和右儿子。
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
遍历二叉树
前序遍历
若二叉树为空则返回,否则先访问根节点,再前序遍历左子树,再前序遍历右子树
总结起来:根左右
中序遍历
若二叉树为空则返回,否则先中序遍历左子树,再访问根节点,再中序遍历右子树
总结起来: 左根右
后序遍历
若二叉树为空则返回,否则先后序遍历左子树,再后序遍历右子树,最后访问根节点
总结起来:左右根
层序遍历
顾名思义,一层一层的遍历二叉树。
前三种是递归的遍历,要用到栈,层序遍历则是循环的遍历,要用到队列!
具体实现方法见代码。
作业
作业题目: 二叉树存储结构的建立、遍历和应用树和二叉树遍历是树形结构的最基础、最重要的核心算法。本作业要求掌
握和巩固二叉树的存储结构的建立方法、二叉树的遍历方法、过程及应用。
作业要求:
- 编写建立二叉树的动态(或者静态) 二叉链表存储结构(左右链表示) 的程序,并以适当的形式显示和保存二叉树;
- 采用二叉树的上述二叉链表存储结构,编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法, 并以适当的形式显示和保存二叉树及其相应的遍历序列;
- 设计并实现判断任意一棵二叉树是否为完全二叉树的算法。
- 设计并实现计算任意一棵二叉树的宽度的(递归或非递归)算法。 二叉树的宽度是指其各层结点数的最大值。
思路:
- 非递归算法则是手写一个栈用于存储节点信息。
- 判断是否为完全二叉树,可采用层序遍历的方式,无论子节点是否为空,都加入到队列中。当遍历到空节点时,退出,判断队列剩余元素是否全为空。如果是则为完全二叉树。
- 计算宽度也是用的层序遍历的方法,每一层计算下队头到队尾的元素数,更新最大值即可。
代码
点击查看代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数返回的类型*/
/* 用于构造二叉树 */
int treeIndex = 1;
typedef char String[MAXSIZE]; /* 0号单元存放串的长度 */
String str; // str为初始化的字符串
FILE *fp; // 保存用的文件指针
typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
/* 非递归使用的栈 */
typedef struct Stack
{
BiTree s[MAXSIZE];
int top;
}Stack;
/* 层序遍历使用的队列 */
typedef struct Queue
{
BiTree q[MAXSIZE];
int head;
int tail;
}Queue;
Status StrAssign(String T,char *chars); // 前序遍历初始化
Status visit(TElemType e); // 访问树的节点元素
Status InitBiTree(BiTree *T); // 初始化
void DestroyBiTree(BiTree *T); // 释放二叉树
void CreateBiTree(BiTree *T); // 建立二叉树
Status BiTreeEmpty(BiTree T); // 判空
int BiTreeDepth(BiTree T); // 求二叉树的深度
TElemType Root(BiTree T); // 求二叉树的根节点
TElemType Value(BiTree p); // 返回该节点的值
void Assign(BiTree p,TElemType value); // 给二叉树的节点赋值
void PreOrderTraverseRec(BiTree T); // 前序遍历递归版
void PreOrderTraverse(BiTree T); // 前序遍历非递归版
void InOrderTraverseRec(BiTree T); // 中序遍历递归版
void InOrderTraverse(BiTree T); // 中序遍历非递归版
void PostOrderTraverseRec(BiTree T); // 后序遍历递归版
void PostOrderTraverse(BiTree T); // 后序遍历非递归版
void SeqTraverse(BiTree T); // 层序遍历
int CalcuWidth(BiTree T); // 返回二叉树的最大宽度
Status JudgeCBT(BiTree T); // 判断是否为完全二叉树
int main(int args, char * argv[])
{
BiTree T;
InitBiTree(&T);
FILE *infile = fopen("in.txt","r");
fp = fopen("out.txt","w");
if(fp == NULL || infile == NULL)
{
(void) fprintf (stderr, "File open error!\n");//错误输出流
exit(EXIT_FAILURE);
}
String input;
fprintf(stdout,"please input BinaryTree with Preorder:(Empty Node with #)\n");
fscanf(infile,"%s", input);
StrAssign(str,input);
fprintf(stdout,"%s\n",input);
fprintf(fp,"%s\n",input);
CreateBiTree(&T);
fprintf(stdout,"\nPreOrderTraverseRec:");
fprintf(fp,"\nPreOrderTraverseRec:");
PreOrderTraverseRec(T);
fprintf(stdout,"\nPreOrderTraverse:");
fprintf(fp,"\nPreOrderTraverse:");
PreOrderTraverse(T);
fprintf(stdout,"\nInOrderTraverseRec:");
fprintf(fp,"\nInOrderTraverseRec:");
InOrderTraverseRec(T);
fprintf(stdout,"\nInOrderTraverse:");
fprintf(fp,"\nInOrderTraverse:");
InOrderTraverse(T);
fprintf(stdout,"\nPostOrderTraverseRec:");
fprintf(fp,"\nPostOrderTraverseRec:");
PostOrderTraverseRec(T);
fprintf(stdout,"\nPostOrderTraverse:");
fprintf(fp,"\nPostOrderTraverse:");
PostOrderTraverse(T);
fprintf(stdout,"\nSeqTraverse:");
fprintf(fp,"\nSeqTraverse:");
SeqTraverse(T);
fprintf(stdout,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T));
fprintf(fp,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T));
fprintf(stdout,"BiTree`s width:%d\n",CalcuWidth(T));
fprintf(fp,"BiTree`s width:%d\n",CalcuWidth(T));
DestroyBiTree(&T);
fclose(fp);
fclose(infile);
return 0;
}
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars) > MAXSIZE)
return ERROR;
else
{
T[0] = strlen(chars);
for(i = 1;i <= T[0]; i ++ )
T[i] = *(chars + i - 1);
return OK;
}
}
Status visit(TElemType e)
{
printf("%c ",e);
return OK;
}
/* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T)
{
if(*T) /* 递归的销毁,类似于后序遍历 */
{
if((*T)->lchild) /* 有左孩子 */
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
if((*T)->rchild) /* 有右孩子 */
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T = NULL; /* 空指针赋NULL */
}
}
/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树,构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
/* scanf("%c",&ch); */
ch=str[treeIndex ++];
if(ch == '#')
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!*T)
{
(void) fprintf (stderr, "Cannot allocate memory!\n");//错误输出流
exit(OVERFLOW);
}
(*T)->data=ch; /* 生成根结点 */
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树 */
}
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i, j;
if(!T)
return 0;
if(T->lchild)
i = BiTreeDepth(T->lchild);
else
i = 0;
if(T->rchild)
j = BiTreeDepth(T->rchild);
else
j = 0;
return i > j ? i+1 : j+1;
}
/* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
TElemType Root(BiTree T)
{
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}
/* 初始条件: 二叉树T存在,p指向T中某个结点 */
/* 操作结果: 返回p所指结点的值 */
TElemType Value(BiTree p)
{
return p->data;
}
/* 给p所指结点赋值为value */
void Assign(BiTree p,TElemType value)
{
p->data=value;
}
/* 前序递归遍历 */
void PreOrderTraverseRec(BiTree T)
{
if(T == NULL)
return;
fprintf(stdout,"%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
fprintf(fp,"%c",T->data);
PreOrderTraverseRec(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverseRec(T->rchild); /* 最后先序遍历右子树 */
}
/* 前序非递归遍历 */
void PreOrderTraverse(BiTree T)
{
Stack stk;
stk.top = 0;
while(T || stk.top)
{
if(T)
{
fprintf(stdout,"%c",T->data);// 先打印根节点
fprintf(fp,"%c",T->data);
stk.s[++ stk.top] = T;// 入栈
T = T->lchild;// 递归左节点
}else
{
T = stk.s[stk.top --]; // 回溯
T = T->rchild; // 递归右节点
}
}
}
/* 中序递归遍历 */
void InOrderTraverseRec(BiTree T)
{
if(T == NULL)
return;
InOrderTraverseRec(T->lchild); /* 中序遍历左子树 */
fprintf(stdout,"%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
fprintf(fp,"%c",T->data);
InOrderTraverseRec(T->rchild); /* 最后中序遍历右子树 */
}
/* 中序非递归遍历 */
void InOrderTraverse(BiTree T)
{
Stack stk;
stk.top = 0;
while(T || stk.top)
{
if(T)
{
stk.s[++ stk.top] = T; /* 入栈,递归左节点 */
T = T->lchild;
}else
{
T = stk.s[stk.top --]; /* 出栈,回溯,打印根节点 */
fprintf(stdout,"%c",T->data);
fprintf(fp,"%c",T->data);
T = T->rchild; /* 递归右节点 */
}
}
}
/* 后序递归遍历 */
void PostOrderTraverseRec(BiTree T)
{
if(T == NULL)
return;
PostOrderTraverseRec(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverseRec(T->rchild); /* 再后序遍历右子树 */
fprintf(stdout,"%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
fprintf(fp,"%c",T->data);
}
/* 后序非递归遍历 */
void PostOrderTraverse(BiTree T)
{
Stack stk;
stk.top = 0;
BiTree right = NULL; /*上一次遍历到的右节点 */
while(T || stk.top)
{
if(T)
{
stk.s[++ stk.top] = T; /* 不断向左递归 */
T = T->lchild;
}else
{
T = stk.s[stk.top];
if(T->rchild && T->rchild != right) /* 向右 */
{
T = T->rchild;
}else /* 左右都不行的话,回溯,打印当前结点 */
{
stk.top --;
fprintf(stdout,"%c",T->data);
fprintf(fp,"%c",T->data);
right = T;
T = NULL;/* 防止死循环 */
}
}
}
}
/* 层序遍历 */
void SeqTraverse(BiTree T)
{
Queue qu;
qu.head = 1;
qu.tail = 0;
qu.q[++ qu.tail] = T;
while(qu.head <= qu.tail) /* 打印队头的元素,再将队头的元素的左右儿子入队 */
{
int lenth = qu.tail - qu.head + 1;
while(lenth --)
{
BiTree root = qu.q[qu.head ++];
fprintf(stdout,"%c",root->data);
fprintf(fp,"%c",root->data);
if (root->lchild)
qu.q[++ qu.tail] = root->lchild;
if(root->rchild)
qu.q[++ qu.tail] = root->rchild;
}
}
}
/* 宽度计算 */
int CalcuWidth(BiTree T)
{
if(T == NULL) return 0;
Queue qu;
qu.head = 1;
qu.tail = 0;
qu.q[++ qu.tail] = T;
int res = 0;
while(qu.head <= qu.tail)
{
int lenth = qu.tail - qu.head + 1;//一行一行的取宽度最大值
if(res < lenth) res = lenth;
while(lenth --)
{
BiTree root = qu.q[qu.head ++];
if (root->lchild)
qu.q[++ qu.tail] = root->lchild;
if(root->rchild)
qu.q[++ qu.tail] = root->rchild;
}
}
return res;
}
/* 判断是否为完全二叉树 */
Status JudgeCBT(BiTree T)
{
if(T == NULL)
{
return TRUE;
}
Queue qu;
qu.head = 1;
qu.tail = 0;
qu.q[++ qu.tail] = T;
while(qu.head <= qu.tail) /* 打印队头的元素,再将队头的元素的左右儿子入队 */
{
BiTree root = qu.q[qu.head ++];
if(root == NULL)
{
break;
}
qu.q[++ qu.tail] = root->lchild;
qu.q[++ qu.tail] = root->rchild;
}
while(qu.head <= qu.tail)
{
if(qu.q[qu.head ++] != NULL)
{
return FALSE;
}
}
return TRUE;
}
参考文献
程杰. 大话数据结构:溢彩加强版[M]. 北京: 清华大学出版社, 2020.
标签:遍历,qu,BiTree,fprintf,二叉树,数据结构,节点 From: https://www.cnblogs.com/Az1r/p/16795060.html