树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合(n=0时,称为空树),把它叫做树是因为它看起来像一颗倒挂的树,也就是说根朝上,而叶朝下的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
一个根由n(n>=0)棵子树构成
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点 兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点 (亲兄弟) 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;(空树高度为 0) 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙 森林:由m(m>0)棵互不相交的树的集合称为森林;
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既要保存值域,也要保存结点和结点之间 的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。下面介绍几种常见的表示树的方法。
用指针数组存储孩子
//假设树的度为6
#define N 10
struct TreeNode
{
int val;
struct TreeNode*childArr[N];
//指针数组
};
使用这种数据结构去存储树事实上存在一点的问题,只有在知道树的度的情况下使用这种结构才比较合理,另外也不是每个节点的度都是一样的,容易造成空间的浪费。
用顺序表存储孩子
struct TreeNode
{
int val;
SeqList child;
//顺序表存储孩子
};
这种方法事实上就是使用数组存储每个节点的信息,当树为完全二叉树时,父节点和子节点之间存在一种关系,这个时候使用这种结构比较方便(下面讲到二叉树时会详细说明)。
孩子兄弟表示法
typedef int DataType;
struct Node
{
struct Node* leftChild1; // 左孩子结点(第一个孩子)
struct Node* rightBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
使用这种方法去存储树的节点时,每次只用存储左孩子结点和指向下一个兄弟(亲兄弟)的结点。
可以使用如下方式遍历
struct Node* child=A->leftChild;
while(child)
{
child=child->rightBrother;
}
一棵二叉树是结点的一个有限集合,该集合:
从上图可以看出:
注意:对于任意的二叉树都是由以下几种情况复合而成的:
下面有几个例题:
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
这种就是一层一层存到数组中。 我们可以发现父子结点的下标之间存在一个规律关系: leftchild=parent*2+1; 奇数 rightchild=parent*2+2; 偶数 parent=(child-1)/2;(不需要区分左右孩子)
非完全二叉树就不适合数组存储,只适合链式存储。
2.链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* LeftChild; // 指向当前节点左孩子
struct BinTreeNode* RightChild; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* Parent; // 指向当前节点的双亲
struct BinTreeNode* LeftChild; // 指向当前节点左孩子
struct BinTreeNode* RightChild; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
};
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。
小堆就是任意一个父节点都<=它的孩子节点 大堆就是任意一个父节点都>=它的孩子节点
下面有几个例题:
1.下列关键字序列为堆的是:()
A. 100,60,70,50,32,65
B. 60,70,65,50,32,100
C. 65,100,70,32,50,60
D. 70,65,100,32,50,60
E. 32,50,100,70,65,60
F. 50,100,70,65,60,32
2.已知小根堆为8,15,10,21,34,16,12,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是()。
A. 1
B. 2
C. 3
D. 4
答案:
1.A 2.C
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
int array[]={27,15,19,18,28,34,65,49,25,37};
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(int* a, int size, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < size)
{
if (child+1<size&&a[child + 1] < a[child])//找兄弟节点中较小的那一个,再交换 //小堆(大堆时是>)
{
child++;
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
//child = parent * 2 + 1;
}
else
{
break;
}
}
}
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
//数组中父节点的下标比子节点的下标小
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])//小堆(大堆时是>)
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
//parent=(parent-1)/2;
}
else
{
break;
}
}
}
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
int a[]={1,5,3,8,7,6};
堆的插入
先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcap = php->capacity == 0 ? 10 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcap);
if (tmp == NULL)
{
perror("realloc!");
exit(-1);
}
php->a = tmp;
php->capacity = newcap;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
删除堆是删除堆顶的数据,需要先将堆顶的数据和最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。
// 规定删除堆顶(根节点)
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
// 规定删除堆顶(根节点)
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->size = 0;
php->capacity = 0;
}
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
//数组中父节点的下标比子节点的下标小
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])//小堆(大堆时是>)
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
//parent=(parent-1)/2;
}
else
{
break;
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcap = php->capacity == 0 ? 10 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcap);
if (tmp == NULL)
{
perror("realloc!");
exit(-1);
}
php->a = tmp;
php->capacity = newcap;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(int* a, int size, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < size)
{
if (child+1<size&&a[child + 1] < a[child])//找兄弟节点中较小的那一个,再交换 //小堆(大堆时是>)
{
child++;
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
//child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 规定删除堆顶(根节点)
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
在讲解二叉树之前,我们需要创建一颗二叉树,这里先手动创建一颗二叉树,后面会详细说明如何创建二叉树。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}
注意:上述代码并不是创建二叉树的方式。
先回顾一下二叉树的概念,二叉树是:
从概念中可以看出,二叉树定义是递归式的,因此接下来的基本操作中基本都是按照该概念实现的。
按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);
前序遍历递归图解:
前序遍历结果:1 2 3 4 5 6(1 2 3 N N N 4 5 N N 6 N N) 中序遍历结果:3 2 1 5 4 6 后序遍历结果:3 2 5 6 4 1 注:N代表NULL
代码实现
// 二叉树前序遍历
//根 左 右
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%c ", root->val);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
//left root right
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->val);
BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
//左 右 根
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->val);
}
层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历的实现需要借助队列这个数据结构,它的核心就是一层一层地遍历,当前结点出队列时,将它的左右子树的非空根节点入队列,当一层遍历完时,下一层已经全部入队列了。
代码实现:
// 层序遍历
void BinaryTreeLeveorder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
int levelsize = 1;
while (!QueueEmpty(&q))
{
while (levelsize--)
{
BTNode* front = QueueFront(&q);
QueuePop(&q);//pop删除的是队列的结点,不会影响front,实际上这几个都是指向二叉树结点的指针
printf("%c ", front->val);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
levelsize = QueueSize(&q);
}
QueueDestroy(&q);
}
这个问题其实可以转化为根节点子树的高度+1,想到这里肯定就明白要用到递归的方法了。
int calculateDepth(struct TreeNode* root) {
if(root==NULL)
return 0;
int left =calculateDepth(root->left);
int right=calculateDepth(root->right);
return left>=right?left+1:right+1;
}
这个问题其实也可以转化为根节点左子树结点的个数+根节点右子树结点的个数+1
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
这个其实也同样可以转化为子树的第k-1层的结点个数
// 二叉树第k层节点个数==子树的第k-1层的结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
以前序遍历创建二叉树为例,假设’#‘代表NULL,方法和前序遍历类似。
BTNode* BinaryTreeCreate(char* a, int* pi)
{
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
root->val = a[(*pi)++];
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
这个需要注意的是,不能先销毁根节点,因为先销毁了根结点就无法找到左右子树的结点,所以先遍历到树的底部,在回归时再销毁。
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root)
{
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;//二级指针记得置空
}
}