Java代码实现创建一棵二叉链表表示的二叉树中,实现1.输入叶子结点、2.求二叉树中叶子结点个数、3.将每个结点的左子树与右子树交换、4.验证二叉树的性质3:n0=n2+1、5.输出值大于k的结点、6.已知先根和中根次序遍历序列构造二叉树、7.以广义表表示构造二叉树、8.判断两颗二叉树是否相等、9.求结点所在的层次、10.求一颗二叉树在后根次序遍历下第一个访问的结点、11.复制一颗二叉树、12.判断一颗二叉树是否为完全二叉树、13.实现二叉树后根次序遍历的非递归算法的操作,并每一个操作分别采用先根、中根、后根、层次遍历算法
时间: 2023-07-10 16:36:08 浏览: 112
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
5星 · 资源好评率100%
好的,我会尽力回答你的问题。以下是对你提出的Java二叉树问题的回答:
1. 输入叶子节点
首先,我们需要定义节点类:
```java
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
```
然后,我们可以通过递归的方式生成二叉树:
```java
public Node createTree(Scanner scanner) {
System.out.println("请输入节点值:");
int value = scanner.nextInt();
if (value == 0) {
return null;
}
Node node = new Node(value);
node.left = createTree(scanner);
node.right = createTree(scanner);
return node;
}
```
2. 求二叉树中叶子结点个数
我们可以通过递归的方式遍历二叉树,统计叶子节点的个数:
```java
public int countLeafNodes(Node node) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
return 1;
}
return countLeafNodes(node.left) + countLeafNodes(node.right);
}
```
3. 将每个结点的左子树与右子树交换
我们可以通过递归的方式遍历二叉树,交换每个节点的左右子树:
```java
public void swapLeftRight(Node node) {
if (node == null) {
return;
}
Node temp = node.left;
node.left = node.right;
node.right = temp;
swapLeftRight(node.left);
swapLeftRight(node.right);
}
```
4. 验证二叉树的性质3:n0=n2+1
我们可以通过递归的方式遍历二叉树,统计叶子节点和度为2的节点的个数,然后判断它们是否符合性质3:
```java
public boolean verifyPropertyThree(Node node) {
int leafNodes = countLeafNodes(node);
int degreeTwoNodes = countDegreeTwoNodes(node);
return leafNodes == degreeTwoNodes + 1;
}
public int countDegreeTwoNodes(Node node) {
if (node == null) {
return 0;
}
if (node.left != null && node.right != null) {
return countDegreeTwoNodes(node.left) + countDegreeTwoNodes(node.right) + 1;
}
return countDegreeTwoNodes(node.left) + countDegreeTwoNodes(node.right);
}
```
5. 输出值大于k的结点
我们可以通过递归的方式遍历二叉树,输出值大于k的节点:
```java
public void printNodesGreaterThanK(Node node, int k) {
if (node == null) {
return;
}
if (node.value > k) {
System.out.print(node.value + " ");
}
printNodesGreaterThanK(node.left, k);
printNodesGreaterThanK(node.right, k);
}
```
6. 已知先根和中根次序遍历序列构造二叉树
我们可以通过递归的方式构造二叉树,先根次序遍历的第一个节点是根节点,然后在中根次序遍历中找到根节点的位置,将序列分为左右两部分,分别构造左右子树:
```java
public Node buildTree(int[] preOrder, int[] inOrder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootValue = preOrder[preStart];
Node root = new Node(rootValue);
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inOrder[i] == rootValue) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root.left = buildTree(preOrder, inOrder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root.right = buildTree(preOrder, inOrder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
```
7. 以广义表表示构造二叉树
我们可以通过递归的方式构造二叉树,广义表的表示方法是:(root,left,right),其中left和right都是广义表的形式:
```java
public Node buildTree(String str) {
if (str == null || str.length() == 0) {
return null;
}
int firstCommaIndex = str.indexOf(",");
int value = Integer.parseInt(str.substring(1, firstCommaIndex));
Node root = new Node(value);
int secondCommaIndex = findSecondCommaIndex(str);
root.left = buildTree(str.substring(firstCommaIndex + 1, secondCommaIndex));
root.right = buildTree(str.substring(secondCommaIndex + 1, str.length() - 1));
return root;
}
private int findSecondCommaIndex(String str) {
int count = 0;
for (int i = 1; i < str.length() - 1; i++) {
if (str.charAt(i) == '(') {
count++;
} else if (str.charAt(i) == ')') {
count--;
} else if (str.charAt(i) == ',' && count == 0) {
return i;
}
}
return -1;
}
```
8. 判断两颗二叉树是否相等
我们可以通过递归的方式比较两棵二叉树是否相等:
```java
public boolean isSameTree(Node p, Node q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.value != q.value) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
```
9. 求结点所在的层次
我们可以通过递归的方式求出结点所在的层次:
```java
public int getNodeLevel(Node node, Node target, int level) {
if (node == null) {
return 0;
}
if (node == target) {
return level;
}
int leftLevel = getNodeLevel(node.left, target, level + 1);
if (leftLevel != 0) {
return leftLevel;
}
int rightLevel = getNodeLevel(node.right, target, level + 1);
return rightLevel;
}
```
10. 求一颗二叉树在后根次序遍历下第一个访问的结点
我们可以通过递归的方式求出在后根次序遍历下第一个访问的结点:
```java
public Node getFirstVisitNode(Node node) {
if (node == null) {
return null;
}
Node left = getFirstVisitNode(node.left);
Node right = getFirstVisitNode(node.right);
if (left == null && right == null) {
return node;
}
if (right == null) {
return left;
}
if (left == null) {
return right;
}
return node;
}
```
11. 复制一颗二叉树
我们可以通过递归的方式复制一颗二叉树:
```java
public Node cloneTree(Node node) {
if (node == null) {
return null;
}
Node clone = new Node(node.value);
clone.left = cloneTree(node.left);
clone.right = cloneTree(node.right);
return clone;
}
```
12. 判断一颗二叉树是否为完全二叉树
我们可以通过层次遍历的方式判断一颗二叉树是否为完全二叉树:
```java
public boolean isCompleteTree(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
boolean nullNodeAppeared = false;
while (!queue.isEmpty()) {
Node current = queue.poll();
if (current == null) {
nullNodeAppeared = true;
} else {
if (nullNodeAppeared) {
return false;
}
queue.offer(current.left);
queue.offer(current.right);
}
}
return true;
}
```
13. 实现二叉树后根次序遍历的非递归算法的操作,并每一个操作分别采用先根、中根、后根、层次遍历算法
我们可以使用栈的方式实现后根次序遍历的非递归算法,先根、中根、层次遍历的非递归算法也可以使用栈或队列实现:
```java
// 后根次序遍历的非递归算法
public void postOrderTraversal(Node node) {
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(node);
while (!stack1.isEmpty()) {
Node current = stack1.pop();
stack2.push(current);
if (current.left != null) {
stack1.push(current.left);
}
if (current.right != null) {
stack1.push(current.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + " ");
}
}
// 先根次序遍历的非递归算法
public void preOrderTraversal(Node node) {
Stack<Node> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
Node current = stack.pop();
System.out.print(current.value + " ");
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
// 中根次序遍历的非递归算法
public void inOrderTraversal(Node node) {
Stack<Node> stack = new Stack<>();
Node current = node;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
System.out.print(current.value + " ");
current = current.right;
}
}
// 层次遍历的非递归算法
public void levelOrderTraversal(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.print(current.value + " ");
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
}
```
阅读全文