-
二叉树的定义和基本概念
0.完全二叉树--》满二叉树的子树，特点->所有节点1~n和满二叉树一一对应...
1.一颗深为k的完全二叉树，包含了2的k次幂-1个节点，每层最大节点数2的(k-1)次幂
2.完全二叉树，深度为logN+1；
3.i==1，节点i是二叉树的Root，i>1时，节点的父节点是i/2，若2i>n，则节点i有左孩子，左孩子编号为2i，否则节点无左孩子，且是叶子节点...
4.同理，若2i+1>n，则节点i有右孩子，右孩子编号为2i+1，否则节点无左孩子
5.n个节点完全二叉树，1~n/2范围都是有孩子节点的非叶子节点，n/2之后是叶子节点...
-
二叉树的基本操作
1.初始化；
public static class Node { Node left = null; Node right = null; Object data = null; Node parent = null; int leftLen;//求距离最远的节点 int rightLen; public Node(){ } public Node(Object data){ this.data = data; } public Node(Object data, Node left, Node right, Node parent ){ this.data = data; this.left = left; this.right = right; this.parent = parent; }
}
2.为指定节点添加子节点...
3.判断二叉树是否为空
4.返回根节点
5.返回指定节点的父节点
6.返回指定节点的左子节点
7.返回指定节点的右子节点
1
2
3 4
5 6 X 7
8
8.返回二叉树的深度
eg:Node8 Node5 Node6 Node3 Node7 Node4 Node2 Node1 maxDepth =>5
public static int getDepth(Node head) { if (head == null) return 0; else { int left = getDepth(head.left); int right = getDepth(head.right); System.out.print("Node" + head.data + "\t"); return 1 + Math.max(left, right); } }
9.返回二叉树的宽度(层次遍历~)
12345678 maxWidth =>3
public static int getWidth(Node head) { if (head == null) return 0; Queue<Node> queue = new ArrayDeque<Node>(); queue.add(head); int maxWidth = 1; while (true) { int len = queue.size(); if (len == 0) break; while (len > 0) { Node tmp = queue.poll(); len--; System.out.print(tmp.data); if (tmp.left != null) queue.add(tmp.left); if (tmp.right != null) queue.add(tmp.right); } maxWidth = Math.max(maxWidth, queue.size()); } return maxWidth; }
10.返回二叉树节点的最大距离
计算一个二叉树的最大距离有两个情况:
1.路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
2.路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
public static int maxLenGet(Node head) { if (head == null) return 0; if (head.left != null) { head.leftLen = maxLenGet(head.left) + 1; System.out.println("Node" + head.data + ".LeftLen ->" + head.leftLen); } else { head.leftLen = 0; System.out.println("Node" + head.data + ".left=null"); } if (head.right != null) { head.rightLen = maxLenGet(head.right) + 1; System.out.println("Node" + head.data + ".RightLen ->" + head.rightLen); } else { head.rightLen = 0; System.out.println("Node" + head.data + ".right=null"); } if (head.rightLen + head.leftLen > maxDistance) { maxDistance = head.rightLen + head.leftLen; } return head.rightLen > head.leftLen ? head.rightLen : head.leftLen; }
11.返回指定节点的位置
-
实现二叉树的3种方式
顺序存储(数组)，二叉链表(只带左右子节点)，三叉链表(加上父节点)...
-
二叉树的顺序存储的实现
顺序存储只适用于完全二叉树，否则会浪费空间，若二叉树只有右节点，会非常浪费空间...
public void add(int index, T data, boolean left) {
if (datas[index] == null) {
throw new RuntimeException(index + "处节点为空，无法添加子节点");
}
if (2 * index + 1 >= arraySize) {
throw new RuntimeException("树底层的数组已满，树越界异常");
}
//添加左子节点
if (left) {
datas[2 * index + 1] = data;//Note:数组从0开始计数，此处需要2i+1，排序是2i
} else {
datas[2 * index + 2] = data;//Note:数组从0开始计数，此处需要2i+2，排序是2i+1
}
}
@getRight和getLeft时同理，也是2*i+1 and 2i+2