@[toc]
一、树的相关概念及表示形式
**定义：**树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。形状很像倒挂的树。
特点：
相关概念【非常重要】
结点的度：一个结点含有子树的个数称为该结点的度。
树的度：一棵树中，所有结点度的最大值称为树的度
叶子结点或终端结点：度为 0 的结点称为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
根结点：一棵树中，没有双亲结点的结点
结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推
树的高度或深度：树中结点的最大层次
【了解】
非终端结点或分支结点：度不为 0 的结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙森林：由 m（m>=0）棵互不相交的树组成的集合称为森林
表示形式
双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法【最常用】等等
class Node { int value; Node firstChild; Node nextBrother;}
复制代码
应用：
互不相交的集合例如：文件管理系统
二、二叉树的相关概念及性质
基本概念及特点
**定义：**一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。（每棵子树又可以看成是由左子树和右子树构成的）
**特点：**1. 二叉树不存在度大于 2 的结点 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。3.根结点没有前驱结点。二叉树是递归定义的，每棵树都是由左子树和右子树组成的，每棵子树也可以看成一棵完整的树。
特殊的二叉树及性质
满二叉树：
二叉树每层的结点数都达到最大值【节点总数是 2^k-1 个】，则这棵二叉树就是满二叉树。
完全二叉树：
对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 0 至 n-1 的结点一一对应时称之为完全二叉树。
满二叉树是一种特殊的完全二叉树。
二叉搜索树（BST）
定义：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值的二叉树叫做二叉搜索树。
二叉搜索树主要支持三个操作：搜索、插入和删除
由于本文主要是基础内容的总结，这个二叉搜索树是文章快完成时加上的知识点，算是拓展也算是拔高，所以解题思路全部都在此版块了，至于代码并没有展开，之后会在做题总结中写。
了解如何在二叉搜索树中进行搜索、插入或删除;
如果目标值等于节点的值，则返回节点；
如果目标值小于节点的值，则继续在左子树中搜索；
如果目标值大于节点的值，则继续在右子树中搜索。
在二叉搜索树中运用递归或迭代的方法，进行搜索、插入和删除操作;
根据节点值与目标节点值的关系，搜索左子树或右子树；
重复步骤 1 直到到达外部节点；
根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。
如果目标节点没有子节点，我们可以直接移除该目标节点。
如果目标节只有一个子节点，我们可以用其子节点作为替换。
如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
了解节点数量、树的高度和操作复杂度之间的关系。
二叉搜索树的有优点是，即便在最坏的情况下，也允许你在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。
二叉树的性质：
若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1)个节点。
若规定只有根结点的二叉树的深度为 1，则深度为 K 的二叉树的最大结点数是(k>=0)，2^k-1
【前两条的性质直接通过等比求和公式和特例解决就可以知道】
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为 2 的非叶结点个数为 n2,则有 n0＝n2＋1 。
【证明：①有 n 个节点的树，有 n-1 边②任意一棵二叉树的节点总数 n=n0+n1+n2 并且每个度为 2 的节点都对应两条边，所以 n-1=n1+2*n2=n0+n1+n2-1==>n0=n2+1】
具有 n 个结点的完全二叉树的深度 k 为 log(n+1)上取整
【随便用两个树实验一下就可以，另外还可以写成 logn+1 向下取整】
对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：
若 i>0，双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点若 2i+1<n，左孩子序号：2i+1，否则无左孩子若 2i+2<n，右孩子序号：2i+2，否则无右孩子
即满足题意的前提下，孩子节点编号为 i，那么双亲结点序号就是(i-1)/2
双亲结点编号为 i，那么左孩子节点序号就是 2i+1,右孩子是 2i+2
因为是偶数个节点，所以一定有一个度为 1 的节点所以
2n=n1+n0+n2=1+n0+n2==>n0=n2+1==>2n=2*n0==>n0=n
奇数个节点的完全二叉树，那么 767=n0+n2=2*n0-1====>n0=768/2=384
log(531+1)=log(534)>log(521)=====>10
三、二叉树的存储、遍历及基本操作实现
二叉树的存储：
存储方式：顺序存储和类似于链表的链式存储
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉【存两个引用】和三叉【存三个引用】表示方式。本节中，多大多数题目都是使用链式存储来解决问题的。
// 孩子表示法 ,目前使用孩子表示法更多class Node { int val; Node left; Node right;}//不存在双向单向的问题，他有左右之分，是有次序的// 孩子双亲表示法 class Node { int val; Node left; Node right; Node parent; }
复制代码
二叉树的遍历 ：
每个二叉树都是由根节点、左子树、右子树组成的，而每棵子树也是这样的定义的，定义是递归的，所以我们在实现遍历操作的时候最好采用递归的方法解决。
遍历定义：沿着某条搜索路线，依次对树中的而每个节点做只做一次访问。
但是在实现操作之前我们先进行一个例子讲解，因为初学者容易对这个顺序理解错误。
层序遍历
1.前序遍历【根节点-->左子树-->右子树】
public void preOrder(TreeNode root){ if(root==null){ return ; } System.out.println(root.val); preOrder(root.left); preOrder(root.right);}
//不直接打印而是存储到一个list表中class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); if(root==null){ return list; } list.add(root.val); List<Integer>leftTree=preorderTraversal(root.left); list.addAll(leftTree); List<Integer> rightTree=preorderTraversal(root.right); list.addAll(rightTree); return list; }}
复制代码
2.中序遍历【左子树-->根节点-->右子树】
public void inOrder(TreeNode root){ if(root==null){ return ; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right);}
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); if(root==null){ return list; } List<Integer>leftTree=inorderTraversal(root.left); list.addAll(leftTree); list.add(root.val); List<Integer> rightTree=inorderTraversal(root.right); list.addAll(rightTree); return list; }}
复制代码
3.后序遍历【左子树-->右子树-->根节点】
public void postOrder(TreeNode root){ if(root==null){ return ; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" ");}
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); if(root==null){ return list; } List<Integer>leftTree=postorderTraversal(root.left); list.addAll(leftTree); List<Integer> rightTree= postorderTraversal(root.right); list.addAll(rightTree); list.add(root.val); return list; }}
复制代码
4.层序遍历
void levelOrder1(TreeNode root){ if(root==null){ return ; } Queue<TreeNode> qu=new LinkedList<>(); qu.offer(root); while(!qu.isEmpty()){ TreeNode cur=qu.poll(); System.out.print(cur.val+" "); if(cur.left!=null){ qu.offer(cur.left); } if(cur.right!=null){ qu.offer(cur.right); } }}
复制代码
确定二叉树的一些小规律
另外我们还可以总结出来一些规律：
只给出一个遍历无法创建一棵二叉树。【可能存在两颗树的某个遍历是一样的】
只给出前序和后序确定不了一棵唯一的二叉树。【前序和后序都是确定根节点的位置，无法确定左右子树的位置，中序遍历确定的是左右子树的位置】
后序遍历最后一个节点一定是根节点，如果有右树，那么倒数第二个节点一定是右树的根；先序遍历的第一个节点一定是根节点。
对于中序遍历，根的左边是左树，右边是右树
对于先序遍历，根的左边是根/左树，右边是右树
四、TreeSet 的介绍及常用方法介绍
二叉树的基本操作
获取树中节点的个数
获取叶子节点的个数
子问题思路-求叶子结点个数
获取第 K 层节点的个数
获取二叉树的高度
检测值为 value 的元素是否存在
层序遍历
判断一棵树是不是完全二叉树
TreeSet 方法源码
二叉树常用操作模拟
public class MyTree { class TreeNode{ public char val; public int val2; public TreeNode left; public TreeNode right;
public TreeNode(char val) { this.val = val; }
public TreeNode(int val2) { this.val2 = val2; } } public TreeNode root; public void preOrder(TreeNode root){ if(root==null){ return ; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } public void inOrder(TreeNode root){ if(root==null){ return ; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } public void postOrder(TreeNode root){ if(root==null){ return ; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); } int size(TreeNode root){//2.递归（递推公式）
if(root==null){ return 0; } return size(root.left)+size(root.right)+1; }
//叶子结点的个数 //叶子结点的定义：左右子树为空算一个 int getLeafNodeCount(TreeNode root){ if(root==null){ return 0; } if(root.left==null&&root.right==null){ return 1; } return getLeafNodeCount(root.left)+getLeafNodeCount(root.right); } // 获取第K层节点的个数 //算一层的依据，左子树和右子树取最大值结果再+1 //左子树和右子树k-1层的个数 int getKLevelNodeCount(TreeNode root,int k){ if(root==null||k<0){ return 0; } if(k==1){ return 1; } return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1); } // 获取二叉树的高度 public int getHeight(TreeNode root){ if(root==null){ return 0; } return Math.max(getHeight(root.left),getHeight(root.right))+1; } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, int val){ if(root==null){ return null; } if(root.val==val){ return root; } TreeNode leftTreeNode=find(root.left,val); if(leftTreeNode!=null){ return leftTreeNode; } TreeNode rightTreeNode=find(root.right,val); if(rightTreeNode!=null){ return rightTreeNode; } return null; } void levelOrder(TreeNode root){ if(root==null){ return ; } Queue<TreeNode> qu=new LinkedList<>(); qu.offer(root); while(!qu.isEmpty()){ TreeNode cur=qu.poll(); System.out.print(cur.val+" "); if(cur.left!=null){ qu.offer(cur.left); } if(cur.right!=null){ qu.offer(cur.right); } } } public boolean isCompleteTree(TreeNode root){ if(root==null){ return true; } Queue<TreeNode> qu=new LinkedList<>(); qu.offer(root); while(!qu.isEmpty()){ List<Integer> tmp=new ArrayList<>(); TreeNode cur=qu.poll(); if(cur==null){ break; } qu.offer(cur.left); qu.offer(cur.right); } //第一个null值的时候出来，然后如果后边队列有还非null的值就不是，后边没有值/全部是null那么就是完全二叉树 while(!qu.isEmpty()){ if(qu.poll()!=null){ return false; } } return true; }}
复制代码
评论