L2-035 完全二叉树的层序遍历(Java)

2024-03-26数据结构与算法2 分钟195 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

题目

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 D{D} 的,有 N{N} 个结点的二叉树,若其结点对应于相同深度完美二叉树的层序遍历的前 N{N} 个结点,这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历,请你给出这棵树的层序遍历结果。

输入格式:
输入在第一行中给出正整数 N(≤30){N(\leq30)},即树中结点个数。第二行给出后序遍历序列,为 N{N} 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

输出格式:
在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

sh 复制代码
8
91 71 2 34 10 15 55 18

输出样例:

sh 复制代码
18 34 55 71 2 10 15 91
sh 复制代码
代码长度限制						16 KB
时间限制							400 ms
内存限制							64 MB

题解

我们知道,二叉树的后序遍历是左右根,我们可以根据这个顺序,每次找到根的时候,将这个节点存储起来。而完全二叉树中,我们可以根据层序遍历给每个节点从 1 到 n 进行编号,由公式可知每个节点的左右节点编号为 2n{2^n}、2n+1{2^n+1}。

代码如下:

java 复制代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

// L2-035 完全二叉树的层序遍历
public class Main {

	static int[] postorder; // 后序遍历
	static int[] tree = new int[31]; // 根据编号存储二叉树的节点
	static int n;

	public static void main(String[] args) throws Exception {
		StreamTokenizer sr = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		sr.nextToken();
		n = (int) sr.nval;
		// 8
		// 91 71 2 34 10 15 55 18
		postorder = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			sr.nextToken();
			postorder[i] = (int) sr.nval;
		}

		// 18 34 55 71 2 10 15 91	
		initTree(1);
		levelorder(1);
	}

	static int count = 1;

	/**
	 * 从根节点开始根据后续遍历生成完全二叉树
	 * 
	 * @param h
	 */
	private static void initTree(int x) {
		if (x > n) {
			return;
		}
		int left = x << 1; // 左节点在完全二叉树的序号
		int right = (x << 1) + 1; // 右节点在完全二叉树的序号
		initTree(left);
		initTree(right);
		tree[x] = postorder[count++];
	}

	/**
	 * 层序遍历
	 * 
	 * @param x
	 */
	private static void levelorder(int x) {
		String s = tree[1] + "";
		for (int i = 2; i <= n; i++) {
			s+=" " + tree[i];
		}
		System.out.print(s);
	}


}
image.png

补充根据节点顺序数组,遍历二叉树

java 复制代码
/**
 * 前序遍历
 * 
 * @param x
 */
private static void preorder(int x) {
	if (x > n) {
		return;
	}
	System.out.print(tree[x] + " ");
	int left = x << 1; // 左节点在完全二叉树的序号
	preorder(left);
	int right = (x << 1) + 1; // 右节点在完全二叉树的序号
	preorder(right);
}

/**
 * 中序遍历
 * 
 * @param x
 */
private static void inorder(int x) {
	if (x > n) {
		return;
	}
	int left = x << 1; // 左节点在完全二叉树的序号
	inorder(left);
	System.out.print(tree[x] + " ");
	int right = (x << 1) + 1; // 右节点在完全二叉树的序号
	inorder(right);
}

/**
 * 后序遍历
 * 
 * @param x
 */
private static void postorder(int x) {
	if (x > n) {
		return;
	}
	int left = x << 1; // 左节点在完全二叉树的序号
	postorder(left);
	int right = (x << 1) + 1; // 右节点在完全二叉树的序号
	postorder(right);
	System.out.print(tree[x] + " ");
}
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句