树
树是一种数据结构它是由n（n>=0）个有限结点组成一个具有层次关系的集合，把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树
“树”这种数据结构真的很像我们现实生活中的“树”，这里面每个元素我们叫作“节点”；用来连线相邻节点之间的关系，我们叫作“父子关系”。
比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。
111.002.jpeg
关于“树”，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的
2222.001.jpeg
“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。
“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。
“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点的位于第 1 层。
二叉树（Binary Tree）
二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
二叉树的性质
- 性质1: 在二叉树的第i层上最多有2i-1个结点
2.性质2: 深度为K的二叉树最多有2k -1 个结点(K>=1)
3.性质3: 对于任何一颗二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1; - 性质4: 具有n个结点的完全二叉树深度为(log2(n))+1
5.性质5:对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号，则对于任意的序号为i的结点有:
A.如果i>1，那么序号为i的结点的双亲结点序号为i/2；
B.如果i=1，那么序号为i的结点为根节点，无双亲结点；
C.如果2i<=n，那么序号为i的结点的左孩子结点序号为2i；
D.如果2i>n，那么序号为i的结点无左孩子；
E.如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1；
F.如果2i+1>n，那么序号为i的结点无右孩子。
满二叉树
2222.003.jpeg
叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。
完全二叉树
2222.004.jpeg
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。
存储一棵二叉树，我们有两种方法，一种是基于数组的顺序存储法，一种是基于指针或者引用的二叉链式存储法。
image.png
如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因
二叉树的遍历
如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
下载.jpeg
实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树
二叉树顺序存储
#include <stdio.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 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
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;
#pragma mark -- 二叉树的基本操作
//1visit
void visit(CElemType c) {
printf("%d ",c);
}
//2.构造空二叉树T,因为T是固定数组,不会改变.
Status InitBiTree(SqBiTree T) {
for (int i = 0; i<MAX_TREE_SIZE; i++) {
//将二叉树初始化值置空
T[i] = Nil;
}
return OK;
}
//3. 手动赋值，按层序次序输入二叉树中的结点值(字符型或整型),构造顺序存储的二叉树T
Status CreateBiTree(SqBiTree T){
/*
1
2 3
4 5 6 7
8 9 10 2^3 7
*/
for (int i = 0; i<10; i++) {
T[i] = i+1;
//如果节点不为空，且无双亲节点，不能插入
if (i != 0 && T[(i+1)/2 - 1] == Nil && T[i] != Nil) {
printf("出现无双亲的非根结点%d\n",T[i]);
exit(ERROR);
}
}
return OK;
}
//技巧:
//如果大家想要2个函数的结果一样,但是目的不同;
//在顺序存储结构中, 两个函数完全一样的结果
#define ClearBiTree InitBiTree
/*4 判断二叉树是否为空
初始条件: 二叉树已存在
操作结果: 若T为空二叉树,则返回TRUE,否则返回FALSE;
*/
Status BiTreeEmpty(SqBiTree T){
//根结点为空,则二叉树为空
if (T[0] == Nil) {
return TRUE;
} else {
return FALSE;
}
}
/*5 获取二叉树的深度
初始条件: 二叉树已存在
操作结果: 返回二叉树T深度;
*/
int BiTreeDepth(SqBiTree T){
//因为是完全二叉树首先找到最后一个
int j = -1;
int i;
for (i = MAX_TREE_SIZE-1; i>=0; i--) {
if (T[i] != Nil) {
break;
}
}
do {
j++;
} while (powl(2, j)<=i); //计算2的j次幂
return j;
}
/*6 返回处于位置e(层,本层序号)的结点值
初始条件: 二叉树T存在,e是T中某个结点(的位置)
操作结构: 返回处于位置e(层,本层序号)的结点值
*/
CElemType Value(SqBiTree T,Position e){
//找到对应的index;
int i = powl(2, e.level-1);//对应层的第一个index
printf("%d\n",i);
return T[i+e.order-2];//本层的位置
}
/*7 获取二叉树跟结点的值
初始条件: 二叉树T存在
操作结果: 当T不空,用e返回T的根, 返回OK; 否则返回ERROR
*/
Status Root(SqBiTree T,CElemType *e){
if (BiTreeEmpty(T)) {
return ERROR;
}
*e = T[0];
return OK;
}
/*
8 给处于位置e的结点赋值
初始条件: 二叉树存在,e是T中某个结点的位置
操作结果: 给处于位置e的结点赋值Value;
*/
Status Assign(SqBiTree T,Position e,CElemType value){
//找到当前e在数组中的具体位置索引
int i = (int)powl(2, e.level-1)+e.order -2;
//叶子结点的双亲为空
if (value != Nil && T[(i+1)/2-1] == Nil) {
return ERROR;
}
//给双亲赋空值但是有叶子结点
if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) {
return ERROR;
}
T[i] = value;
return OK;
}
/*
9 获取e的双亲;
初始条件: 二叉树存在,e是T中的某一个结点
操作结果: 若e是T的非根结点, 则返回它的双亲,否则返回"空"
*/
CElemType Parent(SqBiTree T, CElemType e){
if (BiTreeEmpty(T)) {
return Nil;
}
for (int i = 0; i<MAX_TREE_SIZE; i++) {
if (T[i] == e) {
return T[(i+1)/2 - 1];
}
}
return Nil;
}
/*
10 获取某个结点的左孩子;
初始条件:二叉树T存在,e是某个结点
操作结果:返回e的左孩子,若e无左孩子,则返回"空"
*/
CElemType LeftChild(SqBiTree T,CElemType e){
//空树
if (T[0] == Nil) {
return Nil;
}
for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
//找到e
if (T[i] == e) {
return T[i*2+1];
}
}
//没有找到
return Nil;
}
/*
6.11 获取某个结点的右孩子;
初始条件:二叉树T存在,e是某个结点
操作结果:返回e的左孩子,若e无左孩子,则返回"空"
*/
CElemType RightChild(SqBiTree T,CElemType e){
//空树
if (T[0] == Nil) {
return Nil;
}
for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
//找到e
if (T[i] == e) {
return T[i*2+2];
}
}
//没有找到
return Nil;
}
/*
6.12 获取结点的左兄弟
初始条件: 二叉树T存在,e是T中某个结点
操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂
*/
CElemType LeftSibling(SqBiTree T,CElemType e)
{
/* 空树 */
if(T[0]==Nil)
return Nil;
for(int i=1;i<=MAX_TREE_SIZE-1;i++)
/* 找到e且其序号为偶数(是右孩子) */
if(T[i]==e&&i%2==0)
return T[i-1];
return Nil; /* 没找到e */
}
/* 6.13 获取结点的右兄弟
初始条件: 二叉树T存在,e是T中某个结点
操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂
*/
CElemType RightSibling(SqBiTree T,CElemType e)
{
/* 空树 */
if(T[0]==Nil)
return Nil;
for(int i=1;i<=MAX_TREE_SIZE-1;i++)
/* 找到e且其序号为奇数(是左孩子) */
if(T[i]==e&&i%2==1)
return T[i+1];
return Nil; /* 没找到e */
}
/*
14 层序遍历二叉树
*/
void LevelOrderTraverse(SqBiTree T){
int i = MAX_TREE_SIZE-1;
//找到最后一个非空结点的序号
while (T[i] == Nil) i--;
//从根结点起,按层序遍历二叉树
for (int j = 0; j <= i; j++)
//只遍历非空结点
if (T[j] != Nil)
visit(T[j]);
printf("\n");
}
/*
15 前序遍历二叉树
*/
void PreTraverse(SqBiTree T, int e) {
//先打印自己
visit(T[e]);
//遍历左子树
if (T[(e*2+1)] != Nil) {
PreTraverse(T, e*2+1);
}
//遍历右子树
if (T[(e*2+2)] != Nil) {
PreTraverse(T, e*2+2);
}
}
Status PreOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
PreTraverse(T, 0);
}
printf("\n");
return OK;
}
/*
16 中序遍历二叉树
*/
void InTraverse(SqBiTree T, int e) {
//遍历左子树，左子树不空
if (T[(e*2+1)] != Nil) {
InTraverse(T, e*2+1);
}
//打印节点
visit(T[e]);
//遍历右子树
if (T[(e*2+2)] != Nil) {
InTraverse(T, e*2+2);
}
}
Status InOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
InTraverse(T, 0);
}
printf("\n");
return OK;
}
/*
17 后序遍历二叉树
*/
void PostTraverse(SqBiTree T, int e) {
//遍历左子树
if (T[(e*2+1)] != Nil) {
PostTraverse(T, e*2+1);
}
//遍历右子树
if (T[(e*2+2)] != Nil) {
PostTraverse(T, e*2+2);
}
//打印节点
visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
PostTraverse(T, 0);
}
printf("\n");
return OK;
}
二叉树的链式存储
#include <stdio.h>
#include "string.h"
#include "stdio.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
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/*二叉树构造*/
int indexs = 1;
typedef int Status;
typedef char String[24]; /* 0号单元存放串的长度 */
String str;
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;
}
}
typedef char CElemType;
CElemType Nil = ' '; /* 字符型以空格为空 */
typedef struct BiTNode /*节点*/
{
CElemType data; /*节点数据*/
struct BiTNode *lchild,*rchild;/* 左右子树指针 */
}BiTNode,*BiTree;
//1 打印数据
void visit(CElemType e)
{
printf("%c ",e);
}
//2 构造空二叉树T
Status InitBiTree(BiTree *T)
{
*T = NULL;
return OK;
}
/* 3 销毁二叉树
初始条件: 二叉树T存在。
操作结果: 销毁二叉树T
*/
void DestroyBiTree(BiTree *T)
{
if (*T) {
//这里我们回忆一下递归,递归的关键是要找到终止条件,终止条件： 左子树或右子树为空，递归终止
//有左子树，递归
if((*T)->lchild)
DestroyBiTree(T);
//有右子树，递归
if((*T)->rchild)
DestroyBiTree(T);
free(*T);//释放根节点
*T = NULL;
}
}
#define ClearBiTree DestroyBiTree
/*4 创建二叉树
按前序输入二叉树中的结点值(字符),#表示空树;
*/
void CreateBiTree(BiTree *T){
CElemType ch;
//取字符
ch = str[indexs++];
if (ch == '#') {
*T = NULL;
} else {
//创建新的节点
*T = (BiTree)malloc(sizeof(BiTNode));
//是否创建成功
if (!*T) {
exit(OVERFLOW);
}
(*T)->data = ch;
/* 构造左子树 */
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
/*
5 二叉树T是否为空;
初始条件: 二叉树T存在
操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
*/
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
/*
6 二叉树T的深度（递归实现）
初始条件: 二叉树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;
}
/*
7 二叉树T的根
初始条件: 二叉树T存在
操作结果: 返回T的根
*/
CElemType Root(BiTree T){
if (BiTreeEmpty(T))
return Nil;
return T->data;
}
/*
8 返回p所指向的结点值;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 返回p所指结点的值
*/
CElemType Value(BiTree p){
return p->data;
}
/*
8 给p所指结点赋值为value;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 给p所指结点赋值为value
*/
void Assign(BiTree p,CElemType value)
{
p->data=value;
}
#pragma mark: 遍历
/*
7.8 前序递归遍历T
初始条件:二叉树T存在;
操作结果: 前序递归遍历T
*/
void PreOrderTraverse(BiTree T) {
//递归终止条件
if (T==NULL) {
return;
}
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
/*
7.9 中序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
/*
7.10 后序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
网友评论