树的术语
- 根节点、父节点、子节点、兄弟节点
- 叶子节点、分支节点
- 节点的度：即节点的分支数
- 树的度：节点的度的最大值
- 节点的层数：树的层数
树的链式存储
- 采用二叉链表的形式：数据域+左孩子节点+右孩子节点
package com.tree;
public class TreeNode{
private String data;
private TreeNode leftNode = null;
private TreeNode rightNode = null;
public TreeNode(String data){
this.data = data;
}
public String getData(){
return data;
}
public TreeNode getLeft(){
return leftNode;
}
public TreeNode getRight(){
return rightNode;
}
public void setLeft(TreeNode left){
this.leftNode = left;
}
public void setRight(TreeNode right){
this.rightNode = right;
}
}
二叉树
树的每个节点至多有两棵子树，且子树有左右之分。二叉树的性质如下：
- 二叉树的第 i 层至多有 2^( i - 1)个节点
- 深度为 k 的二叉树至多有 2^k - 1个节点
- 二叉树的叶子节点的个数比度为2的节点的个数多一
满二叉树
深度为k且有2^k - 1个节点的二叉树称为满二叉树。
完全二叉树
对满二叉树中的节点从根节点开始自上而下、自左至右连续编号，其中任意1 - n个节点形成的二叉树称为完全二叉树。
完全二叉树的特点和性质如下：
- 叶子节点只可能在层次最大的两层上出现
- 对具有 n 个节点的完全二叉树进行顺序存储，对于其中任意一个节点 i ，存在如下关系：
