算法初级-04-二叉树系列
2019-07-15 本文已影响0人
囧么肥事
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：二叉树的先序、中序、后序遍历，包括递归方式和非递归方式
实例2：如何直观的打印一颗二叉树
实例3：在二叉树中找到一个节点的后继节点（前驱）
实例4：介绍二叉树的序列化和反序列化
实例5：
实例6：平衡二叉树
实例7：判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树
实例8：已知一棵完全二叉树，求其节点的个数
实例9：
实例10：
本节全部都是关于二叉树的问题。
实例1
实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式
递归方式遍历二叉树
其实三种遍历都是一样的，唯一的区别就是打印的时机不同
先打印就是先序
中间打印就是中序
后打印就是后序
非递归遍历二叉树
使用辅助栈根据不同的压栈顺序进行遍历。
import java.util.Stack;
/**
* @description: 二叉树操作：前序遍历二叉树、中序、后序遍历二叉树。
* @version: 1.0
*/
public class Code_25_PreorderInorderPostorderTraversal {
// 二叉树节点
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 前序遍历递归版
public static void preOrderRecur(Node head) {
if (head == null)
return;
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
// 中序遍历递归版
public static void inOrderRecur(Node head) {
if (head == null) return;
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
// 后序遍历递归版
public static void postOrderRecur(Node head) {
if (head == null) return;
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
/**
* 前序遍历：非递归
* 1、准备一个栈，先入头结点
* 2、遍历栈（循环条件：栈不为空）
* 从栈中弹出一个元素，打印
* 判断这个节点是否有右子树，有入栈
* 判断这个节点是否有左子树，有入栈
* @param head
*/
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
if (head == null) return;
Stack<Node> stack = new Stack<>();
stack.add(head);
// stack.push(head); // 存头结点
// stack 的add 方法和push 方法本质上没有区别，都是调用java.util.Vector.add(E)方法
// 唯一不同就是返回值不同，add 返回添加成功否，push 返回这个添加的元素对象
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
System.out.println();
}
/**
* 中序遍历，非递归
*
* 全力压左边界入栈，整棵树可以被左边界分解
*
* 1、准备一个栈
* 2、遍历（循环条件：栈不为空 || 当前节点不为空）
* a、当前节点不为空，就将当前节点入栈，指向左孩子
*
* b、当前节点为空，栈不为空，从当前栈中弹出一个节点，打印
* 当前节点 指向当前节点的右孩子
*
* 即：
* if（当前节点不为空）{ //
* 压入当前节点的左孩子
* 当前节点 = 当前节点.left
* } else {
* 弹出一个节点， 打印
* 指向右孩子，继续循环 2 过程
* }
* @param head
*/
public static void inOrderUnRecur(Node head){
System.out.print("in-order: ");
if (head == null) return;
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()){
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
System.out.println();
}
/**
* 后序遍历：非递归
*
* 前序遍历：中左右 非递归 思路
* 保存头结点，当前节点有右孩子，存
* 当前节点有左孩子，存
* 总体入栈顺序是：右左 ---> 打印结果：中左右
*
* 后序遍历 ：左右中 思路：借用前序遍历的思路，做出一个 中右左的打印结果，在该打印的时候入另一个栈
* 根据栈的弹出顺序，就成了左右中
*
* 保存头结点，当前节点有左孩子，存
* 当前节点有右孩子，存
* 总体入栈顺序是：左右 ---> 打印结果：中右左（不打印，节点入另一个栈）
*
* 最后在统一打印另一个栈的节点 --- 中右左 ----> 左右中
* @param head
*/
public static void postOrderUnRecur1(Node head) {
System.out.print("post-order-1: ");
if (head == null) return;
Stack<Node> preStack = new Stack<>();
Stack<Node> postStack = new Stack<>();
preStack.add(head);
while (!preStack.isEmpty()) {
head = preStack.pop();
postStack.push(head); // 在本该打印的时机，选择存入到另一个栈
if (head.left != null) {
preStack.push(head.left);
}
if (head.right != null){
preStack.push(head.right);
}
}
while (!postStack.isEmpty()){
System.out.print(postStack.pop().value + " ");
}
System.out.println();
}
// 暂时不要求理解
public static void postOrderUnRecur2(Node h) {
System.out.print("pos-order: ");
if (h != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(h);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
// recursive
System.out.println("==============recursive==============");
System.out.print("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.print("pos-order: ");
postOrderRecur(head);
System.out.println();
// unrecursive
System.out.println("============unrecursive=============");
preOrderUnRecur(head);
inOrderUnRecur(head);
postOrderUnRecur1(head);
postOrderUnRecur2(head);
}
}
实例2
如何直观的打印一颗二叉树
左神设计的打印方式，虽然看着丑！但很实用
package cn.zqtao.learn.day4;
/**
* 直观打印二叉树
*/
public class Code_26_PrintBinaryTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(-222222222);
head.right = new Node(3);
head.left.left = new Node(Integer.MIN_VALUE);
head.right.left = new Node(55555555);
head.right.right = new Node(66);
head.left.left.right = new Node(777);
printTree(head);
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.left = new Node(5);
head.right.right = new Node(6);
head.left.left.right = new Node(7);
printTree(head);
head = new Node(1);
head.left = new Node(1);
head.right = new Node(1);
head.left.left = new Node(1);
head.right.left = new Node(1);
head.right.right = new Node(1);
head.left.left.right = new Node(1);
printTree(head);
head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
printTree(head);
}
}
实例3
在二叉树中找到一个节点的后继节点
【题目】 现在有一种新的二叉树节点类型如下：
public class Node{
public int value;
public Node parent; // 父节点
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
假 设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针 都正确地指向 自己的父节点，头节点的parent指向null。只给一个在 二叉树中的某个节点 node，请实现返回node的后继节点的函数。
在二 叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。
思路：
给定二叉树中的任意一个节点，找到，当前节点的后继节点，并返回
第一种情况：如果node有右子树，那么后继节点就是整棵右子树上最左边的节点 右子树--->最左
第二种情况：如果node没有右子树
a、node是不是node 父节点的左孩子, 是，返回父节点
b、不是，向上遍历，创建指针parent指向node父节点，node节点和父节点一直上移，找到 a 的情况， 返回
PS: 代码中给出了寻找前驱节点的思路
/**
* @auther: zqtao
* @description:
* @version: 1.0
*/
public class Code_27_SuccessorNode {
public static class Node{
public int value;
public Node parent; // 父节点
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
/**
* 给定二叉树中的任意一个节点，找到，当前节点的后继节点，并返回
*
* 第一种情况：如果node有右子树，那么后继节点就是整棵右子树上最左边的节点 右子树--->最左
* 第二种情况：如果node没有右子树
* a、node是不是node 父节点的左孩子, 是，返回父节点
* b、不是，向上遍历，创建指针parent指向node父节点，node节点和父节点一直上移，找到 a 的情况， 返回
*
*/
public static Node successorNode(Node node){
if (node == null) return node;
if (node.right != null) { // 有右孩子
return getLeftMostOfNodeHaveRightChild(node.right);
} else { // 无右孩子
Node parent = node.parent;
while (parent != null && parent.left != node) { // parent != null 针对的是整个二叉树上的最后一个节点
node = parent;
parent = parent.parent;
}
return parent;
}
}
/**
* 有右子树找后继节点
* @param node 目标节点的右节点
* @return 后继节点
*
* 思路，如果目标节点有右子树，那么后继节点就是整棵右子树上最左边的那个节点
*/
public static Node getLeftMostOfNodeHaveRightChild(Node node){
if (node == null) return node;
while (node.left != null) {
node = node.left;
}
return node;
}
public static void main(String[] args) {
Node head = new Node(6);
head.parent = null;
head.left = new Node(3);
head.left.parent = head;
head.left.left = new Node(1);
head.left.left.parent = head.left;
head.left.left.right = new Node(2);
head.left.left.right.parent = head.left.left;
head.left.right = new Node(4);
head.left.right.parent = head.left;
head.left.right.right = new Node(5);
head.left.right.right.parent = head.left.right;
head.right = new Node(9);
head.right.parent = head;
head.right.left = new Node(8);
head.right.left.parent = head.right;
head.right.left.left = new Node(7);
head.right.left.left.parent = head.right.left;
head.right.right = new Node(10);
head.right.right.parent = head.right;
Node test = head.left.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.left.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.left.right.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.left.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.left;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right;
System.out.println(test.value + " next: " + successorNode(test).value);
test = head.right.right; // 10's next is null
System.out.println(test.value + " next: " + successorNode(test));
}
/*
补充：二叉树寻找前驱节点
回忆一下二叉树寻找后继节点
1、有右孩子
右孩子 ---> 最左
2、无右孩子
找其中父节点的【左子树节点】等于当前节点（一直在向上移动，即，当前节点在变）的父节点
同理前驱
1、有左孩子
左孩子 ---> 最右
2、无孩子
找其中父节点的【右子树节点】等于当前节点（一直在向上移动，即，当前节点在变）的父节点
*/
}
实例4
介绍二叉树的序列化和反序列化
二叉树被记录成文件的过程叫做二叉树的序列化
通过记录的文件重建二叉树的过程叫做二叉树的反序列化。
方法：先序、中序、后序、按层遍历都可以实现二叉树的序列化和反序列化。
但是我悲哀的发现，学习完了左神的两个序列化和反序列化方式后，我想继续其他方式编写，出现了bug, 向百度求助查找时，悲哀的发现都是一群水军，只要你搜索二叉树的序列化和反序列化，所有人的帖子都是惊人的雷同，说的一句话就是左神在课堂上说的：“先序，中序，后序序列化和反序列是类似的，这里以先序为例，，，然后，，，”，因为左神只讲了二叉树的先序，给出了层次遍历的方式，然后就爆炸了，所有的帖子都是先序为例，我疯狂找网上中序的方式实现序列化，，，得到的答案是：呵呵
这让菜鸡的我很难受。只能先放弃，等以后有能力再加上吧，现在太菜了。
伤心的我，连左神的代码都懒得改了
import java.util.LinkedList;
import java.util.Queue;
/**
* @description:
* @version: 1.0
*/
public class Code_28_SerializeAndReconstructTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// =================================== {先序} ============================================
// 通过先序遍历来序列化二叉树
public static String serialByPre(Node head) {
if (head == null) return "#!";
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
// 通过先序遍历反序列化二叉树
public static Node reconByPreString(String serialNodeString) {
return reconPreOrder(getQueue(serialNodeString));
}
public static Node reconPreOrder(Queue<String> queue) {
String poll = queue.poll();
if (poll.equals("#"))
return null;
// 不为空，消费这个节点
Node head = new Node(Integer.parseInt(poll));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
public static Queue<String> getQueue(String serialNodeString) {
if (serialNodeString == null) return null;
String[] split = serialNodeString.split("!");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < split.length; i++) {
queue.add(split[i]);
}
return queue;
}
// =================================== {中序} ============================================
// 中序遍历序列化
public static String serialByIn(Node head) {
if (head == null) return "#!";
String res = serialByIn(head.left);
res += head.value + "!";
res += serialByIn(head.right);
return res;
}
public static Node reconByInString(String serialNodeString) {
return reconByIn(getQueue(serialNodeString));
}
// 中序遍历反序列化: 不会
public static Node reconByIn(Queue<String> queue) {
return null;
}
public static String serialByLevel(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
Queue<Node> queue = new LinkedList<Node>();
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
if (head.left != null) {
res += head.left.value + "!";
queue.offer(head.left);
} else {
res += "#!";
}
if (head.right != null) {
res += head.right.value + "!";
queue.offer(head.right);
} else {
res += "#!";
}
}
return res;
}
public static Node reconByLevelString(String levelStr) {
String[] values = levelStr.split("!");
int index = 0;
Node head = generateNodeByString(values[index++]);
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.offer(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return head;
}
public static Node generateNodeByString(String val) {
if (val.equals("#")) {
return null;
}
return new Node(Integer.valueOf(val));
}
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = null;
printTree(head);
String pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
String level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.right = new Node(5);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(100);
head.left = new Node(21);
head.left.left = new Node(37);
head.right = new Node(-42);
head.right.left = new Node(0);
head.right.right = new Node(666);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
}
}
实例6
判断一棵二叉树是否是平衡二叉树。平衡二叉树的性质为:要么是一棵空树,要么任何一个节点的左右子树高度差的绝对值不超过1。给定一棵二叉树的头节点head,判断这棵二叉树是否为平衡二又树。
递归函数套路，高度套路化（也叫树形dp, 就是树形动态规划）
1、分析各种可能性
2、设计返回结构
分析好可能性后，确定要收集的信息，定义好返回结构，
根据子过程收集的信息，自己在决策过程也加工整合出同样结构的信息，往上一层进行返回。
这个套路最重要的是列出所有的可能性。
比如这道题：平衡二叉树
可能性，考虑以每一个节点为根节点的每一棵子树是否也是平衡的
1、左子树是否平衡
2、右子树是否平衡
3、左子树是否平衡和高度
4、右子树是否平衡和高度
当前节点的高度是根据子树给的高度决定的。
6_1_平衡二叉树_任意一个节点返回信息.png
/**
* @description:
* @version: 1.0
*/
public class Code_29_IsBanlaceTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 递归返回值结构
public static class ReturnData{
public boolean isB; // 是否平衡
public int heith; // 高度
public ReturnData(boolean isB, int heith) {
this.heith = heith;
this.isB = isB;
}
}
public static boolean isBanlanceTree(Node head){
return process(head).isB;
}
/**
* 递归处理过程
*
* 递归套路：分析好可能性后，确定要收集的信息，定义好返回结构，
* 根据子过程收集的信息，自己在决策过程也加工整合出同样结构的信息，往上一层进行返回。
*
*
* 这个套路最重要的是列出所有的可能性。
*
* 比如这道题：平衡二叉树
* 可能性，考虑以每一个节点为根节点的每一棵子树是否也是平衡的
*
* 1、左子树是否平衡
*
* 2、右子树是否平衡
*
* 3、左子树是否平衡和高度
*
* 4、右子树是否平衡和高度
*
*
*
* 当前节点的高度是根据子树给的高度决定的。
* @param head
* @return
*/
public static ReturnData process(Node head){
// 07
if (head == null) return new ReturnData(true, 0);// null是平衡树
// 收集左子树信息
ReturnData leftData = process(head.left);
if (!leftData.isB) { // 左子树不平衡
return new ReturnData(false,0);
}
// 收集右子树信息
ReturnData rightData = process(head.right);
if (!rightData.isB) { // 左子树不平衡
return new ReturnData(false, 0);
}
// 根据左右子树信息，加工整合出同样结构的信息
if (Math.abs(leftData.heith - rightData.heith) > 1) { // 左右子树平衡，高度差大于1情况
return new ReturnData(false, 0);
}
// 平衡，往上一层进行返回
return new ReturnData(true, Math.max(leftData.heith, rightData.heith) + 1);
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
System.out.println(isBanlanceTree(head));
}
}
实例7
判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树
搜索二叉树：任意节点的左节点都比自己小，右节点都比自己大
二叉树中序遍历的结果是依次升序的就是搜索二叉树，否则就不是。注意：通常搜索二叉树是不含重复值节点的。
完全二叉树
判断一棵二叉树是否是完全二叉树,依据以下标准会使判断过程变得简单且易实现:
1,按层遍历二叉树,从每层的左边向右边依次遍历所有的节点。
2,如果当前节点有右孩子,但没有左孩子,直接返回false.
3,如果当前节点并不是左右孩子全有,那之后的节点必须都为叶节点,否则返回false.
4,遍历过程中如果不返回false,遍历结束后返回true.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @description:
* @version: 1.0
*/
public class Code_30_IsBSTAndCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 回忆之前学的非递归：中序遍历
// 全力压左孩子入栈，整棵二叉树可以被分解为多个左子树状态
/*public static void inOrderUnRecure(Node head){
System.out.println("in-order: ");
if (head != null){
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
}*/
// 根据非递归形式改写中序遍历，判断搜索二叉树
// 搜索二叉树特点，中序遍历结果是依次递增的
public static boolean BST(Node head){
if (head == null){
return true;
}
int val = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<>();
while (head != null || !stack.isEmpty()){
if (head != null) {
stack.add(head);
head = head.left;
} else {
head = stack.pop();
if (val > head.value){
return false;
} else {
val = head.value;
}
head = head.right;
}
}
return true;
}
// 层次遍历进行遍历
/**
* 判断一棵二叉树是否是完全二叉树,
* 依据以下标准会使判断过程变得简单且易实现:
*
* 1,按层遍历二叉树,从每层的左边向右边依次遍历所有的节点。
* 2,如果当前节点有右孩子,但没有左孩子,直接返回false.
* 3,如果当前节点并不是左右孩子全有,那之后的节点必须都为叶节点,否则返回false.
* 4,遍历过程中如果不返回false,遍历结束后返回true.
*/
public static boolean CBT(Node head){
if (head == null) return true;
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
Node L = null;
Node R = null;
boolean leaf = false; // 记录接下来的遍历是否都是叶节点的遍历
while (!queue.isEmpty()){
head = queue.poll();
L = head.left;
R = head.right;
// 排除掉不是的可能性方案
if (
(leaf && (L != null || R != null)) // 当开启叶节点遍历时：叶节点存在子树，则返回false
|| (L == null && R != null) // 或者当前节点的左子树为null，右子树不为空，返回false
) {
return false;
}
// 继续遍历子树
if (L != null) {
queue.offer(L);
}
if (R != null) {
queue.offer(R);
} else {
leaf = true; // 当左子树，或者右子树等于null时，开启叶节点遍历
}
}
return true;
}
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.left = new Node(5);
printTree(head);
System.out.println(BST(head));
System.out.println(CBT(head));
}
//////////////////////////////////for test s/////////////////////////////////////////
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
//////////////////////////////////for test e/////////////////////////////////////////
}
实例8
已知一棵完全二叉树，求其节点的个数
要求：时间复杂度低于O(N)，N为这棵树的节点个数
思路：
1、如果head== null ，空树，return0
2、head ！= null，遍历求树的高度。遍历左边界即可。
3、递归过程：给定一个节点，返回以该节点为二叉树的所有节点数
每一层只需要选择一个节点node进行遍历过程
节点右子树左边界到达最后一层
证明该节点的左子树是一课满完全二叉树
总节点=公式计算左子树总节点数 + 右子树递归查找节点数 + 当前节点
8_1_节点右子树左边界到达最后一层.png
节点右子树左边界没有到达最后一层
否， 证明该节点的右子树是一课满完全二叉树
总节点=左子树递归查找节点数 + 公式计算右子树总节点数 + 当前节点
8_2_节点右子树左边界没有到达最后一层.png
因为每一层都只选取了开一个节点进行递归过程，所以真正访问节点的个数等于完全二叉树的层数，都会查看node右子树的最左节点，假设h层，会遍历O(h)个节点，整个过程时间复杂度O(h^2)。也可以按照样本量写为O(logN ^2)
/**
* @description: 已知一棵完全二叉树，求其节点的个数
*
*要求：时间复杂度低于O(N)，N为这棵树的节点个数
*
* 时间复杂度 O(logN ^ 2)
* @version: 1.0
*/
public class Code_31_CompleteTreeNodeNumber {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static int getNumber(Node head) {
if (head == null) return 0;
return process(head, 1, getMaxLeftLevel(head, 1));
}
// 返回当前节点为树的节点数
public static int process(Node node, int level, int treeHigh) {
if (level == treeHigh) { // 当前节点所在的层级是二叉树的总高度，叶子节点
return 1;
}
if (getMaxLeftLevel(node.right, level + 1) == treeHigh) { // 该节点的右子树的左边界是否等于二叉树总高度
// 是 ，证明该节点的左子树是一课满完全二叉树
// 总节点=公式计算左子树总节点数 + 右子树递归查找节点数 + 当前节点
return (1 << (treeHigh - level)) + process(node.right, level + 1, treeHigh);
/*
return (1<< (treeHigh - level) - 1) + process(node.right, level + 1, treeHigh) + 1;
*/
} else {
// 否， 证明该节点的右子树是一课满完全二叉树
// 总节点=左子树递归查找节点数 + 公式计算右子树总节点数 + 当前节点
return process(node.left, level + 1, treeHigh) + (1 << (treeHigh - level - 1));
}
}
// 返回当前节点的最大左边界
public static int getMaxLeftLevel(Node node, int level) {
while (node != null) {
level++;
node = node.left;
}
return level - 1;
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
System.out.println(getNumber(head));
}
}
