二叉树和堆的概念和特点_二叉搜索树和堆的优缺点

前言

本篇文章将带大家了解二叉树和堆。二叉树和堆的外形非常相似，都是一个下宽上窄的金字塔结构，常常让人傻傻分不清楚。这篇文章将介绍二叉树和堆的概念，区别，以及他们的特点。

一、树

1.1 树的概念

树是一种非线性的数据结构，它是由若干个有限节点组成起来的，一种有层次关系的集合。他的根朝上，而叶朝下。

1.2 树的特点

• 根结点是树最上面的的结点，它没有前驱结点。

• 除根节点外，树的其他根结点被分为若干个子树，每一个子树都有一个自己的根节点和若干自己的子树

• 除根结点外，每个结点有一个前驱和若干的后继

• 树是递归的

1.3 孩子兄弟表示法

树的表示法有很多，如：双亲表示法，孩子表示法，孩子兄弟表示法等。这里只介绍最常用的孩子兄弟表示法：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7