一、二叉树
1、前序遍历：先访问根节点、前序遍历左子树、前序遍历右子树
private void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if(node == null) return;
System.out.printIn(node.element);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
2、中序遍历：先访问中序遍历左子树、根节点、中序遍历右子树
private void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if(node == null) return;
inorderTraversal(root.left);
System.out.printIn(node.element);
inorderTraversal(root.right);
}
3、后序遍历：先访问后序遍历左子树、后序遍历右子树、根节点
private void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if(node == null) return;
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.printIn(node.element);
}
4、层序遍历：从上到下，从左到右依次访问每一个节点，使用队列
思路:
1、将根节点入队
2、循环下列操作，直到队列为空
a、将队头节点A出队，进行访问
b、将A的左子节点入队
c、将A的右子节点入队
public void reverseTree() {
if(root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
Node node = queue.poll()
Sysytem.out.printIn(node.element)
if(node.left != null) {
queue.offer(node.left)
}
if(node.right != null) {
queue.offer(node.right)
}
}
}
5、计算二叉树的高度
public int height() {
return height(root);
}
1、递归
private int height(Node node) {
if(node == null) return 0;
return 1 + Max.max(height.left, height.right);
}
2、迭代，使用层序遍历方式
public int height() {
if(root== null) return 0;
int height = 0;
int levelSize = 1;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
Node node = queue.poll()
levelSize--;
if(node.left != null) {
queue.offer(node.left)
}
if(node.right != null) {
queue.offer(node.right)
}
if(levelSize == 0) {
levelSize = queue.size();
height++;
}
}
}
6、判断一个树是否为完全二叉树
1、思路
a、如果树为空，返回false
b、如果树不为空，开始层序遍历二叉树(队列方式)
- 如果node.left !=null && node.right != null,将 node.left、node.right 按顺序入队
- 如果node.left == null && node.right != null ,返回false
- 如果node.left != null && node.right == null 或者node.left == null && node.right == null,那么后面遍历的所有节点都为叶子节点，才是完全二叉树，否则返回false
public boolean isComplete() {
if(root == null) return false;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while(!queue.isEmpty()) {
Node node = queue.poll();
if(lead && !(node.left == null && node.right == null)) {
return false;
}
if(node.left != null && node.right != null) {
queue.offer(node.left);
queue.offer(node.right);
} else if(nodel.left = == null && node.right != null) {
return false;
} else { // 判断后面遍历的节点都是叶子结点
leaf = true;
}
}
return true;
}
7、翻转二叉树
a、前序遍历
private TreeNode invertTree(TreeNode root) {
if(root == null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
b、中序遍历
private TreeNode invertTree(TreeNode root) {
if(root == null) return root;
invertTree(root.left);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
return root;
}
c、后序遍历
private TreeNode invertTree(TreeNode root) {
if(root == null) return root;
invertTree(root.left);
invertTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
d、层序遍历
private TreeNode invertTree(TreeNode root) {
if(root == null) return root;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (! queue.isEmpty()) {
Node node = queue.poll();
Node tmp = node.left;
node.left = node.right;
node.right = tmp;
if(node.left != null) {
queue.offer(node.left);
}
if(node.left != null) {
queue.offer(node.right);
}
}
}
二、计算完全二叉树的结点个数
// n：总结点数量
当n是偶数，n0 = n / 2
当n时奇数，n0 = (n + 1)/2
n0 = (n + 1) >> 1
