树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点。
如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2’n-1 , n为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
二、二叉树遍历的方法 1、递归遍历前序遍历
//前序遍历---先头，左，右
public void preorder(ThreeNode threeNode) {
if (threeNode != null ) {
System.out.println(threeNode); //头
if (threeNode.left != null) {
threeNode.left.preorder(threeNode.left); //左
}
if (threeNode.right != null) {
threeNode.right.preorder(threeNode.right); //右
}
}
}
中序遍历
//中序遍历---先左，头，右
public void middleOrder(ThreeNode threeNode) {
if (threeNode != null ) {
if (threeNode.left != null) {
threeNode.left.middleOrder(threeNode.left); //左
}
System.out.println(threeNode);
if (threeNode.right != null) {
threeNode.right.middleOrder(threeNode.right); //右
}
}
}
后序遍历
//后序遍历---先左右头
public void postOrder(ThreeNode threeNode) {
if (threeNode != null ) {
if (threeNode.left != null) {
threeNode.left.postOrder(threeNode.left); //左
}
if (threeNode.right != null) {
threeNode.right.postOrder(threeNode.right); //右
}
System.out.println(threeNode);
}
}
先序遍历
先准备一个栈
将头结点压入栈
每次从栈弹出一个节点cur----处理cur
先右在左的将节点压入栈----周而复始的操作
public void noPreorder(ThreeNode threeNode){
if (threeNode !=null){
Stack stack = new Stack<>();
stack.add(threeNode);
while (!stack.isEmpty()){
threeNode = stack.pop(); //没弹出一个节点，都要判断一个有没有孩子
System.out.println(threeNode); //弹出栈
if (threeNode.getRight() !=null){
stack.push(threeNode.getRight()); //将左孩子压入栈
}
if (threeNode.getLeft() !=null){
stack.push(threeNode.getLeft()); //将右孩子压入栈
}
}
System.out.println();
}
}
中序遍历
先准备一个栈
先将整棵树的左边全压入栈
从栈中弹出一个元素并判断是否有右边—有的话将指针指向弹出的右边—在判断是否有右边和左边—没有的话弹出–周而复始
public void noMiddleOrder(ThreeNode threeNode) {
if (threeNode != null) {
Stack stack = new Stack<>();
//自己写的-------------------------------
// while (threeNode != null) {
// stack.push(threeNode);
// threeNode = threeNode.getLeft();
// }
// while (!stack.isEmpty()) {
// threeNode = stack.pop();
// System.out.println(threeNode);
// if (threeNode.getRight() != null) {
// threeNode = threeNode.getRight();
// while (threeNode != null) {
// stack.push(threeNode);
// threeNode = threeNode.getLeft();
// }
// }
// }
// System.out.println();
// }
// }
//网上的方法------------
while (!stack.isEmpty() || threeNode !=null){
if (threeNode !=null){
stack.push(threeNode);
threeNode = threeNode.getLeft();
}else {
threeNode = stack.pop();
System.out.println(threeNode);
threeNode = threeNode.getRight();
}
}
System.out.println();
}
}
后序遍历
先准备两个栈
入第一个栈的出栈顺序是先—头，右，左----所以压入第一个栈的顺序是–先：头，左，右
第二个的入栈顺序是：头，右，左----这样出栈的顺序相反—左右头–>对应的是后序
public void noPostOrder(ThreeNode threeNode) {
if (threeNode !=null) {
Stack stack = new Stack<>(); //放入栈---弹出顺序为---头，右，左
Stack stack1 = new Stack<>(); //收集栈---收集栈刚好相反---左，右，头
stack.add(threeNode);
while (!stack.isEmpty()){
threeNode = stack.pop();
stack1.push(threeNode);
if (threeNode.getLeft() !=null){
stack.push(threeNode.getLeft());
}
if (threeNode.getRight() !=null){
stack.push(threeNode.getRight());
}
}
while (!stack1.isEmpty()){
System.out.println(stack1.pop());
}
System.out.println();
}
}
4、宽度优先遍历
先准备一个队列队列是先进先出的先放—头、左、右
//宽度优先遍历
public void witchOrder(ThreeNode threeNode){
if (threeNode ==null){
return ;
}
Queue queue = new linkedList<>();
queue.add(threeNode);
while (!queue.isEmpty()){
ThreeNode cur = queue.poll(); //弹出并捕捉
System.out.println(cur); //打印
if (cur.getLeft() !=null){
queue.add(cur.getLeft());
}
if (cur.getRight() != null){
queue.add(cur.getRight());
}
}
System.out.println();
}
三、二叉树的查找
-
1、先序遍历查找//先序遍历查找
//先找头--然后找左边---最后找右边
public ThreeNode preorderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
if (threeNode.num == num1) {
return threeNode;
}
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
threeNode2 = threeNode.left.preorderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.right != null){
threeNode2 = threeNode.left.preorderSearch(threeNode.right, num1);
}
return threeNode2;
}
2、中序查找
//中序查找
//先左---头---右
public ThreeNode middleOrderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
ThreeNode threeNode2 = null;
if (threeNode.left !=null) {
threeNode2 = threeNode.left.middleOrderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.num == num1){
return threeNode;
}
if (threeNode.right != null){
threeNode2 = threeNode.right.preorderSearch(threeNode.right, num1);
}
return threeNode2;
}
3、后序查找
//后序查找
//先--左右--再头
public ThreeNode postOrderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
threeNode2 = threeNode.left.postOrderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.right != null) {
threeNode2 = threeNode.right.postOrderSearch(threeNode.right, num1);
}
if (threeNode.num == num1) {
return threeNode;
}
return threeNode2;
}
四、二叉树的删除
//删除树的结点
public ThreeNode deleteNode(ThreeNode threeNode,int num1) {
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
if (threeNode.left.num == num1) { //判断左子是不是要删除的
threeNode2 = threeNode.left;
threeNode.left = null;
return threeNode;
}
}
if (threeNode.right != null) {
if (threeNode.right.num == num1) { //判断右子是不是要删除的
threeNode2 = threeNode.right;
threeNode.right = null;
return threeNode;
}
}
if (threeNode2 == null) { //一直不是时threeNode2 就会是一直为null---然后进行递归删除
if (threeNode.left != null) {
threeNode.left.deleteNode(threeNode.left, num1);
}
if (threeNode2 == null) {
if (threeNode.right != null) {
threeNode.right.deleteNode(threeNode.right, num1);
}
}
}
return threeNode;
}
全部代码（遍历，查找，删除）
public class BinaryTreeTest {
public static void main(String[] args) {
//ThreeNode root = new ThreeNode();
//root.create(root);
ThreeNode root = new ThreeNode(1, "zzj");
ThreeNode threeNode2 = new ThreeNode(2, "lmg");
ThreeNode threeNode3 = new ThreeNode(3, "xxl");
ThreeNode threeNode4 = new ThreeNode(4, "dyf");
ThreeNode threeNode5 = new ThreeNode(5, "zhh");
ThreeNode threeNode6 = new ThreeNode(6, "jcd");
ThreeNode threeNode7 = new ThreeNode(7, "lwh");
//手动生成数---后面使用递归生成
root.setLeft(threeNode2);
root.setRight(threeNode3);
threeNode2.setLeft(threeNode4);
threeNode2.setRight(threeNode5);
threeNode3.setLeft(threeNode6);
threeNode3.setRight(threeNode7);
//遍历树
System.out.println("前序");
root.preorder(root);
System.out.println("--------------------------------上递归下非递归");
root.noPreorder(root);
System.out.println("中序");
root.middleOrder(root);
System.out.println("--------------------------------上递归下非递归");
root.noMiddleOrder(root);
System.out.println("后序");
root.postOrder(root);
System.out.println("--------------------------------上递归下非递归");
root.noPostOrder(root);
System.out.println("宽度优先遍历");
root.witchOrder(root);
System.out.println("先序查找");
System.out.println(root.preorderSearch(root, 2));
System.out.println("中序查找");
System.out.println(root.middleOrderSearch(root, 4));
System.out.println("后序查找");
System.out.println(root.postOrderSearch(root, 5));
System.out.println("===============================================================");
root.witchOrder(root);
root.deleteNode(root, 6);
System.out.println("===============================================================");
root.witchOrder(root);
}
}
//创建二叉树
//先创建颗树的节点
class ThreeNode{
private int num;
private String name;
private ThreeNode left; //构造器不赋值---初值为null
private ThreeNode right;
//构造器
public ThreeNode() {
}
public ThreeNode(int num, String name) {
this.num = num;
this.name = name;
}
//提供get set方法
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public ThreeNode getLeft() {
return left;
}
public void setLeft(ThreeNode left) {
this.left = left;
}
public ThreeNode getRight() {
return right;
}
public void setRight(ThreeNode right) {
this.right = right;
}
//递归建立二叉树
public ThreeNode create(ThreeNode threeNode){
Scanner scanner = new Scanner(System.in);
int num1 = scanner.nextInt();
String name1 = scanner.nextLine();
if (num !=0 && !name.equals("")) {
threeNode.num = num1;
threeNode.name = name1;
//左枝，右枝
threeNode.left = create(threeNode.left);
threeNode.right = create(threeNode.right);
}else{
threeNode = null;
}
return threeNode;
}
//前序遍历---先头，左，右
public void preorder(ThreeNode threeNode) {
if (threeNode != null ) {
System.out.println(threeNode); //头
if (threeNode.left != null) {
threeNode.left.preorder(threeNode.left); //左
}
if (threeNode.right != null) {
threeNode.right.preorder(threeNode.right); //右
}
}
}
//中序遍历---先左，头，右
public void middleOrder(ThreeNode threeNode) {
if (threeNode != null ) {
if (threeNode.left != null) {
threeNode.left.middleOrder(threeNode.left); //左
}
System.out.println(threeNode);
if (threeNode.right != null) {
threeNode.right.middleOrder(threeNode.right); //右
}
}
}
//后序遍历---先左右头
public void postOrder(ThreeNode threeNode) {
if (threeNode != null ) {
if (threeNode.left != null) {
threeNode.left.postOrder(threeNode.left); //左
}
if (threeNode.right != null) {
threeNode.right.postOrder(threeNode.right); //右
}
System.out.println(threeNode);
}
}
//无递归遍历----------------------------------------------------------
//1. 先序遍历
// - 先准备一个栈
// - 将头结点压入栈
// - 每次从栈弹出一个节点cur----处理cur
// - 先右在左的将节点压入栈----周而复始的操作
public void noPreorder(ThreeNode threeNode){
if (threeNode !=null){
Stack stack = new Stack<>();
stack.add(threeNode);
while (!stack.isEmpty()){
threeNode = stack.pop(); //没弹出一个节点，都要判断一个有没有孩子
System.out.println(threeNode); //弹出栈
if (threeNode.getRight() !=null){
stack.push(threeNode.getRight()); //将左孩子压入栈
}
if (threeNode.getLeft() !=null){
stack.push(threeNode.getLeft()); //将右孩子压入栈
}
}
System.out.println();
}
}
//中序非递归
//- 先准备一个栈
//- 先将整棵树的左边全压入栈
//- 从栈中弹出一个元素并判断是否有右边---有的话将指针指向弹出的右边---在判断是否有右边和左边---没有的话弹出--周而复始
public void noMiddleOrder(ThreeNode threeNode) {
if (threeNode != null) {
Stack stack = new Stack<>();
//自己写的-------------------------------
// while (threeNode != null) {
// stack.push(threeNode);
// threeNode = threeNode.getLeft();
// }
// while (!stack.isEmpty()) {
// threeNode = stack.pop();
// System.out.println(threeNode);
// if (threeNode.getRight() != null) {
// threeNode = threeNode.getRight();
// while (threeNode != null) {
// stack.push(threeNode);
// threeNode = threeNode.getLeft();
// }
// }
// }
// System.out.println();
// }
// }
//网上的方法------------
while (!stack.isEmpty() || threeNode !=null){
if (threeNode !=null){
stack.push(threeNode);
threeNode = threeNode.getLeft();
}else {
threeNode = stack.pop();
System.out.println(threeNode);
threeNode = threeNode.getRight();
}
}
System.out.println();
}
}
//后序非递归
//- 先准备两个栈
//- 入第一个栈的出栈顺序是先---头，右，左----所以压入第一个栈的顺序是--先：头，左，右
//- 第二个的入栈顺序是：头，右，左----这样出栈的顺序相反---左右头-->对应的是后序
public void noPostOrder(ThreeNode threeNode) {
if (threeNode !=null) {
Stack stack = new Stack<>(); //放入栈---弹出顺序为---头，右，左
Stack stack1 = new Stack<>(); //收集栈---收集栈刚好相反---左，右，头
stack.add(threeNode);
while (!stack.isEmpty()){
threeNode = stack.pop();
stack1.push(threeNode);
if (threeNode.getLeft() !=null){
stack.push(threeNode.getLeft());
}
if (threeNode.getRight() !=null){
stack.push(threeNode.getRight());
}
}
while (!stack1.isEmpty()){
System.out.println(stack1.pop());
}
System.out.println();
}
}
//宽度优先遍历
public void witchOrder(ThreeNode threeNode){
if (threeNode ==null){
return ;
}
Queue queue = new linkedList<>();
queue.add(threeNode);
while (!queue.isEmpty()){
ThreeNode cur = queue.poll(); //弹出并捕捉
System.out.println(cur); //打印
if (cur.getLeft() !=null){
queue.add(cur.getLeft());
}
if (cur.getRight() != null){
queue.add(cur.getRight());
}
}
System.out.println();
}
//先序遍历查找
//先找头--然后找左边---最后找右边
public ThreeNode preorderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
if (threeNode.num == num1) {
return threeNode;
}
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
threeNode2 = threeNode.left.preorderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.right != null){
threeNode2 = threeNode.left.preorderSearch(threeNode.right, num1);
}
return threeNode2;
}
//中序查找
//先左---头---右
public ThreeNode middleOrderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
ThreeNode threeNode2 = null;
if (threeNode.left !=null) {
threeNode2 = threeNode.left.middleOrderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.num == num1){
return threeNode;
}
if (threeNode.right != null){
threeNode2 = threeNode.right.preorderSearch(threeNode.right, num1);
}
return threeNode2;
}
//后序查找
//先--左右--再头
public ThreeNode postOrderSearch(ThreeNode threeNode,int num1) {
if (threeNode ==null) {
return null;
}
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
threeNode2 = threeNode.left.postOrderSearch(threeNode.left, num1);
}
if (threeNode2 !=null) {
return threeNode2;
}
if (threeNode.right != null) {
threeNode2 = threeNode.right.postOrderSearch(threeNode.right, num1);
}
if (threeNode.num == num1) {
return threeNode;
}
return threeNode2;
}
//删除树的结点
public ThreeNode deleteNode(ThreeNode threeNode,int num1) {
ThreeNode threeNode2 = null;
if (threeNode.left != null) {
if (threeNode.left.num == num1) { //判断左子是不是要删除的
threeNode2 = threeNode.left;
threeNode.left = null;
return threeNode;
}
}
if (threeNode.right != null) {
if (threeNode.right.num == num1) { //判断右子是不是要删除的
threeNode2 = threeNode.right;
threeNode.right = null;
return threeNode;
}
}
if (threeNode2 == null) { //一直不是时threeNode2 就会是一直为null---然后进行递归删除
if (threeNode.left != null) {
threeNode.left.deleteNode(threeNode.left, num1);
}
if (threeNode2 == null) {
if (threeNode.right != null) {
threeNode.right.deleteNode(threeNode.right, num1);
}
}
}
return threeNode;
}
@Override
public String toString() {
return "ThreeNode{" +
"num=" + num +
", name='" + name + ''' +
'}';
}
}
