赞
踩
(1)树的定义
树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。直观的看,树是以分支关系定义的层次结构。树是一种一对多的数据结构。
树 (Tree)是 n(n ≥ 0)个结点的有限集。n = 0 时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集 T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(Sub Tree)。如下图所示。
上图为一个结点 n =13 的树,其中结点 A 为唯一根结点,其余结点分成 3 个互不相交的子集:T1 = { B,E,F,K,L },T2 = { C,G},T3 = { D,H,I,J,M };T1,T2,T3都是 A 的子树,且本身也是一个树。如下图所示。
另,例如 T1 ,其根为 B ,其余结点又可分为互不相交的子集:T11 = { E,K,L },T12 = { F }。如下图所示。
即树的结构定义是一个递归的定义,即在树的定义中又用到树的概念,它道出了树的固有特性。
(2)树的基本术语
树的结点包含一个数据元素及若干个指向其子树的分支。
(3)二叉树的性质
二叉树(Binary Tree)是一种特殊的有序树。特点是,它的每一个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点);并且,二叉树的子树有左右之分,其次序不能任意颠倒。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。