树
在介绍二叉树之前，我们需要先明白什么是树，因为二叉树是树的其中一种，因为我们用的最多，所以我们大多都在学习和了解二叉树。
树是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。
树具有以下特点：
- 每个节点都只有有限个子节点或无子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 树里面没有环路(cycle)
树还有一些专用的术语和概念，我们通过下边这个图为例来说明。
- 节点的度： 一个节点含有的子树的个数为该节点的度（如下图中 A 节点的度为 2）
- 树的度：一棵树中，度最大的那个节点度即为树的度（下图中度最大的节点为 B，其度为 3，所以树的度为 3）
- 根节点：没有父节点的节点称为根节点（如图中的 A 节点）
- 叶节点：度为零的节点（如图中的 K,J,F,L,O,P 节点）
- 分支节点：度不为零的节点
- 子节点：一个节点含有的子树的跟节点称为该节点的子节点（如图中，B 和 C 为 A 的子节点）
- 父节点：如果一个节点含有子节点，那么这个节点称为其子节点的父节点（如图中，A 为 B 和 C 的父节点）
- 兄弟节点：具有相同父节点的节点互为兄弟节点（如图中，B 和 C 互为兄弟节点）
- 层：根为第1层，根的子节点为第2层，以此类推
- 深度：对于任意节点 n ，n 的深度为从根到 n 的唯一路径长，根的深度为0
- 高度：对于任意节点 n ，n 的高度为从 n 到叶节点的最长路径长，所有叶节点的高度为0
dOymDA.png
二叉树
树的种类有很多，不过最常用的还是二叉树。
二叉树，顾名思义，我们就能知道每个节点最多有两个子节点，分别称为左子节点和右子节点。当然，并不是每个节点都有两个节点，也可能有的只有左子节点，有的只有右子节点。
二叉树中有两种特殊的类型，满二叉树和完全二叉树。
叶子节点全部都在最底层，除叶子节点外，每个节点都有两个子节点，这种二叉树称作满二叉树（如下图）。
在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（如下图）。
dzWbND.png
二叉树的存储
我们上面已经基本了解了什么是二叉树，那么我们在使用的时候是怎么来存储的呢？
我们首先来看顺序存储法。我们把根节点放在索引为 的位置（假设根节点的索引为0），那么他的左子节点的索引会是
，右子节点的索引会是
，而他的父节点（如果有）索引则为
。这种存储方法更有利于紧凑存储和单个节点的访问，例如上边提到的满二叉树和完全二叉树就非常适合用这种方法存储，紧凑排列而不浪费空间。因为这种方法需要连续的存储空间，所以如果不是完全二叉树的话就会浪费不少的存储空间，这也是这种存储方法的一个缺点。
我们再来看一下链式存储法。链式存储法比较简单直观。每个节点存储三个字段，其中一个是该节点的数据，另外两个是指向左右子节点的指针。我们只要通过根节点，就可以通过左右子节点的指针，把整棵树都串起来。这也是我们比较常用的存储方式。大部分的二叉树也都是通过这种结构实现的。
二叉树的遍历
前边说了定义和存储方法，现在我们来看一下二叉树的遍历（面试常问）。
怎样把二叉树的所有节点都输出出来呢，有三种常用的方法，前序遍历、中序遍历和后序遍历。他们的不同在于输出节点和它左右子节点的先后顺序。
前序遍历
前序遍历是指，对于二叉树的任意节点，我们首先输出该节点，然后输出它的左子树，最后输出它的右子树。
我们来看一下具体的代码实现：
//节点结构类
class TreeNode
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
//前序遍历，递归实现
public void preOrderRe(TreeNode node)
{
System.out.println(node.value);
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
}
//前序遍历，借用栈实现
public void preOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
System.out.println(nd.value);
stack.push(nd);
nd = nd.left;
}
else
{
nd = stack.pop();
nd = nd.right;
}
}
}
中序遍历
中序遍历是指，对于树中的任意节点，我们首先输出它的左子树，然后再输出它本身，最后输出它的右子树。
我们来看一下具体的代码实现：
//中序遍历，递归实现
public void midOrderRe(TreeNode node)
{
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
System.out.println(node.value);
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
}
//中序遍历，借用栈实现
public void midOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
stack.push(nd);
nd = nd.left;
}
else
{
nd = stack.pop();
System.out.println(nd.value);
nd = nd.right;
}
}
}
后序遍历
后序遍历是指，对于树中的任意节点来说，我们首先输出它的左子树，然后再输出它的右子树，最后输出这个节点本身。
我们来看一下具体的代码实现：
//后序遍历，递归实现
public void postOrderRe(TreeNode node)
{
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
System.out.println(node.value);
}
//后序遍历，借用栈实现
public void postOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
//构造一个中间栈来存储逆后序遍历的结果
Stack<TreeNode> output = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
output.push(nd);
stack.push(nd);
nd = nd.right;
}
else
{
nd = stack.pop();
nd = nd.left;
}
}
while(output.size() > 0)
{
System.out.println(output.pop());
}
}
内容小结
以上就是树和二叉树一些基础的知识，我们来总结回顾一下。我们讲了一种非线性数据结构树，树有几个比较常用的概念我们需要了解和掌握：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。
我们最常用的树就是二叉树。二叉树每个节点最多有两个子节点，左子节点和右子节点。我们又介绍了两种比较特殊的树，满二叉树和完全二叉树，满二叉树其实也属于完全二叉树。
二叉树的存储方式有顺序存储和链式存储。顺序存储比较适合完全二叉树，会更充分利用内存空间而不会造成浪费。链式存储是比较简单直观，也是比较常用的存储方法。还有非常重要的二叉树前、中、后序遍历，是我们必须要掌握的。
网友评论