Java数据结构（二叉树）
·
目录
1、什么是二叉树
二叉树（Binary Tree） 是一种非线性的数据结构，由节点组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树可以为空（没有节点），也可以是一个根节点加上两个互不相交的左子树和右子树。如图所示：
满二叉树和完全二叉树是两种特殊的二叉树结构。
满二叉树：所有层都填满节点的二叉树，即每个节点要么是叶子节点，要么有两个子节点。
完全二叉树：除了最后一层外，其他所有层都被完全填满，并且最后一层的节点全部靠左排列。
2、二叉树的性质
1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有(i>0)个结点
2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全二叉树的深度k为上取整
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有： 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点 若2i+1
2.1.二叉树的存储
二叉树的存储结构分为：顺序存储和类似于链表的链式存储，本章中主要讲链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：
public class binaryTree {
public 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;
}3.二叉树的遍历
二叉树的遍历分为深度优先遍历和广度优先遍历：
深度优先遍历分为前序遍历（遍历顺序：root -> left -> right），中序遍历，后序遍历。了解一个遍历其他两个就解决了，可以用递归的思想去理解遍历；
广度优先遍历分为层序遍历(从上向下，逐层遍历）。
了解这几个遍历才可以完成接下来的二叉树的基本操作。
前序遍历（递归）：
public void preOrder(TreeNode root) {
//当左子树为空时return；
if (root == null) {
return;
}
System.out.print(root.val + "");
preOrder(root.left);
preOrder(root.right);
}非递归：
public List<Character> preTraversal(TreeNode root) {
List<Character> list = new ArrayList<>();
if (root == null) {
return list;
}
TreeNode curr = root;
//用栈的方法实现非递归
Stack<TreeNode> stack = new Stack<>();
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
//访问一个结点入栈并入队列；
stack.push(curr);
list.add(curr.val);
curr = curr.left;
}
//当该结点左子树为空时，出栈去到右子树
curr = stack.pop();
curr = curr.right;
}
return list;
}层序遍历：
pubilc void levelOrder(TreeNode root) {
//从上而下遍历先进先出，用队列实现
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
System.out.print(curr.val);
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}
}4.二叉树的基本操作
学会二叉树的基本操作后就可以熟练的掌握。
获取树中节点的个数，通过子问题思想图解决，二叉树的结点个数就是左子树的个数加上右子树的个树加上根结点。通过递归去实现：
public int size(TreeNode root) {
if (root == null) {
return 0;
}
return size(root.left) + size(root.right) + 1;
}获取叶子节点的个数，当左为null与右为null时为叶子结点：
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层的结点,从根结点出发到第k层相当于递归了k-1层；
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);
}获取二叉树的高度，二叉树的高度等于左子树和右子树最大的高度加1：
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}检测值为value的元素是否存在，找到该元素后变直接向上传递
public TreeNode find(TreeNode root, char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode leftT = find(root.left, val);
if (leftT != null) {
return leftT;
}
TreeNode rightT = find(root.right, val);
if (rightT != null) {
return rightT;
}
return null;
}判断一棵树是不是平衡二叉树On平方时间复杂度情况下，要知道一棵树是不是平衡二叉树就需要知道二叉树的高度，所以可以直接调用上面求二叉树高度的方法
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeinght = getHeight(root.left);
int rightHeinght = getHeight(root.right);
//绝对值的判断也可以用if语句放在return前面
return Math.abs(leftHeinght - rightHeinght) < 2 && isBalanced(root.left) && isBalanced(root.right);
}完全二叉树，树结点左边有树右边可有可无，但右边有左边没有的话就不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
if (root == null){
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
if(curr == null){
break;
}
queue.offer(curr.left);
queue.offer(curr.right);
}
while (!queue.isEmpty()) {
TreeNode curN = queue.poll();
if(curN != null){
return false;
}
}
return true;
}5.优先级队列（堆）
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中，并满足：Ki = K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
5.1堆的创建
import java.util.Arrays;
//用堆在实现优先队列
public class MyHeap {
public int [] elem;
public int useSize;
public MyHeap(){
this.elem = new int[10];
}
public void createHeap(){
for (int parent = (this.useSize-1-1)/2; parent >= 0 ; parent--) {
siftDown(parent,this.useSize);
}
}
//向下
private void siftDown(int parent, int useSize) {
int child = 2*parent + 1;
while (child < useSize){
if (child+1 < useSize && elem[child] < elem[child+1]){
child++;
}
if (elem[child] > elem[parent]){
swap(child,parent);
parent = child;
child = 2*parent + 1;
}else {
break;
}
}
}
public void push(int val){
if (isFull()){
elem = Arrays.copyOf(elem,elem.length*2);
}
elem[useSize] = val;
siftUp(useSize);
useSize ++;
}
//用插入元素的方式实现一个向上
public void siftUp(int child){
int parent = (child-1)/2;
while (child >= 0 ) {
if (elem[child] > elem[parent]) {
swap(child,parent);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
public int poll(int index){
if (isEmpty()){
return -1;
}
int val = elem[index];
int child = useSize - 1;
swap(child, index);
useSize--;
siftDown(index , useSize);
return val;
}
public int peek(){
if (isEmpty()){
return -1;
}
return elem[0];
}
public int contains(int[]elem,int val){
for (int i = 0; i < useSize; i++) {
if (elem[i] == val){
return i;
}
}
return -1;
}
public boolean isFull(){
return this.useSize == elem.length;
}
public boolean isEmpty(){
return useSize == 0;
}
}
5.2.PriorityQueue常用接口介绍
PriorityQueue<Integer> priorityQueue= new PriorityQueue<>();默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}更多推荐
15
0- 0
已为社区贡献1条内容
所有评论(0)