本文共 877 字，大约阅读时间需要 2 分钟。

目录

树：（树的定义是递归定义）

1.树可以为空树，即没有节点。

2.树的每一个节点也可以是一棵树。

相关概念：

1.度：当前节点的子树棵数 ， 树的度（也叫树的宽度）：树中节点最大的度

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

3.满足连通、且边数等于节点数-1的结构一定是一棵树。

4.节点的深度：指从根节点自上而下逐层累加至该节点时的深度值（自上而下） 对于树来说：树的深度指树中最大的深度

5.节点的高度：指从叶子节点自下而上逐层累加至该节点时的高度值（自下而上）树的高度指树中最大的高度，树的高度和深度其实是相等的。

6.森林是若干树的集合。

二叉树的递归定义：

1.要么为空树

2.要么由根节点、左子树、右子树组成，左右子树也是二叉树。

二叉树与度为2的树的区别：

对树来说：他的子树没有顺序，而二叉树，他的左子树和右子树严格区分，不能随意交换位置。

二种特殊的二叉树：

1.满二叉树：每一层都达到了当前层所能达到的最大节点数。

如何判断一个二叉树是不是满二叉树？ 一个深度为k，节点个数为 2^k - 1 的二叉树为满二叉树。

2.完全二叉树：除了最下面的一层，剩余的每一层都达到了所能达到的最大层数，最低一层从左到右存在连续的若干节点，这些节点右侧不存在节点。

相关概念：

1.孩子节点、父亲节点、兄弟节点：这些意义如其名

2.祖先节点、子孙节点：如果存在一条从X到Y自上而下的路，那么X为Y的祖先节点，Y为X的子孙节点。注意：自己是自己的祖先节点，自己也是自己的子孙节点。

四种遍历方法：

1.与DFS有关的三种遍历方法：先序、中序、后序遍历，所谓的“先中后”，是指根节点在遍历中的位置，如：先序遍历，先访问根节点，再访问左子树，后访问右子树。

2.与BFS有关的遍历：层次遍历，

一层一层的访问，类似BFS那样。

相关性质：

1.如果给出中序遍历，再给出先序、后序、层次遍历这三者中的任意一个都可以确定一个唯一的二叉树。而后三者任意两个或三个都不能确定一个唯一的二叉树。因为这三个遍历作用都是相同的，而中序遍历可以确定左右子树。

如有错，请评论！

转载地址：http://huven.baihongyu.com/