定义
树是n(n>=0)个结点的有限集。n=0时,称为空树。在任意一棵树非空树中应满足:
(1) 有且仅有一个特定的称为根 (root) 的结点(2) 当时,其余结点可分为个互不相交的有限集,其中每一个集合本身又是一颗树,并且称为根的子树。
基本概念
结点的度:一个结点拥有的子树的数目
叶子结点:度为0的结点
树的度:树内各结点的度的最大值
树的深度或高度:树中结点的最大层次
森林:由m(>=0)棵互不相交的树的集合称为森林
有序树和无序树:树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树
路径和路径长度:路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数
树的类型
二叉树
二叉树的特点包括:(1)每个结点最多有两个子结点,分别称为左子结点和右子结点。
(2)左子树和右子树都是二叉树,它们本身也可以是空树。
(3)二叉树的结点结构包含一个数据元素和指向左右子树的指针。
二叉树和度为2的树
1.度为2的树至少有一个结点度数为2,而二叉树可以为空
2.度为2的树不区分左右子树
二叉排序树(二叉查找树/二叉搜索树)
(1)若左子树不空,则左子树上所有结点的值均小于它的 根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左,右子树也分别为二叉排序树;
平衡二叉树(AVL树)
平衡二叉树特点包括:- 左子树和右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
标签:左子,结点,路径,--,右子,二叉,二叉树,数据结构 From: https://www.cnblogs.com/hui-xiang/p/18534165