二叉树（上）
目录
树型结构
概念
二叉树
概念
二叉树的存储
二叉树基本操作
基本变量
二叉树的遍历
完整代码
树型结构
概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树状图的形式如下图所示
二叉树
概念
一棵二叉树是结点点的一个优先集合，该集合有以下两种情况
- 为空
- 有一个根结点加上两棵分别称为左子树和右子树的二叉树组成
二叉树如图所示
特殊的二叉树
满二叉树：二叉树的每层节点数都达到最大值，这棵树就是满二叉树。如果一颗二叉树的层数为k，且节点总数是2^k - 1,则它就是满二叉树。
完全二叉树：对于深度有k的，有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。满二叉树是一种特殊的完全二叉树。
二叉树的存储
二叉树的存储结构分为：顺序存储 和 类似于链表的链式存储。
本文先介绍的是第二种： 类似于链表的链式存储。
二叉树的链式存储时通过一个一个结点引用起来的，常用的表达方式有二叉和三叉表达方式。
因为这里主要运用的是二叉表示法（下面称为孩子表示法），故先以这种方法为例。
//孩子表示法
class Node{
Node root; //根结点
Node right; //左孩子，常代表左孩子为根的整棵左子树
Node left; //右孩子，常代表右孩子为根的整棵右子树
int val; //数据域
}二叉树基本操作
为了减少二叉树的学习成本，我们可以先创建一棵简单的二叉树，以方便快速进入二叉树的操作学习。
基本变量
首先我们要创建关于二叉树的一些基本变量，根据 孩子表示法 来进行。创建的二叉树如图所示
public class BinaryTree {
static class TreeNode{
public TreeNode left;
public TreeNode right;
public char val;
public TreeNode(char val){
this.val = val;
}
}
public TreeNode createTree(){
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;
}
}再次提醒：上述代码并不是创建二叉树的方式，只是为了减少学习成本而简单实现的二叉树
通过调试可以看到，A的左子树是B，A的右子树为C，依次向下推。
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createTree();
}
}
二叉树的遍历
二叉树的遍历方式有：前序遍历，中序遍历，后序遍历以及层序遍历。这里先主要了解前中后序遍历，层序遍历后序会以例题的方式提出来。
- 前序遍历：依照 根结点 ——> 根的左子树 ——> 根的右子树 进行遍历
- 中序遍历：依照 根的左子树 ——> 根结点 ——> 根的右子树 进行遍历
- 后序遍历：依照 根的左子树 ——> 根的右子树 ——> 根结点 进行遍历
可以把前面的前中后看作是根据 根结点的位置 来定义的，方便记忆。
这三种遍历的实现都是依靠递归来实现的，通过根节点的形式上的不断变化来实现递归。
前序遍历
依照 根结点 ——> 根的左子树 ——> 根的右子树 进行遍历。
//前序遍历
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createTree();
System.out.print("前序遍历：");
binaryTree.preOrder(root);
}
}输出结果为：
整个过程可以对比着下面这张图来看。
中序遍历
依照 根的左子树 ——> 根结点 ——> 根的右子树 进行遍历
// 后序遍历
public void postOrder(TreeNode root) {
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}输出结果为：
后序遍历
// 后序遍历
public void postOrder(TreeNode root) {
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}输出结果为：
这篇文章到这里就结束了，主要介绍了树和二叉树的概念方面的大致内容，以及实现二叉树的创建和三种遍历方式。
之后也会进行二叉树基本操作的实现以及对应问题的自己的理解，如果有不妥的地方，还请指出，一定会进行改正。
完整代码
BinaryTree类
public class BinaryTree {
static class TreeNode{
public TreeNode left;
public TreeNode right;
public char val;
public TreeNode(char val){
this.val = val;
}
}
public TreeNode createTree(){
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;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}Test类
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createTree();
System.out.print("前序遍历：");
binaryTree.preOrder(root);
System.out.println();
System.out.print("中序遍历：");
binaryTree.inOrder(root);
System.out.println();
System.out.print("后序遍历：");
binaryTree.postOrder(root);
}
}