二叉树（一）

📑前言

本文主要是【数据结构】——二叉树使用的文章，如果有什么需要改进的地方还请大佬指出??

🎬作者简介：大家好，我是听风与他🥇
??博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

• 以如下二叉树为例

1.二叉树的创建及打印

package 二叉树;

import java.util.Scanner;

public class Main {

	static 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;
		}
	}
	TreeNode root;//整顿二叉树的根
	public Main() {
		root=null;//开始的时候根结点为空
	}
	Scanner sc = new Scanner(System.in);
	//创建二叉树，递归思想，根，递归左子树，递归右子树，用0表示没有后继的点
	public TreeNode createBinaryTree() {
		TreeNode t;//当前的根结点
		int x=sc.nextInt();//从键盘读入当前结点的数值，如果是0表示null结点
		if(x==0) {t=null;}
		else {
			t=new TreeNode();
			t.data=x;
			t.left=createBinaryTree();
			t.right=createBinaryTree();
		}
		
		return t;
	}
	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(")");
			}
		}
	}
	/*
1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main a = new Main();
		a.root=a.createBinaryTree();
		a.printTree(a.root);
	}

}

打印结果:

//输入:1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
1(2(4,5),3(6,7)) 

2.二叉树层次前中后序遍历

package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

import 二叉树.Main.TreeNode;

public class Order {
	/*
1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main a = new Main();
		TreeNode root =	a.createBinaryTree();
		preOrder(root);
		System.out.println();
		midOrder(root);
		System.out.println();
		postOrder(root);
		System.out.println();
		levelOrder(root);
	}
	
	public static void preOrder(TreeNode root) {
		if (root!=null) {
			System.out.print(root.data+" ");
			preOrder(root.left);
			preOrder(root.right);
		}
	}
	public static void midOrder(TreeNode root) {
		if (root!=null) {
			midOrder(root.left);
			System.out.print(root.data+" ");
			midOrder(root.right);
		}
	}
	public static void postOrder(TreeNode root) {
		if (root!=null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print(root.data+" ");
		}
	}
	
	public static void levelOrder(TreeNode t) {
		Queue<TreeNode> q = new LinkedList<>();
		if(t==null) return;
		q.offer(t);//根入列
		while(!q.isEmpty()) {
			TreeNode head = q.poll();//弹出列头
			System.out.print(head.data+" ");
			if(head.left!=null)
			q.offer(head.left);
			if(head.right!=null)
			q.offer(head.right);
		}
	}
}

打印结果:

//输入:1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
1 2 4 5 3 6 7 
4 2 5 1 6 3 7 
4 5 2 6 7 3 1 
1 2 3 4 5 6 7 

3.二叉树深度和叶子结点个数

package 二叉树;

import 二叉树.Main.TreeNode;

public class 二叉树深度及叶子节点个数 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main a = new Main();
		TreeNode root =	a.createBinaryTree();
		System.out.println(treeDepth(root));
		System.out.println(treeLeaf(root));
	}
	
	public static int treeDepth(TreeNode root) {
		if (root==null) {
			return 0;
		}
		return Math.max(treeDepth(root.left), treeDepth(root.right))+1;
	}
	
	public static int treeLeaf(TreeNode root) {
		if (root==null) {
			return 0;
		}
		if(root.left==null&&root.right==null) return 1;
		else return treeLeaf(root.left)+treeLeaf(root.right);
	}
	
}

📑文章末尾