二叉树常用方法(一)
树节点
public class Node {
public int data;
public Node leftNode;
public Node rightNode;
public Node(){
this.data = -1;
}
public Node(int data){
this.data = data;
this.leftNode = null;
this.rightNode = null;
}
}
二叉树方法
二叉树
public class Tree {
private Node root;
public Tree(){
root = null;
}
}
前序数组创建二叉树
public int creatTreeByPre(Node node, int[] treeNodes, int n){
//如果提供空节点,那么需要创建根节点并保持到root中
if (node == null) {
root = new Node();
node = root;
}
//给当前节点赋值
node.data = treeNodes[n];
//记录左子树和右子树放回的位置
int left =0,right=0;
//前序
//如果下一个节点是空的话(-1),那么直接跳过,否则创建节点,向下递归
if(treeNodes[n+1] != -1){
node.leftNode = new Node();
left = creatTreeByPre(node.leftNode,treeNodes,n+1);
}else {
//下一个是空,那么再下一个
left = n+1+1;
}
//同理
if (treeNodes[left]!=-1){
node.rightNode = new Node();
right = creatTreeByPre(node.rightNode,treeNodes,left);
}else {
right = left+1;
}
return right;
}
前序遍历
public void printNodeByPre(Node root){
if (root==null) return;
System.out.print(root.data+"\t");
printNodeByPre(root.leftNode);
printNodeByPre(root.rightNode);
}
求树最大深度
public int maxDeath(Node node){
if (node == null) return 0;
int left = maxDeath(node.leftNode);
int right = maxDeath(node.rightNode);
return Math.max(left,right)+1;
}
求二叉树节点个数
public int getNodenum(Node root){
if (root == null) return 0;
int left = getNodenum(root.leftNode);
int right = getNodenum(root.rightNode);
return left+right+1;
}
求树最小深度
public int minDeath(Node root){
if (root == null) return 0;
int left = minDeath(root.leftNode);
int right = minDeath(root.rightNode);
return Math.min(left,right)+1;
}
求左右树节点个数(不包含根节点)
public int getNumOfChildNode(Node root){
if (root == null) return 0;
int left = getNumOfChildNode(root.leftNode);
int right = getNumOfChildNode(root.rightNode);
return left+right;
}
判断是否为平衡二叉树
//平衡树条件:一颗树没一层节点的左子树和右子树的最大层数不能相差超过一
public boolean isbalancedTree(Node root){
//-1表示破坏平衡,
return getAbsDeath(root,1)!=-1;
}
//当树中出现左右子树的深度差大于n时放回-1,否则返回最大深度
public int getAbsDeath(Node root,int n){
//空返回0
if (root == null) return 0;
//获取左右子树的深度
int left = getAbsDeath(root.leftNode,n);
int right = getAbsDeath(root.rightNode,n);
//左右深度相差>2,破坏相对条件,返回-1,左右子树哪一边破开相对条件也返回-1
if (left ==-1 || right==-1 || Math.abs(left-right)>n) return -1;
//相对条件没被破坏,继续统计层数
return Math.max(left,right)+1;
}
判断是否为完美树
public boolean isCompleteTree(Node root){
if (root == null) return false;
//判断是否为完美二叉树,需要一层一层从左往右扫描,所以用到队列,先进先出顶多特点
Queue<Node> queue = new LinkedList<>();
//当出现只有一个子节点或没有子节点的节点时,后面的所以节点必须没有子节点,
//否则该二叉树不是完美二叉树。有没子节点是判断的分界,判断不同。
boolean hasChild = true;
while (!queue.isEmpty()){
//有子节点的-----------------------
if (hasChild){
if (root.leftNode == null &&root.rightNode == null)
hasChild = false;
if (root.leftNode != null && root.rightNode == null){
hasChild = false;
queue.add(root.leftNode);
}
if (root.leftNode == null && root.rightNode != null){
return false;
}
if (root.leftNode != null && root.rightNode !=null){
queue.add(root.leftNode);
queue.add(root.rightNode);
}
//没子节点的-------------------------
}else {
if (root.leftNode != null || root.rightNode != null)
return false;
}
}
return true;
}
判断两棵树是否相等
public boolean isSameTree(Node root,Node otherroot){
//先判断节点是否都存在
if (otherroot == null && root == null) return true;
else if (otherroot != null && root == null) return false;
else if (otherroot == null && root != null) return false;
//判断数据和左右子树的结果
boolean mainresult = (otherroot.data == root.data);
boolean leftresult = isSameTree(root.leftNode,otherroot.leftNode);
boolean rightresult = isSameTree(root.rightNode,otherroot.rightNode);
//结果三个结果做综合判断
return mainresult && leftresult && rightresult;
}