menu 首页 标签 归档 视频 关于
数据结构-树与二叉树再回顾(一)

一言加载中...

什么是树?

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

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

树的示例:

tree

树的层次:

树的根节点为第一层,根节点的孩子为第二层,以此类推。(示例图共四层)

树的度:

树的度,即子节点的个数;(如图中A节点的度为:2,D的度为:3,G的度为0)

叶子:

度数为0的节点;(如:G,H,I,J,F)

二叉树??

二叉树的性质

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

满二叉树

full tree

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

完全二叉树

Complete Tree

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

二叉树的遍历

请移步博文:
数据结构-二叉树的遍历(二)

TonyChenn
2018-10-17
写博客不易,请我喝杯咖啡?

评论

arrow_upward