二叉树
二叉树是一种数据结构，由节点（node）组成，每个节点最多有两个子节点，分别称为左子节点（left child）和右子节点（right child）。一个节点也可以没有子节点，这时该节点就是叶子节点（leaf node）。
二叉树有许多不同的类型，其中比较常见的包括二叉搜索树、平衡二叉树、红黑树等。二叉搜索树的特点是，对于每个节点，它的左子树中所有节点的值都小于它的值，而右子树中所有节点的值都大于它的值。这使得二叉搜索树可以快速地查找、插入和删除节点，时间复杂度为O(log n)。
二叉树的创建和嵌套打印
首先用一个类来封装二叉树的节点
代码语言：javascript复制public class TreeNode {
int data;//数据
TreeNode left;//左子节点
TreeNode right;//右子节点
public TreeNode(){};
//构造函数
public TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}创建二叉树
代码语言：javascript复制public class BinaryTree {
Scanner scanner = new Scanner(System.in);
TreeNode root = null;//二叉树的根,默认为空
public TreeNode createBinaryTree() {//创建二叉树
TreeNode t;//当前树的根
int x = scanner.nextInt();//输入当前节点的值，如果为0则表示空节点
if (x == 0) {
t = null;
} else {
t = new TreeNode();
t.data = x;//data为往前节点的数值
t.left = createBinaryTree();
t.right = createBinaryTree();
}
return t;
}
}嵌套打印
代码语言：javascript复制public void printTree(TreeNode t) {//嵌套打印
if (t != null) {
System.out.print(t.data);//输出根节点
if (t.left != null || t.right != null) {
//只要左子节点和右子节点有一个不为空就输出
System.out.print("(");
printTree(t.left);//递归调用左子节点
if (t.right != null) {
System.out.print(",");
}
printTree(t.right);
System.out.print(")");
}
}
}二叉树的前中后序遍历
二叉树的遍历是指按照一定的顺序访问树中的每个节点。二叉树的三种遍历方式分别为前序遍历（pre-order traversal）、中序遍历（in-order traversal）和后序遍历（post-order traversal）。其中前序遍历的顺序是根节点-左子树-右子树，中序遍历的顺序是左子树-根节点-右子树，后序遍历的顺序是左子树-右子树-根节点。
前中后序遍历
代码语言：javascript复制public void preOrder(TreeNode root) {//前序遍历 根节点-左子树-右子树
if (root != null) {
System.out.print(root.data " ");
preOrder(root.left);
preOrder(root.right);
}
}
public void midOrder(TreeNode root) {//中序遍历 左子树-根节点-右子树
if (root != null) {
midOrder(root.left);
System.out.print(root.data " ");
midOrder(root.right);
}
}
public void postOrder(TreeNode root) {//后序遍历 左子树-右子树-根节点
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data " ");
}
}层次遍历
代码语言：javascript复制public void leverOrder(TreeNode root) {//层次遍历
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) return;
queue.offer(root);//根入列
while (!queue.isEmpty()) {
TreeNode head = queue.poll();//弹出列头
System.out.print(head.data " ");
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
}二叉树的深度和叶子节点的个数
代码语言：javascript复制 public int treeDepth(TreeNode root) {//求二叉树的深度
if (root == null) return 0;
return Math.max(treeDepth(root.left), treeDepth(root.right)) 1;
}
public int treeLeaf(TreeNode root) {//求二叉树的叶子数量
if (root == null) return 0;
else if (root.left == null && root.right == null) return 1;
else return treeLeaf(root.left) treeLeaf(root.right);
}演示各个遍历后的结果以及深度和叶子节点的个数
代码语言：javascript复制public class AppStart {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = binaryTree.createBinaryTree();
binaryTree.printTree(binaryTree.root);//嵌套打印
System.out.println();//换行
binaryTree.preOrder(binaryTree.root);//前序遍历
System.out.println();
binaryTree.midOrder(binaryTree.root);//中序遍历
System.out.println();
binaryTree.postOrder(binaryTree.root);//后序遍历
System.out.println();
binaryTree.leverOrder(binaryTree.root);//层次遍历
System.out.println();
System.out.println(binaryTree.treeDepth(binaryTree.root));//深度
System.out.println(binaryTree.treeLeaf(binaryTree.root));//叶子个数
}
}输入的数据为1 2 4 0 0 5 0 0 3 6 0 0 7 0 0，是因为4 5 6 7为叶子，没有子叶
二叉树的重建
二叉树的重建是指根据已知的二叉树的前序遍历和中序遍历序列，重新构建出二叉树的过程。具体过程如下：
（1）根据前序遍历序列，第一个元素为根节点，将其插入二叉树中。
（2）根据中序遍历序列，找到根节点在其中的位置，将中序遍历序列划分为左子树和右子树的序列。
（3）对于前序遍历序列，左子树序列的下一个元素即为左子树的根节点，右子树序列的下一个元素即为右子树的根节点。将它们插入二叉树中。
（4）递归处理左子树和右子树，重复步骤2和步骤3，直到序列为空或者只剩下一个元素。
代码语言：javascript复制import java.util.Scanner;
public class rebuiltBinaryTree {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String pre,mid;//定义前序和中序变量
while (scanner.hasNext()) {
pre = scanner.next();
mid = scanner.next();
System.out.println(f(pre,mid));
}
}
public static String f(String pre, String mid) {
if (pre.length() == 0) return "";
else if (pre.length() == 1) return pre;
else {
int pos = mid.indexOf(pre.charAt(0));//根据前序的根去中序里分左右
/*
public int indexOf(int ch)
返回指定字符在此字符串中第一次出现处的索引。
如果在此 String 对象表示的字符序列中出现值为 ch 的字符，则返回第一次出现该字符的索引
*/
String left = f(pre.substring(1, pos 1), mid.substring(0, pos));
/*
public String substring(int beginIndex,int endIndex)
返回一个新字符串，它是此字符串的一个子字符串。该子字符串从指定的 beginIndex 处开始，
直到索引 endIndex - 1 处的字符。因此，该子字符串的长度为 endIndex-beginIndex
*/
String right = f(pre.substring(pos 1), mid.substring(pos 1));
/*
public String substring(int beginIndex)
返回一个新的字符串，它是此字符串的一个子字符串。
该子字符串从指定索引处的字符开始，直到此字符串末尾。
*/
return left right pre.charAt(0);//前序的第一个字符是根
}
}
}
