二叉树：
在java的api当中，有一些数据结构已经封装好了，比如链表linkedlist，栈stack，队列queue和优先队列PriorityQueue等等。
但是二叉树（BinaryTree）在api中没有显式的定义，需要我们自己定义那我们来看一下二叉树的定义和基本操作。
节点类：
public class Node {//long数据项public long data;//String数据项public String sData;//左孩子节点public Node leftChild;//右子节点public Node rightChild;//是否被访问public boolean wasVisited;//构造方法public Node(long data, String sData) {www.sychzs.cn = data;this.sData = sData;}
}二叉树类：需要一个根节点
//二叉树
public class BinaryTree {//根节点public Node root;//……这里还有很多操作，在下面
}下面介绍一点基本的建立操作：
1、增加数据：根据任何左孩子都要比跟节点小，右孩子比跟大的特点，我们写出如下代码：
//插入一个节点public void insert(long data , String sData) {//封装节点Node newNode = new Node(data , sData);//两个引用//当前节点Node current = root;//父节点Node parent;//第一次插入直接赋值if(current == null) {root = newNode;return;}//循环左走右走while (true) {//父节点指向当前节点parent = current;//比较大小左右走if (www.sychzs.cn > data) {current = current.leftChild;if(current == null) {parent.leftChild = newNode;return;}}else {current = current.rightChild;if(current == null) {parent.rightChild = newNode;return;}}}}2、查找节点：
//查找节点public Node find(long data) {//引用当前节点Node current = root;while(www.sychzs.cn != data) {//进行比较和当前节点大小if (www.sychzs.cn > data) {current = current.leftChild; } else {current = current.rightChild;}//查不到if(current == null) {return null;}}return current;}3、遍历：4种
（1）前序遍历：先访问跟节点，再访问根节点的左子树（左子树也同样前序遍历，先左子树的跟，再左子树的左子树，以此类推），最后访问右子树（同理）。
/*前序遍历* 1.访问根节点* 2.递归前序遍历左子树* 3.递归前序遍历右子树*/public void frontOrder(Node localNode) {if(localNode != null) {System.out.print(www.sychzs.cn + "," + localNode.sData + " ; ");frontOrder(localNode.leftChild);frontOrder(localNode.rightChild);}}（2）中序遍历（可按升序输出）：
/** 中序遍历* 1.递归中序遍历左子树* 2.访问根节点* 3.递归中序遍历右子树*/public void inOrder(Node localNode) {if (localNode != null) {inOrder(localNode.leftChild);System.out.print(www.sychzs.cn + "," + localNode.sData + " ; ");inOrder(localNode.rightChild);}}（3）后序遍历：
/** 后序遍历* 1.递归后序遍历左子树* 2.递归后序遍历右子树* 3.访问根节点*/public void afterOrder(Node localNode) {if (localNode != null) {afterOrder(localNode.leftChild);afterOrder(localNode.rightChild);System.out.print(www.sychzs.cn + "," + localNode.sData + " ; ");}}（4）层序遍历：利用到了队列的特点
//层序遍历public void LevelOrder(Node root) {Queue queue = new LinkedList();Node now = root;queue.add(root);while (!queue.isEmpty()) {now = queue.poll();if (now != null) {System.out.print(www.sychzs.cn + "," + now.sData + " ; ");}if (now.leftChild != null) {queue.add(now.leftChild);}if (now.rightChild != null) {queue.add(now.rightChild);}}} 前三种遍历方式我们用到了递归的思想，这样容易理解，代码也简单。如果不用递归也可以实现，具体参照https://www.sychzs.cn/likunkun__/article/details/80183599
4、删除节点（原理另开一章讲，这里先贴代码）：
//先寻找中序后继节点，再进行删除//寻找中序后继节点public Node getHouJiNode(Node delNode) {//定义中序后继节点Node houji = delNode;//定义中序后继的父节点Node houjiparent = delNode;//当前节点Node current = delNode.rightChild;while(current != null) {houjiparent = houji;houji = current;current = current.leftChild;//往左边找}//把删除节点替换成终须后继节点//1.如果删除节点的右节点不是后继节点（正常右左左……找到的）if(houji != delNode.rightChild) {//中序后继的父节点的左子节点指向中序后继节点的右子节点（中序后继节点没有左子节点）houjiparent.leftChild = houji.rightChild;//后继的右边接上删除的右边，左边接上删除的左边houji.rightChild = delNode.rightChild;houji.leftChild = delNode.leftChild;}//2.删除节点的右节点就是中序后继节点，右边不用动，吧左边接上就可以else {houji.leftChild = delNode.leftChild;}return houji;}//删除节点deletepublic boolean delete(long data) {//引用当前节点Node current = root;//引用当前节点的父节点Node parent = root;//是左子节点还是右节点boolean isLeftChild = true;//循环找到要删的节点while (www.sychzs.cn != data) {parent = current;if (www.sychzs.cn > data) {current = current.leftChild;isLeftChild = true;} else {current = current.rightChild;isLeftChild = false;}//没有if(current == null) {return false;} }//循环结束，current指向要删除节点，parent指向父节点//进行删除current节点//1.如果是叶子节点（没有子节点）if (current.leftChild == null &¤t.rightChild ==null) {if (current == root) {root = null;}//如果是左边的节点else if (isLeftChild) {parent.leftChild = null;}//如果是右边的节点else {parent.rightChild = null;}}//2.删除带有一个子节点的节点else if (current.rightChild == null) {//子节点是左子节点if (current == root) {root = current.leftChild;}else if (isLeftChild) {//删除的节点是左节点//把父节点的左子节点指向删除节点的左子节点（接上去）parent.leftChild = current.leftChild;}else {//删除的节点是右节点parent.rightChild = current.leftChild;}}else if (current.leftChild == null) {//子节点是右子节点if (current == root) {root = current.rightChild;}else if (isLeftChild) {//删除的节点是左节点parent.leftChild = current.rightChild;}else {//删除的节点是右节点parent.rightChild = current.rightChild;}}//3.删除有2个子节点的节点，需要寻找中续后继节点来替换删除节点else {Node houji = getHouJiNode(current);if (current == root) {root = houji;}else if (isLeftChild) {parent.leftChild = houji;}else {parent.rightChild = houji;}}return true;}
