什么是二叉树，二叉树及其应用
二叉树是一个结点的集合，其中每个结点最多与两个后继结点相关联，分别称为左侧子结点和右侧子结点。二叉树中的每个结点并不是全都有两个子结点，也可能只有一个结点或两个结点都可能被省略。在二叉树中，没有子结点的结点称为叶结点。
包含子结点的结点称为其子结点的父结点。对于一个定义为二叉树的非空的结点集合，每个结点必须至多有一个父结点，并且必须有一个结点是没有父结点的。这个没有父结点的结点称为二叉树的根结点。一个空的结点集合可以构成一个空的二叉树。
链表和二叉树有一些相似之处。二叉树的根对应于链表的头部，二叉树结点的子结点对应于链表中的后继结点，二叉树结点的父结点对应于链表中结点的前驱结点。当然，空链表的模拟是空的二叉树。
二叉树的实现
二叉树可用于将值存储到其结点中。因此，二叉树中的结点就是一个结构或类对象，它包含一个用于存储值的成员，以及另外两个指向该结点的左侧和右侧子结点的成员：
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
};
二叉树本身就是由指向根结点的指针所代表的。图 1 给出了一个二叉树示例，其中未显示结点中存储的值。如果该结点不具有相应的子结点，则结点中的 left 指针或 right 指针将设置为 nullptr。
发表评论