二叉树的概念1，将每个节点最多只有两个子节点的树称为二叉树
2、二叉树的子节点分为左节点和右节点
3、如果二叉树的所有节点都在最后一个层次，节点总数为2^n-1，n为阶数，则称该二叉树为满二叉树
4 .如果此二叉树的所有叶节点都在最后一层或倒数第二层，且最后一层叶节点在左边连续，倒数第二层叶节点在右边连续，则此二叉树称为完全二叉树
二叉树扫描前序扫描：先输出父节点，并扫描左子树和右子树
中顺序扫描：先扫描左子树，再输出父节点，再扫描右子树
后面的遍历：首先遍历左侧的子树，然后遍历右侧的子树，查找最后输出父节点
遍历前后的顺序取决于父节点的输出顺序。
先行横移步骤
输出当前节点(初始节点全部为根节点) )。
如果左子树节点不为空，递归向前遍历左子树
如果右子节点不为空，递归向前遍历右子树
中顺序扫描步骤
如果当前节点左边的子节点不为空，递归地中顺序扫描左边的子树
输出当前节点
如果当前节点的右子节点不为空，递归遍历右子树
后面的横移步骤
如果当前节点左边的子节点不为空，则递归遍历左边的子树
如果当前节点右边的子节点不为空，则递归向后遍历右边的子树
输出当前节点
该实例创建了三个类，并将其全部放在Binary包下
heroNode的实现
成员变量：
成员方法：
heronode(intno，String name )是一种构造方法，不需要传递给左右子节点，默认值为null
getNo (，getNo )、getname (getname )、getname (getname )和stringname (字符串名称)用于获取或设置私有成员变量的序列号和名称
setleft(Heronodeleftnode )设定左侧的子节点
setright(Heronoderightnode )是设置右子节点
toString ) )是一种改写方法，是为了容易输出节点信息
preOrder ()是前导遍历
inOrder ()是后续遍历
postOrder ()是中顺序遍历的前顺序遍历
输出当前节点(初始节点全部为根节点) )。
如果左子树节点不为空，递归向前遍历左子树
如果右子节点不为空，递归向前遍历右子树
/*超前遍历输出当前节点(初始节点均为根节点)如果左侧子节点不为空，递归超前遍历左侧子树如果右侧子节点不为空，递归超前遍历右侧子树) */public=null () { this.left.preOrder )； () /递归地按前序扫描右部分树的if(this.right！=null () { this.right.preOrder )； }中顺序扫描
如果当前节点左边的子节点不为空，递归地中顺序扫描左边的子树
输出当前节点
如果当前节点的右子节点不为空，递归遍历右子树
/*中序遍历如果当前节点左边的子节点不为空，则递归遍历左边的子树输出当前节点如果当前节点右边的子节点不为空，则递归遍历右边的子树*/public void inOrder=null () { this.left.inOrder )； //输出当前节点system.out.println(this )； //递归地将右边的子树按中顺序设为if(this.right！=null () { this.right.inOrder )； }后遍历
如果当前节点左边的子节点不为空，则递归遍历左边的子树
如果当前节点右边的子节点不为空，则递归向后遍历右边的子树
输出当前节点
/*后继遍历如果当前节点的左侧子节点不为空，则递归后继遍历左侧子树如果当前节点的右侧子节点不为空，则递归后继遍历右侧子树当前节点*/public void postoid
stOrder(); } //若右子节点不为空，对右子节点进行后序遍历 if(this.right!=null) { this.right.postOrder(); } //输出当前节点 System.out.println(this); }heroNode源码：
package BinaryTree;/*创建节点表示人物，no是人物的序号，name是人物的姓名left是当前节点指向的左子节点，默认为nullright是当前节点指向的右子节点，默认为null */public class heroNode { private int no; private String name; private heroNode left; private heroNode right; //无需初始化左右子节点，因为创建时并不知道指向哪里 public heroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } //设置左子节点 public void setLeft(heroNode leftNode) { this.left=leftNode; } //设置右子节点 public void setRight(heroNode rightNode) { this.right=rightNode; } @Override public String toString() { return "heroNode{" + "no=" + no + ", name='" + name + ''' + '}'; } /*前序遍历 ①输出当前节点（初始节点均为root节点） ②若左子节点不为空，则对左子树递归进行前序遍历 ③若右子节点不为空，则对右子树递归进行前序遍历 */ public void preOrder() { //输出父节点 System.out.println(this); //递归对左子树进行前序遍历 if(this.left!=null) { this.left.preOrder(); } //递归对右子树进行前序遍历 if(this.right!=null) { this.right.preOrder(); } } /*中序遍历 ①若当前节点的左子节点不为空，则对左子树递归进行中序遍历 ②输出当前节点 ③若当前节点的右子节点不为空，则对右子树递归进行中序遍历 */ public void inOrder() { //递归对左子树进行中序遍历 if(this.left!=null) { this.left.inOrder(); } //输出当前节点 System.out.println(this); //递归对右子树进行中序遍历 if(this.right!=null) { this.right.inOrder(); } } /*后续遍历 ①若当前节点的左子节点不为空，则对左子树递归进行后序遍历 ②若当前节点的右子节点不为空，则对右子树递归进行后序遍历 ③输出当前节点 */ public void postOrder() { //若左子节点不为空，对左子节点进行后序遍历 if(this.left!=null) { this.left.postOrder(); } //若右子节点不为空，对右子节点进行后序遍历 if(this.right!=null) { this.right.postOrder(); } //输出当前节点 System.out.println(this); }} Binarytree实现 package BinaryTree;public class BinaryTree { private heroNode root; public void setRoot(heroNode root) { this.root=root; } //前序遍历 public void preOrder() { if(this.root!=null) this.root.preOrder(); else System.out.println("二叉树为空，无法遍历"); } //中序遍历 public void inOrder() { if(this.root!=null) this.root.inOrder(); else System.out.println("二叉树为空，无法遍历"); } //后序遍历 public void postOrder() { if(this.root!=null) this.root.postOrder(); else System.out.println("二叉树为空，无法遍历"); }} BinaryTreeDemo实现根据该图创建二叉树：
package BinaryTree;public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); heroNode node1=new heroNode(1,"健忘的翅膀"); heroNode node2=new heroNode(2,"wjdkj"); heroNode node3=new heroNode(3,"kndzc"); heroNode node4=new heroNode(4,"ngdxbc"); binaryTree.setRoot(node1); //手动创建二叉树 node1.setLeft(node2); node1.setRight(node3); node3.setRight(node4); //前序遍历 System.out.println("前序遍历:"); binaryTree.preOrder(); //中序遍历 System.out.println("中序遍历:"); binaryTree.inOrder(); //后序遍历 System.out.println("后序遍历:"); binaryTree.postOrder(); }}
运行结果：