目录
树形结构
一棵树是由若干个不相交的子树组成的
树形结构中，子树之间不能有交集，否则就不是树形结构
子树是不相交的
除了根结点外，每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边。
树中的概念
结点的度 ：一个结点含有子树的个数称为该结点的度 树的度 ：一棵树中，所有结点度的最大值称为树的度 叶子结点或终端结点 ：度为 0 的结点称为叶结点 双亲结点或父结点 ：若一个结点含有子结点，则这个结点称为其子结点的父结点 孩子结点或子结点 ：一个结点含有的子树的根结点称为该结点的子结点 根结点 ：一棵树中，没有双亲结点的结点 结点的层次 ：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推 树的高度或深度 ：树中结点的最大层次 树的以下概念只需了解，在看书时只要知道是什么意思即可： 非终端结点或分支结点 ：度不为 0 的结点 兄弟结点 ：具有相同父结点的结点互称为兄弟结点 堂兄弟结点 ：双亲在同一层的结点互为堂兄弟 结点的祖先 ：从根到该结点所经分支上的所有结点 子孙 ：以某结点为根的子树中任一结点都称为该结点的子孙 森林 ：由 m （ m>=0 ）棵互不相交的树组成的集合称为森林树的表示方法
孩子双亲表示法 class Node { int value ; // 树中存储的数据 Node firstChild ; // 第一个孩子引用 Node nextBrother ; // 下一个兄弟引用，同深度的兄弟 }二叉树
一棵二叉树是结点的一个有限集合，该集合： 1. 或者为空 2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。
从上图可以看出：
1.
二叉树不存在度大于
2
的结点
2.
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
一颗树如果是二叉树，那么他每棵树都是二叉树
每个节点度<=2
二叉树都是由以下几种情况复合而成
1.
满二叉树
:
一棵二叉树，如果
每层的结点数都达到最大值，则这棵二叉树就是满二叉树
。也就是说，
如果一棵
二叉树的层数为
K
，且结点总数是
节点编号：
从上到下，从左到右，依次存放。
二叉树的重要性质
二叉树的性质 1. 若规定 根结点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有
二叉树的存储
// 孩子表示法 class Node { int val ; // 数据域 Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val ; // 数据域 Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树 Node parent ; // 当前节点的根节点 }遍历
指的是沿着某条路线遍历
前序遍历
前序是指根在前
先根，再左子树，再右子树
当左子树遍历完时，返回时遍历右子树，直到遍历到根
中序遍历
后续遍历
层序遍历
从上到下，从左到右依次遍历
创建二叉树
二叉树的遍历
public class BinaryTree {
static class TreeNode{
//孩子表示法
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
//public TreeNode root;
//创建一棵二叉树，创建成功后，返回根节点
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;
}
//前序遍历
void preOrder(TreeNode root){
if (root==null){
return;
}
System.out.println(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
//中序遍历
void inOrder(TreeNode root){
if (root==null){
return;
}
preOrder(root.left);
System.out.println(root.val+" ");
preOrder(root.right);
}
//后续遍历
void postOrder(TreeNode root){
if (root==null){
return;
}
preOrder(root.left);
preOrder(root.right);
System.out.println(root.val+" ");
}
//把前序遍历的结果储存到list当中
List<Integer> ret=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root){
if (root==null){
return null;
}
ret.add(root.val);
preOrder(root.left);
preOrder(root.right);
return ret;
}
}获取树中节点个数
前序遍历还是中序遍历，只要遍历到节点就让计数器++
//获取树中节点的个数
public int nodeSize;
int size(TreeNode root){
if (root==null){
return 0;
}
nodeSize++;
size(root.left);
size(root.right);
return nodeSize;
}
int size2(TreeNode root){
if (root==null){
return 0;
}
return size2(root.left)+size2(root.right)+1;
}获取叶子节点的个数
//获取叶子节点个数
//不用递归
public int leafSize;
int getLeafNodeCount1(TreeNode root){
if (root==null){
return 0;
}
if (root.left==null&&root.right==null){
leafSize++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
return leafSize;
}
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层节点个数
// 获取第K层节点的个数
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);
}获取二叉树的高度
左子树的高度，与右子树的高度的最大值加1
// 获取二叉树的高度
int getHeight(TreeNode root){
if (root==null){
return 0;
}
int leftHeight=getHeight(root.left);
int rightHeight=getHeight(root.right);
return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}检测val元素是否存在
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, int val) {
if (root==null){
return null;
}
if (root.val==val){
return root;
}
TreeNode ret1=find(root.left,val);
if (ret1!=null){
return ret1;
}
TreeNode ret2=find(root.right,val);
if (ret2!=null){
return ret2;
}
return null;
}二叉树相关题目
检查两棵树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if ((p == null && q != null) || (p != null && q == null)) {
return false;
}
//上述代码走完之后，要么两个都为空，要么两个都不为空
if (p == null && q == null) {
return true;
}
//代码走到这里 两个都不为空
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}另一棵树的子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root==null||subRoot==null){
return false;
}
//1、是不是根节点相同
if (isSameTree(root,subRoot)){
return true;
}
//2、判断是不是root左子树
if (isSubtree(root.left,subRoot)){
return true;
}
//3、右子树
if (isSubtree(root.right,subRoot)){
return true;
}
//4、返回
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if ((p == null && q != null) || (p != null && q == null)) {
return false;
}
//上述代码走完之后，要么两个都为空，要么两个都不为空
if (p == null && q == null) {
return true;
}
//代码走到这里 两个都不为空
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}反转二叉树
public TreeNode invertTree(TreeNode root) {
if (root==null){
return null;
}
if (root.left==null&&root.right==null){
return root;
}
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}