数据结构基础之树和二叉树_非空树被定义”{l,a,r}”。其中 l 为左子树,r 为右子树,a 为节点编号。

点击上方“程序猿小哈”，选择“置顶公众号”

有趣有内涵的文章第一时间送达！

 

 

数据结构基础之树和二叉树

前言

树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。一直以来，对于树的掌握都是模棱两可的状态，现在希望通过写一个关于二叉树的专题系列。在学习与总结的同时更加深入的了解掌握二叉树。本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。希望各位读者能够关注专题，并给出相应意见，通过系列的学习做到心中有“树”.

基本概念

节点

节点:数据结构中的基础,是构成复杂数据结构的基本组成单位.本文中所有的节点专指树的节点.例如结点A在图中表示为:

节点的度和关系

• 节点拥有的子树数目称为节点的度.

• 点子数的节点为该节点的孩子节点.该节点就是子节点的父节点,孩子节点之间为兄弟节点.

如图所示 节点的度.A为B的双亲节点,B为A的孩子节点,B与C互为兄弟节点.

树

树（Tree）是n（n>=0)个结点的有限集.

• n=0时称为空树.

• 在任意一颗非空树中：

1.有且仅有一个特定的称为根（Root）的节点.

2.当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树.

如图为为一棵普通的树:

由树的定义可以看出,树的定义使用了递归的方式.递归在树的学习过程中起着重要作用,如果对于递归不是十分了解,建议先看看递归算法.

节点的层次

从根开始定义起,根为第一层,根的孩子为第二层,以此类推. 如图所示树的层次关系

树的深度

树中节点的最大层次数称为树的深度或高度.

二叉树

二叉树是n(n>=0)个结点的有限集合,该集合为空时称为空二叉树. 如图为一棵普通二叉树:

二叉树的特点

1. 每个节点最多有两颗子树,所以二叉树中不存在度大于2的节点.(知道为什么叫二叉了吧

   声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/592525