一、树的概念及结构
1.树的概念
树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。除根节点外, 其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ,其中每一个集合 Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有 0 个或多个后继。因此, 树是递归定义 的。
2.相关概念
节点的度:一个节点含有的子树个数称为该节点的度。如上图:根节点A的度为5
叶节点/终端节点:度为0的节点称为叶节点。如上图:B、D、G、I、K、L、M、N、O均为叶节点
分支节点/非终端节点:度不为0的节点。如上图:C、E、F、H、J为分支节点
3.树的表示
实际中树的表示方法有很多种,最常用的是链式存储结构的孩子兄弟表示法:
typedef int DataType;
struct Node
{
struct Node* _firstChild; // 指向其第一个孩子结点
struct Node* _Brother; // 指向其兄弟结点
DataType _data; // 结点中的数据域
};
例如,上图的部分节点表示如下:
4.树的性质
①设度为i的节点个数为,则对于一颗度为m的树,其总节点个数N =
②所有节点的度之和
二、二叉树的概念
1.概念
一棵二叉树是结点的一个有限集合,该集合 :1. 或者为空2. 或者 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
2.特殊的二叉树
3.二叉树的性质
三、二叉树的存储结构
1.顺序存储
顺序存储就是使用一个数组来存储,顺序存储一般只适用于完全二叉树或近似于完全二叉树,否则会造成较大的空间浪费。现实使用中只有堆才会使用数组存储,关于堆的内容将在下篇博客【堆的实现及应用】讲解。
二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
2.链式存储
二叉树的链式存储结构是指,用链表来表示一颗二叉树,即用链来指示元素的逻辑关系。通常链表中的每个节点由三个域组成:数据域、左指针域、右指针域。其中左右指针域分别给出该节点左孩子和右孩子所在链节点的地址。这种链式结构又叫做二叉链。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
一颗二叉树可以分为三部分:根节点、左子树、右子树,而左右子树又都是一颗二叉树,可见二叉树的结构具有递归性,因此基于链式存储结构的二叉树算法多数也是递归的,这样代码的可读性更高、容易理解。
(1)二叉树的遍历
二叉树遍历是指按照某种特定规则依次访问二叉树的全部节点,每个节点只访问一次。
遍历是二叉树最重要的算法之一,也是其他算法的基础。
二叉树的遍历可分为四种:
①前序遍历:按照根节点、左子树、右子树的顺序遍历二叉树。如上图,遍历结果为1 2 4 6 5 3
②中序遍历:按照左子树、根节点、右子树的顺序遍历二叉树。如上图,遍历结果为4 6 2 5 1 3
③后序遍历:按照左子树、右子树、根节点的顺序遍历二叉树。如上图,遍历结果为6 4 5 2 3 1
④层序遍历:从根节点开始,自上而下、自左至右逐层访问二叉树的每个节点。如上图,遍历结果为1 2 3 4 5 6
其中,前三种遍历方式均属于递归遍历,第四种为非递归遍历。
下面以前序遍历为例演示递归遍历:
void PreOrder(BTNode* t)
{
if (t == NULL)
{
printf("NULL ");
return;
}
printf("%d ", t->val);
PreOrder(t->left);
PreOrder(t->right);
}
层序遍历需要借助队列来实现,使用队列保存每个节点的孩子节点,通过不断地入队和出队以此来实现所有节点的访问:(注:有关队列的接口函数均与上篇博客中保持一致)
void LevelOrder(BTNode* t)
{
Queue qu;
QueueInit(&qu);
QueuePush(&qu, t);
while (!QueueEmpty(&qu))
{
BTNode* tmp = QueueFront(&qu);
QueuePop(&qu);
printf("%d ", tmp->val);
if (tmp->left != NULL)
QueuePush(&qu, tmp->left);
if (tmp->right != NULL)
QueuePush(&qu, tmp->right);
}
}
(2)二叉树的创建和销毁
已知一颗二叉树的某种递归遍历序列,如何构建出对应的二叉树?下面以前序序列为例:(注:子树为空用‘#’表示)
//创建单个节点
BTNode* SingleNode(BTDataType x)
{
BTNode* _new = (BTNode*)malloc(sizeof(BTNode));
if (_new == NULL)
{
perror("malloc error");
exit(-1);
}
_new->val = x;
_new->left = NULL;
_new->right = NULL;
return _new;
}
//创建二叉树
BTNode* CreateBT(char* a, int* pi) //pi为遍历序列a的下标,开始为0
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc error");
exit(-1);
}
root->val = a[(*pi)++]-'0'; //注意数据类型
root->left = CreateBT(a, pi);
root->right = CreateBT(a, pi);
return root;
}
二叉树的销毁:
void BTDestroy(BTNode** pt)
{
BTNode* t = *pt;
if (t == NULL)
return;
BTDestroy(&(t->left));
BTDestroy(&(t->right));
free(t);
*pt = NULL;
}
(3)其他算法
下面列举了一些有关二叉树遍历的其他算法,可以加深对递归遍历和链式结构的理解。当然,这些算法题在各大OJ平台都可以搜到。
①计算二叉树的节点个数:
int TreeNodeSize(BTNode* t)
{
if (t == NULL)
return 0;
return TreeNodeSize(t->left) + TreeNodeSize(t->right) + 1;
}
②计算二叉树叶子节点的个数:
int LeafSize(BTNode* t)
{
if (t == NULL)
return 0;
if (t->left == NULL && t->right == NULL)
return 1;
return LeafSize(t->left) + LeafSize(t->right);
}
③计算二叉树的高度:
int TreeHeight(BTNode* t)
{
if (t == NULL)
return 0;
int left = TreeHeight(t->left);
int right = TreeHeight(t->right);
return (left > right ? left : right) + 1;
}
④计算第k层的节点个数:
int Size_k(BTNode* t,int k)
{
if (t == NULL)
return 0;
if (k == 1)
return 1;
return Size_k(t->left, k - 1) + Size_k(t->right, k - 1);
}
⑤查找值为x的节点:
BTNode* BTFind(BTNode* t, BTDataType x)
{
if (t == NULL)
return NULL;
if (t->val == x)
return t;
BTNode* t1 = BTFind(t->left, x);
if (t1 != NULL)
return t1;
else
return BTFind(t->right, x);
}
⑥判断两棵树是否相同:文章来源:https://www.toymoban.com/news/detail-834520.html
bool isSameTree(BTNode* p, BTNode* q)
{
if (p == NULL && q == NULL) //在条件判别时,p==NULL等价于!p
return true;
if (p == NULL || q == NULL)
return false;
if (p->val != q->val)
return false;
bool left = isSameTree(p->left, q->left);
bool right = isSameTree(p->right, q->right);
return left && right;
}
⑦翻转二叉树:文章来源地址https://www.toymoban.com/news/detail-834520.html
BTNode* invertTree(BTNode* root)
{
if (root == NULL)
return NULL;
BTNode* _root = (BTNode*)malloc(sizeof(BTNode*));
if (_root == NULL)
{
perror("malloc error");
exit(-1);
}
_root->val = root->val;
_root->left = invertTree(root->right);
_root->right = invertTree(root->left);
return _root;
}
到了这里,关于树和二叉树的基本知识的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!