数据结构和算法-07平衡二叉树-01

树的发展历程

来认识我们的树结构

平衡二叉树

如果得知二叉树是否平衡，直接的方法是左右子树的高度值不大于1。我们在节点中添加height指标用来检验二叉树的高度差。

规范：如果为空，高度 0。默认产生一个节点高度为： 1

tips： 高度为虚拟高度（类似于层）

添加height属性

定义height属性，默认高度为1，即height=1为根节点。

package com.ffyc.tree.node;/*** 树的节点*/
public class TreeNode {public int val;public TreeNode left;public TreeNode right;public int height;public TreeNode() {}public TreeNode(int val) {this.val = val;this.height = 1; //默认高度为1}public TreeNode(int val, TreeNode left, TreeNode right, int height) {this.val = val;this.left = left;this.right = right;this.height = height;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}@Overridepublic String toString() {return "TreeNode{" +"val=" + val +", left=" + left +", right=" + right +", height=" + height +'}';}
}

获取height

public int getHeight(TreeNode curr) {if (curr == null) return 0;return curr.height;
}

更新insert

public TreeNode insert(TreeNode curr, int val) {if (curr == null) {size++;return new TreeNode(val);}if (val < curr.val) { //比左节点小curr.left = insert(curr.left, val);} else {curr.right = insert(curr.right, val);}curr.height = 1 + Math.max(getHeight(curr.left), getHeight(curr.right));return curr;
}

计算负载因子

public int balanceFactor(TreeNode curr) {if (curr == null) return 0;return Math.abs(getHeight(curr.left) - getHeight(curr.right));
}

如何判断一棵树是否为BST树

public boolean isBST(TreeNode curr) {if (curr == null) return true;List<Integer> list = new ArrayList<>();inOrder(curr, list);for (int i = 1; i < list.size(); i++) {if (list.get(i) < list.get(i - 1)) {return false;}}return true;
}

中序遍历

private  void inOrder(TreeNode root, List<Integer> list) {if (root == null) {return;}//System.out.print(root.val + "\t");inOrder(root.left, list);list.add(root.val);inOrder(root.right, list);
}

测试

int[] arr = {53, 51, 11, 23, 47, 62, 41, 9, 85, 19, 24, 13, 17, 50};
TreeNode  root = new TreeNode(arr[0]);
Bst bst= new Bst();
for(int i=1;i<arr.length;i++){root = bst.insert(root,arr[i]);}
bst.inOrder(root);
new TreePrint<Integer>().print(root);
System.out.println(bst.getHeight(root.left));
System.out.println(bst.balanceFactor(root.left));
System.out.println(bst.isBST(root));