18、数据结构与算法 - 实战：二叉树1
题目：查找二叉树中最大元素
思路1：利用递归思想，分别查找到左子树中最大元素和右子树中最大元素，然后将它们与根节点的值进行比较。
/**
* 查找二叉树中最大元素
* @param root 二叉树根节点
* @return 二叉树中最大元素
*/
public static int findMax(BinaryTreeNode<Integer> root) {
int max = Integer.MIN_VALUE;
int root_val = 0;
int left_val = 0;
int right_val = 0;
if (root != null) {
root_val = root.getData();
left_val = findMax(root.getLeft());
right_val = findMax(root.getRight());
// 3个值进行比较
if (left_val > right_val) {
max = left_val;
} else {
max = right_val;
}
if (root_val > max) {
max = root_val;
}
}
return max;
}
思路2：利用层序遍历，在节点出队时观察其数据值是否为最大值
/**
* 用非递归的方法查找二叉树中最大元素
* @param root 二叉树根节点
* @return 二叉树中最大元素
*/
public static int findMaxUsingLevelOrder(BinaryTreeNode<Integer> root) {
int max = Integer.MIN_VALUE;
BinaryTreeNode<Integer> temp;
LinkListQueue<BinaryTreeNode<Integer>> queue = new LinkListQueue<BinaryTreeNode<Integer>>();
// 根节点先入队
queue.enQueue(root);
// 队列不为空则遍历
while (!queue.isEmpty()) {
// 获取出队元素
temp = queue.deQueue();
// 判断最大值
if (temp.getData() > max) {
max = temp.getData();
}
// 出队节点的左子树不为空，则左子树入队
if (temp.getLeft() != null) {
queue.enQueue(temp.getLeft());
}
// 出队节点的右子树不为空，则右子树入队
if (temp.getRight() != null) {
queue.enQueue(temp.getRight());
}
}
return max;
}
题目：搜索二叉树中某个元素
思路1：对于给定的二叉树，如果发现树中某个节点的数据值与搜索的元素值相同，返回true。递归的从树根节点向下，比较左子树与右子树各个节点的值。
/**
* 题目：搜索二叉树中某个元素
* @param root 二叉树根节点
* @param data 目标数据值
* @return true 存在该元素 false 不存在该元素
*/
public static boolean hasData(BinaryTreeNode<Integer> root, int data) {
boolean temp = false;
// 二叉树为空，说明数据未找到，返回false
if (root == null) {
return false;
} else {
// 判断当前节点的值是否等于目标数据值
if (root.getData() == data) {
return true;
} else {
// 判断左子树是否包含该元素
temp = hasData(root.getLeft(), data);
// 如果左子树不包含该元素，查找右子树
if (!temp) {
temp = hasData(root.getRight(), data);
}
}
}
return temp;
}
思路2：层序遍历
/**
* 题目：用非递归方法搜索二叉树中某个元素
* @param root 二叉树根节点
* @param data 目标数据值
* @return true 存在该元素 false 不存在该元素
*/
public static boolean hasDataByLevelOrder(BinaryTreeNode<Integer> root, int data) {
BinaryTreeNode<Integer> temp = new BinaryTreeNode<Integer>();
LinkListQueue<BinaryTreeNode<Integer>> queue = new LinkListQueue<BinaryTreeNode<Integer>>();
// 二叉树为空，说明数据未找到，返回false
if (root == null) {
return false;
}
// 根节点入队
queue.enQueue(root);
// 当队列不为空则遍历
while (!queue.isEmpty()) {
// 获取出队元素
temp = queue.deQueue();
// 判断当前节点是否是目标元素
if (temp.getData() == data) {
return true;
}
// 左子树不为空时入队列
if (temp.getLeft() != null) {
queue.enQueue(temp.getLeft());
}
// 左子树不为空时入队列
if (temp.getRight() != null) {
queue.enQueue(temp.getRight());
}
}
return false;
}
题目：向二叉树插入一个元素
思路：因为给定的是二叉树，所以能在任意位置插入元素。为了插入元素，可以使用层序遍历找到一个左孩子或右孩子为空的节点，然后插入该元素。
/**
* 题目：向二叉树插入一个元素
* @param root 二叉树的根节点
* @param data 需要插入的元素
* @return 插入新元素后的根节点
*/
public static BinaryTreeNode<Integer> insert(BinaryTreeNode<Integer> root, int data) {
// 创建新节点
BinaryTreeNode<Integer> newNode = new BinaryTreeNode<Integer>(data);
// 二叉树为空则设置根节点并返回
if (root == null) {
root = newNode;
return root;
}
// 出队元素
BinaryTreeNode<Integer> temp = new BinaryTreeNode<Integer>();
// 创建存储二叉树节点的队列
LinkListQueue<BinaryTreeNode<Integer>> queue = new LinkListQueue<BinaryTreeNode<Integer>>();
// 根节点入队
queue.enQueue(root);
// 队列不为空则遍历
while (!queue.isEmpty()) {
// 获取出队元素
temp = queue.deQueue();
// 检查当前节点左孩子是否为空
if (temp.getLeft() == null) {
temp.setLeft(newNode);
return root;
} else {
queue.enQueue(temp.getLeft());
}
// 检查当前节点右孩子是否为空
if (temp.getRight() == null) {
temp.setRight(newNode);
return root;
} else {
queue.enQueue(temp.getRight());
}
}
return null;
}
题目：获取二叉树节点个数
思路1：递归计算左子树和右子树的大小，再加一
/**
* 题目：获取二叉树节点个数
* @param root 二叉树根节点
* @return 二叉树节点数
*/
public static int size(BinaryTreeNode<Integer> root) {
if (root == null) {
return 0;
} else {
return (size(root.getLeft()) + 1 + size(root.getRight()));
}
}
思路2：利用层序遍历，有元素出队时节点个数加一
/**
* 题目：非递归获取二叉树节点个数
* @param root 二叉树根节点
* @return 二叉树节点数
*/
public static int sizeByLevelOrder(BinaryTreeNode<Integer> root) {
if (root == null) {
return 0;
}
// 出队元素
BinaryTreeNode<Integer> temp = new BinaryTreeNode<Integer>();
// 创建存储二叉树节点的队列
LinkListQueue<BinaryTreeNode<Integer>> queue = new LinkListQueue<BinaryTreeNode<Integer>>();
// 根节点入队
queue.enQueue(root);
// 计数
int count = 0;
// 队列不为空则遍历
while (!queue.isEmpty()) {
// 获取出队元素
temp = queue.deQueue();
// 计数加一
count++;
// 当前节点左子树不为空则入队
if (temp.getLeft() != null) {
queue.enQueue(temp.getLeft());
}
// 当前节点右子树不为空则入队
if (temp.getRight() != null) {
queue.enQueue(temp.getRight());
}
}
return count;
}
题目：逆向逐层输出树中的元素
思路：采用层序遍历，将数据先存入队列，然后出队存入栈中，最后再出栈即可
例如下图所示的二叉树逆向逐层输出顺序为：4 5 6 7 2 3 1
二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
/**
* 题目：逆向逐层输出树中的元素
* @param root 二叉树根节点
*/
public static void printLevelInReverse(BinaryTreeNode<Integer> root) {
// 如果根节点为空，即二叉树本来就不存在
if (root == null) {
return;
}
// 存储出队元素
BinaryTreeNode<Integer> temp = new BinaryTreeNode<Integer>();
// 创建存储二叉树节点的队列
LinkListQueue<BinaryTreeNode<Integer>> queue = new LinkListQueue<BinaryTreeNode<Integer>>();
// 创建存储出队元素的栈
LinkedListStack<BinaryTreeNode<Integer>> stack = new LinkedListStack<BinaryTreeNode<Integer>>();
// 根节点最先入队
queue.enQueue(root);
// 队列不为空则遍历
while (!queue.isEmpty()) {
// 获取出队元素
temp = queue.deQueue();
// 将出队元素入栈
stack.push(temp);
// 右子树先入队
if (temp.getRight() != null) {
queue.enQueue(temp.getRight());
}
// 左子树后入队
if (temp.getLeft() != null) {
queue.enQueue(temp.getLeft());
}
}
// 输出结果
System.out.print("逐层逆向输出：");
while (!stack.isEmpty()) {
System.out.print(stack.pop().getData() + " ");
}
}
说明：完整代码以及对应的测试用例已经提交到我的github上，如有错误敬请指正
https://github.com/Lining531309997/DataStructure