二叉树
class Tree {
Node left;
Node right;
int value;
//递归
public static void f(Tree head) {
if(head == null) {
reutrn;
}
f(head.left);
f(head.right);
}
//遍历结果
//1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
}
遍历
先序遍历
先序遍历指的是所有子树中先打印头节点、在左节点、最后右节点
头左右：：1，2，4，5，3，6，7（利用递归顺第一次出现的打印）
递归方式：
public static void f(Tree head) {
if(head == null) {
reutrn;
}
System.out.println(head.value);
f(head.left);
f(head.right);
}
非递归压栈形式可实现：
每次
- 从栈中弹出一个节点cur
- 打印
- 先右后左压入（如果有）
- 重复1
public static void f(Tree head) {
if(head == null) {
return;
}
Stack<Node> stack = new Stack();
stack.add(head);
while(!stack.isEmpty()){
Node head = stack.pop();
System.out.print(head.value);
if(head.right != null) {
stack.push(head.right);
}
if(head.left!= null) {
stack.push(head.left);
}
}
}
中序遍历
左头右：4，2，5，1，6，3，7（利用递归顺第二次出现的打印）
public static void f(Tree head) {
if(head == null) {
reutrn;
}
f(head.left);
System.out.println(head.value);
f(head.right);
}
非递归：
- 先将所有子树左节点放入栈中
- 弹出打印
- 弹出时判断是否存在右子树
- 存在压入右节点
public void inOrderUnRecur(Node head) {
if (head == null) {
return;
}
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.println(head.value);
head = head.right;
}
}
}
后序遍历
左右头：4，5，2，6，7，3，1（利用递归顺第三次出现的打印）
public static void f(Tree head) {
if(head == null) {
reutrn;
}
f(head.left);
f(head.right);
System.out.println(head.value);
}
非递归：
- 申请1个栈、1个收集栈
- 放入头cur 弹出放入收集栈
- 先左在右放入（如果右）
- 弹出
- 遍历收集栈
public static void f(Tree head) {
if(head == null) {
return;
}
Stack<Node> s1= new Stack();
Stack<Node> s2 = new Stack();
stack.push(head);
while(!s1.isEmpty()){
head = s1.pop();
s2.push(head);
if(head.left!= null) {
stack.push(head.right);
}
if(head.right != null) {
stack.push(head.right);
}
}
while(!s2.isEmpty()){
System.out.println(s2.pop().value);
}
}
深度遍历
二叉树的深度遍历即为先序遍历。
广度遍历（宽度遍历）
用队列先左在右放入取出即可
public static void f(Node head) {
if(head == null) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(head);
while(!queue.isEmpty()){
head= queue.poll();
System.out.print(head.value);
if(head.left!= null) {
queue.add(head.left);
}
if(head.right!= null) {
queue.add(head.right);
}
}
}
计算当前树最大宽度是多少
public static int w(Node head) {
if(head == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(head);
//记录节点个数
Map<TreeNode, Integer> levelMap = new HashMap<>();
levelMap.put(head,1);
//当前最大个数
int max = Integer.MIN_VALUE;
//当前层数
int curLevel = 0;
//当前节点个数统计
int curNodeNum = 0;
while(!queue.isEmpty()){
head = queue.poll();
if (levelMap.get(head) == curLevel) {
curNodeNum ++;
} else {
max = Math.max(max, curNodeNum);
curLevel ++;
curNodeNum = 1;
}
if(head.left!= null) {
levelMap.put(head.left, curLevel + 1);
queue.add(head.left);
}
if(head.right!= null) {
levelMap.put(head.right, curLevel + 1);
queue.add(head.right);
}
}
return Math.max(max, curNodeNum);
}
搜索二叉树
所有子树左节点都比右小
判断是否为搜索二叉树
中序遍历 判断是否为依次升序、升序即为搜索二叉树
public static boolean isBST(Tree head) {
int preValue = 0;
if(head == null) {
reutrn true;
}
boolean result= isBST(head.left);
if(!result){
return false;
}
if(head.value <= preValue) {
return false;
}else{
preValue = head.value;
}
return isBST(head.right);
}
判断完全二叉树
- 进行广度遍历并记录
- 如果出现有右孩子无左孩子直接false
- 满足2条件如果出现第一个左右不全必须为叶子节点