使用Java实现一个二叉树。
二叉树是一个递归的数据结构，每个节点最多有两个子节点，且有左右之分，分别称为该节点的左右孩子。二叉树是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树形式，因此二叉树显得特别重要，但它的存储结构和算法都较为简单。
二叉树结构以及代码实现很容易，但一定要注意理解递归思想，只要可以很好地理解递归思想，解决二叉树相关问题难度就降低很多了，大家可以参考我博客的内容自己手敲一边代码实现二叉树，收获一定会很大，一起加油
目录
模拟实现二叉树
定义节点类
二叉树的初始化
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的节点个数
求二叉树的叶子节点数
获取第K层节点个数
获取二叉树的高度
二叉树的查询
完整代码
模拟实现二叉树
二叉树的结构如下图所示，本篇文章是实现一个字符型的二叉树
定义节点类
根据二叉树的定义，它有两个节点，且有左右之分，称为左孩子和右孩子，则根据定义，可以定义出二叉树的节点类
class TreeNode {
public char val;
public TreeNode left;//左孩子
public TreeNode right;//右孩子
public TreeNode(char val) {
this.val = val;
}
}
二叉树的初始化
为了方便实现二叉树的操作，首先手动初始化一棵二叉树，二叉树包含A、B、C、D、E、F、G、H八个节点，具体结构如下图所示
具体代码如下：
public TreeNode creteTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return A;//根节点
}
二叉树的先序遍历
根据定义，二叉树的先序遍历顺序为：根节点->左孩子->右孩子，则根据先序遍历顺序，可以得到上述初始化的二叉树先序遍历顺序为：ABDEHCFG
具体代码如下：
// 先序遍历
void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
二叉树的中序遍历
二叉树的中序遍历顺序为：左孩子->根节点->右孩子，根据该遍历顺序，可以得出上述初始化二叉树的中序遍历顺序为：DBEHAFCG
具体代码如下：
// 中序遍历
void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
二叉树的后序遍历
二叉树的后序遍历顺序为：左孩子->右孩子->根节点，根据该遍历顺序，可以得出上述初始化二叉树的后序遍历顺序为：DHEBFGCA
具体代码如下：
// 后序遍历
void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
二叉树的节点个数
求二叉树的节点个数有两种方式：一种是遍历思路，另一种思路是子问题思路。
遍历思路
定义一个全局变量count，用来记录树中的节点个数，利用递归依次遍历二叉树，求出节点个数.
public static int count = 0;//记录节点个数
// 获取树中节点的个数
public void size1(TreeNode root) {
if (root == null) {
return;
}
count++;
size1(root.right);
size1(root.left);
}
子问题思路
利用递归思想不遍历，将整个树分为若干的小树，来求出二叉树的节点个数.节点数为左子树节点 + 右子树节点 + 1.
public int size2(TreeNode root) {
if (root == null) {
return 0;
}
//root不为空
int tmp = size2(root.left) + size2(root.right) + 1;
return tmp;
}
求二叉树的叶子节点数
叶子节点：度为0的节点称为叶子节点，即该节点无左右孩子.
求二叉树的叶子节点数依旧有遍历和分为子问题两种思路。
遍历思想：
定义全局变量num，用来记录叶子节点个数，依次遍历该二叉树，如果该节点的左孩子为空且右孩子为空，则num + 1，具体代码如下：
// 获取叶子节点的个数 遍历思路
public static int num = 0;
void getLeafNodeCount1(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
num++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
子问题思想：
// 获取叶子节点的个数 子问题
int getLeafNodeCount2(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}
获取第K层节点个数
获取第k层节点，即求的是当k等于1时，有多少个节点，例如需要求出第三层的节点个数，二叉树的结构如下图所示，k从3开始，当k = 1时，即处在第三层，求出该层有多少个节点即可.
具体代码实现：
// 获取第K层节点的个数
int getKLevelNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.right, k - 1) + getKLevelNodeCount(root.left, k - 1);
}
获取二叉树的高度
要求出二叉树的高度，即求出左子树的高度，再求出右子树的高度，判断哪个高，如果左子树高，则左子树的高度+1即为该二叉树的高度.
具体代码实现：
// 获取二叉树的高度
int getHeight(TreeNode root){
if(root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
二叉树的查询
二叉树的查询利用遍历的思想，以递归的方式实现，首先判断根节点的值是否为待查值，如果不是则依次访问左子树和右子树，如果找到，则返回该节点，如果未找到则返回null.
具体代码实现：
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = find(root.left, val);
if (ret != null) {
return ret;
}
ret = find(root.right, val);
if (ret != null) {
return ret;
}
return null;
}
完整代码
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class TestBinaryTree {
public TreeNode creteTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return A;//根节点
}
// 前序遍历
void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历
void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
public static int count = 0;
// 获取树中节点的个数 遍历思路：
public void size1(TreeNode root) {
if (root == null) {
return;
}
count++;
size1(root.right);
size1(root.left);
}
//获取树中节点的个数 子问题思路
public int size2(TreeNode root) {
if (root == null) {
return 0;
}
//root不为空
int tmp = size2(root.left) + size2(root.right) + 1;
return tmp;
}
// 获取叶子节点的个数 遍历思路
public static int num = 0;
void getLeafNodeCount1(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
num++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
// 获取叶子节点的个数 子问题
int getLeafNodeCount2(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}
// 获取第K层节点的个数
int getKLevelNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.right, k - 1) + getKLevelNodeCount(root.left, k - 1);
}
// 获取二叉树的高度
int getHeight(TreeNode root){
if(root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = find(root.left, val);
if (ret != null) {
return ret;
}
ret = find(root.right, val);
if (ret != null) {
return ret;
}
return null;
}
}
