数据结构-树与二叉树再回顾（一）｜默然的博客

什么是树？

树是n个节点的有限集合。当n==0时为空树，n>0时为非空树；

• 树只有一个根节点
• 除了根结点的其他所有节点又是一个新树，称为根节点的子树。

树的示例：

树的层次：

树的根节点为第一层，根节点的孩子为第二层，以此类推。（示例图共四层）

树的度：

树的度，即子节点的个数；（如图中A节点的度为：2，D的度为：3，G的度为0）

叶子：

度数为0的节点；（如：G，H，I，J，F）

二叉树？？

二叉树的性质

• 在二叉树的第i层至多含有个节点$2^{n-1}$
• 深度为k的二叉树最多含有$2^k-1$个节点
• 对于任意一个二叉树，度为0的节点个数=度为2节点个数+1

满二叉树

• 深度为k，且含有$2^k-1$个节点的二叉树成为满二叉树；
• 每一层节点数都为最大节点数

完全二叉树

• 叶子节点只能在层次最大的两成出现
• 具有n个节点的完全二叉树深度为：⌊log₂n⌋+1
• 对于一个含有n个节点的完全二叉树，对于任意一个节点i:
  • 如果 i=1，则i节点为根节点
  • 如果 i>1，则i节点的双亲节点为：$\frac{i}{2}$
  • 如果 2i>n，则i节点为叶子节点（无子节点）,否则，i节点的左孩子节点为2i
  • 如果2i+1>n，则i节点无右子节点，否则，右子节点为2i+1

二叉树的遍历

请移步博文：
数据结构-二叉树的遍历（二）

TonyChenn
2018-10-17

相关阅读

• 数据结构-二叉排序树(三)
• 数据结构-二叉树的遍历（二）