【数据结构与算法】二分钟初识树

一：树的定义

树是一种数据结构，由n(n>1)个有限结点组成一个有层次关系的集合。形状像一颗倒立的树而得名。分为：无序树，有序树，二叉树，满二叉树，完全二叉树，平衡二叉树（AVL），二叉查找树（二叉搜索树、BST），霍夫曼树，红黑树，B-tree（B-树或者B树），B+树，B*树等。

节点结构体(C/C++)表示为：

typedef struct treeNode
{
 void *val; //数据项，任意类型
 struct treeNode *left; //左子节点指针 
 struct treeNode *right; //右子节点指针
}node;

欢迎大家来到IT世界,在知识的湖畔探索吧!

节点类(Java)表示为：

欢迎大家来到IT世界,在知识的湖畔探索吧!public class TreeNode {
 private Object data; //数据项
 private TreeNode leftChild; //左子节点的引用
 private TreeNode rightChild; //右子节点的引用
}

二：树的特点

1.根节点没有父节点。

2.每个非根节点只有一个父节点。

3.每个节点有零个或多个子节点。

三：相关术语

1.节点的度：节点含有子树的个数

2.叶子节点：节点的度为0。

3.子节点：一个节点含有的子树的根节点称为该节点的子节点。(这句有点绕口，举例：上图a,b,c是R的子节点)

4.父节点：含有子节点的节点，成为子节点的父节点。

5.兄弟节点：父节点相同的节点。

6.堂兄弟节点：父节点为兄弟节点的节点。

7.树的度：最大的节点的度称为树的度

8.树的高度或深度：树种节点的最大层次。

9.森林：n(n>=0)颗互不相交树的集合。

四：树的遍历

1.前序遍历

遍历顺序：访问根节点—>遍历左子树—>遍历右子树

2.中序遍历

遍历顺序：遍历左子树—>访问根节点—>遍历右子树

3.后序遍历

遍历顺序：遍历左子树—>遍历右子树—>访问根节点