一、简介
今天这篇文章，介绍一下和二叉树有关的操作，所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。 这部分包括：
- 递归遍历二叉树（先序遍历、中序遍历、后序遍历）
- 分层打印二叉树
- 打印二叉树的第n层
- 统计二叉树叶结点的个数
- 统计二叉树的高度
1. 解决思路
二叉树的遍历方式有以下三种：
- 先序遍历：根结点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根结点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 根结点
递归的方式比较容易理解，只需要改变函数调用和打印元素值语句之间的顺序即可，例如先序遍历，就先打印该结点元素的值，再分别打印左子树和右子树即可。
2. 代码实现
class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i > 3
>> 1 5
>> -1 2 4 6
>> -3
1. 解决思路
打印二叉树的第n层和2.2中是相同的原理，只不过是在遍历到第n层时才打印所需的元素。
2. 代码实现
import java.util.LinkedList;
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i k) {
break;
}
end = queue.getLast();
} else {
System.out.print(" ");
}
//将该结点从队列头部删除。
queue.pop();
}
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
printTreeKLevel(tree, 3);
}
}
3. 运行结果
>> -1 2 4 6
1. 解决思路
叶结点指的是没有左右子树的结点，因此二叉树的叶结点个数等于它的左右子树叶结点之和，可以通过递归的方法来实现。
2. 实现代码
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i > 叶结点个数=4
1. 解决思路
二叉树的高度 为其根结点到叶结点的最大距离，我们可以先求出它的左右子树的高度的最大值，再加上1就可得到以该结点为根结点的二叉树的高度，同样可以采用递归的方式来实现。
2. 代码实现
public class Untitled {
static class Tree {
int size;
Node root;
}
static class Node {
Node parent;
Node left;
Node right;
int value;
}
static void insertNode(Tree tree, int value) {
if (tree == null) {
return;
}
Node tNode = tree.root;
//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
Node pNode = null;
//新的结点。
Node nNode = new Node();
nNode.value = value;
while (tNode != null) {
pNode = tNode;
if (tNode.value > value) {
tNode = tNode.left;
} else {
tNode = tNode.right;
}
}
nNode.parent = pNode;
if (pNode == null) {
tree.root = nNode;
} else if (pNode.value > value) {
pNode.left = nNode;
} else {
pNode.right = nNode;
}
tree.size++;
}
static Tree createBinTree(int p[], int len) {
Tree tree = new Tree();
for (int i = 0; i right ? left : right;
}
public static void main(String[] args) {
int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
Tree tree = createBinTree(p, p.length);
System.out.println("二叉树高度=" + getTreeHeight(tree.root));
}
}
3. 运行结果
>> 二叉树高度=4
