树

概念

树是一种非线性的数据结构, 它是由n(n>=0)个有限结点组成一个具有层次关系的集合. 把它叫做树是因为它看起来像一棵倒挂的树, 也就是说它是根朝下, 而叶朝上的.

树的特点

每个结点有零个或多个子节点没有父节点的结点称为根节点每个非根节点有且只有一个父节点除了根节点外, 每个子节点可以分为多个不相交的子树

节点的度: 一个节点含有的子树的个数称为该节点的度; 如A的度为6

叶节点(终端节点): 度为0的节点称为叶节点; 如B, C, H, I....等节点为叶节点

分支节点(非终端节点): 度不为0的节点; 如D, E, F, G....等节点为分支节点

父节点(双亲节点): 若一个节点含有子节点, 则这个节点称为其子节点的父节点; 如A是B的父节点

子节点(孩子节点): 一个节点含有的子树的根节点称为该节点的子节点; 如B是A的子节点

兄弟节点: 具有相同父节点的节点互称为兄弟节点; 如B, C是兄弟节点

树的度: 一棵树中, 最大的节点的度称为树的度; 如上图树的度为6

节点的层次: 从根开始定义起, 根为第一层, 根的子节点为第二层,由此类推

树的高度(深度): 树中节点的最大层次; 上图树的高度为4

堂兄弟节点: 双亲在同一层的节点互称为堂兄弟; 如H, I互为堂兄弟节点

节点的祖先: 从根到该节点所经分支上的所有节点; 如A是所有节点的祖先

子孙: 以某节点为根的子树中任一节点都是该节点的子孙; 上图所有节点都是A的子孙

森林: 有m(m>=0)棵互不相交的树的集合称为森林

树的表示方式

双亲表示法

struct Node { TDataType _data; struct Node* _parent; };

孩子表示法

struct Node { TDataType _data; struct Node* child1; struct Node* child2; struct Node* child3; };

孩子兄弟表示法

struct Node { TDataType _data; struct Node* _firstChild; //第一个孩子节点 struct Node* _pNextBrother; //指向下一个兄弟节点 };

二叉树

概念

一棵二叉树是节点的一个有限集合, 该集合或者为空, 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

特点

每个结点最多有两棵子树, 即二叉树不存在度大于2的节点

二叉树的子树有左右之分, 其子树的次序不能颠倒

特殊的二叉树

满二叉树: 一个二叉树, 如果每一层的节点数都达到了最大值, 则这个二叉树就是满二叉树完全二叉树: 对于深度为k, 有n个节点的二叉树, 当且仅当其每一个节点都与深度为k的满二叉树中 编号从1至n的节点一一对应时称为完全二叉树. (满二叉树是一种特殊的完全二叉树)

二叉树的存储结构

顺序存储

顺序结构存储就是使用数组来存储, 一般使用数组只适合表示完全二叉树, 因为不是完全二叉树会有空间的浪费. 二叉树的顺序存储在物理上是一个数组, 在逻辑上是一棵二叉树

链式存储

二叉树的链式存储结构是指, 用链表来表示一棵二叉树, 即用链来指示元素的逻辑关系. 通常的方法是链表中每一个节点有三个域组成, 数据域和左右指针域, 左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址.