一.概念
一颗二叉树是结点的一个有限集合,该集合:
1.或者为空
2.或者由一个根结点加上两颗别称为左子树和右子树的二叉树组成
从上图可以看出:
1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:任何任意的二叉树都是由以下几种情况复合而成的:
二.两种特殊的二叉树
完全二叉树:从上到下,从左到右依次存放,下图就不是完全二叉树
三.二叉树的性质
翻译:对于任何一颗二叉树,叶子结点的个数,永远比度为2的结点个数多1
完全二叉树对于偶数节点其父节点编号为其编号除以2,奇数节点其父节点编号为(其编号-1)/2
6.在完全二叉树中,如果节点总个数为奇数,则没有度为1的节点,如果节点总个数为偶数,只有一个度为1的节点
四.二叉树的储存
二叉树的存储结构分为:顺序存储和类似于链表的链式存储。
链式存储:
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方法,具体如下:
1.孩子表示法
class Node{
int val; //数据域
Node left; //左孩子的引用,常常代表左孩子为根的整颗左子树
Node right; //右孩子的引用,常常代表右孩子为根的整颗右子树
}
2.孩子双亲表示法
class Node{
int val; //数据域
Node left; //左孩子的引用,常常代表左孩子为根的整颗左子树
Node right; //右孩子的引用,常常代表右孩子为根的整颗右子树
Node parent; //当前节点的根节点
}
五.二叉树的基本操作
1.快速手动创建一个简单的二叉树
package BinaryTree;
import sun.reflect.generics.tree.Tree;
public class BinaryTree {
static class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public TreeNode createTree(){
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A; //返回根节点
}
}
package BinaryTree;
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode ret = binaryTree.createTree();
}
}
2.二叉树的遍历
1.前中后序遍历
- NLR:前序遍历:--访问根节点——>根的左子树——>根的右子树
- LNR:中序遍历:--根的左子树——>根节点——>根的右子树
- LRN:后序遍历:--根的左子树——>根的右子树——>根节点
分析前中后序遍历图解
注:通过前序和后序遍历序列都只能得到根,所以只知道前序和后序遍历序列无法得出二叉树,必须得到中序遍历序列
2.前序遍历具体实现
public void preOrder(TreeNode root){
if (root == null){
return;
}
System.out.print(root.val);
preOrder(root.left);
preOrder(root.right);
}
3.中序遍历具体实现
public void inOder(TreeNode root){
if (root == null){
return;
}
inOder(root.left);
System.out.print(root.val);
inOder(root.right);
}
}
4.后序遍历具体实现
public void postOder(TreeNode root){
if (root == null){
return;
}
inOder(root.left);
inOder(root.right);
System.out.println(root.val);
}
}
5.层序遍历
3.获取树中节点个数
//获取树中节点个数
//1.遍历方法
int size = 0;
public void nodeSize(TreeNode root){
if (root == null){
return;
}
size++;
nodeSize(root.left);
nodeSize(root.right);
}
//2.子方法
//树中节点个数等于左树节点个数加右树节点个数加1
public int nodeSize2(TreeNode root){
if (root == null){
return 0;
}
return nodeSize2(root.left)+nodeSize2(root.right)+1;
}
4.获取叶子节点的个数
//获取叶子节点个数
//1.遍历方法
public int leafSize = 0;
public void getLeafSize(TreeNode root){
if (root == null){
return;
}
if (root.left == null && root.right == null){
leafSize++;
}
getLeafSize(root.left);
getLeafSize(root.right);
}
//2.子方法
//叶子节点个数等于左树叶子节点个数加右树叶子节点个数
public int getLeafSize2(TreeNode root){
if (root == null)return 0;
if (root.left ==null && root.right == null)return 1;
return getLeafSize2(root.left)+getLeafSize2(root.right);
}
5.获取第k层节点个数
//获取第k层节点个数
public int getKlevelNodeCount(TreeNode root,int k){
if (root == null)return 0;
if (k==1){
return 1;
}
return getKlevelNodeCount(root.left, k-1) + getKlevelNodeCount(root.right, k-1);
}
6.获取二叉树的高度
//获取二叉树高度
public int getHigh(TreeNode root) {
if (root == null) return 0;
int leftHight = getHigh(root.left);
int rightHight = getHigh(root.right);
return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
7.检测值为value的元素是否存在
//检测值为value的元素是否存在
public boolean find(TreeNode root, char key){
if (root == null){
return false;
}
if (root.val == key){
return true;
}
boolean leftval = find(root.left, key);
if (leftval == true){
return true;
}
boolean rightval = find(root.left, key);
if (rightval == true){
return true;
}
return false;
}
8.层序遍历
public void levelOrder(TreeNode root){
Queue<TreeNode>q = new LinkedList<>();
if (root == null){
return;
}
q.offer(root);
while(!q.isEmpty()){
TreeNode cur = q.poll();
if (cur.left != null){
q.offer(cur.left);
}
if (cur.right != null){
q.offer(cur.right);
}
System.out.print(cur.val);
}
}
9.判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root){
Queue<TreeNode>q = new LinkedList<>();
if (root == null){
return true;
}
q.offer(root);
while(!q.isEmpty()){
TreeNode cur = q.poll();
if (cur != null){
q.offer(cur.left);
q.offer(cur.right);
}else {
break;
}
}
while(!q.isEmpty()){
if (q.poll() != null){
return false;
}
}
return true;
}