java - 树节点的高度和级别顺序
问题描述
请看一下代码，让我知道问题出在哪里。因为我想找到高度和水平顺序，但输出什么都没有。因为左右节点总是包含空值。
这是主要功能：
public static void main(String[] args)
{
Tree t1 = new Tree();
Tree t2 = new Tree();
t1.makeTree();
t1.levelOrder(); //0 1 2 3 4 5 6 13 14 15 7 8 9 10 11 12
System.out.println("height: " + t1.height()); //3
t2.makeTree2();
t2.levelOrder(); //0 1 2 3
System.out.println("height: " + t2.height()); //1
System.out.println("sub tree t1 and t1 " + t1.isSubTree(t1));
System.out.println("sub tree t1 and t2 " + t1.isSubTree(t2)); //t2 is not a subTree of t1
Tree t3 = new Tree();
t3.makeTree3();
t3.levelOrder();
System.out.println("sub tree t1 and t3 " + t1.isSubTree(t3)); //t3 is a subTree of t1
Tree t4 = new Tree();
t4.makeTree4();
t4.levelOrder();
System.out.println("sub tree t1 and t4 " + t1.isSubTree(t4)); //t4 is a subTree of t1
}
}
这是树类：
class Tree{
private static class TNode{
private int value;
private TNode parent;
private TNode left, right;
private List<TNode> children;
public TNode(){
this(0, null);
}
public TNode(int e){
this(e, null);
}
public TNode(int e, TNode p){
value = e;
parent = p;
left=right=null;
children = new ArrayList<TNode>();
}
}
private TNode root;
private int size;
Tree(){
root = null;
size = 0;
}
public TNode createNode(int e, TNode p){
return new TNode(e, p);
}
public TNode addChild(TNode n, int e){
TNode temp = createNode(e, n);
n.children.add(temp);
size++;
return temp;
}
public void makeTree(){
root = createNode(0, null);
size++;
buildTree(root, 3);
}
public void makeTree2(){
root = createNode(0, null);
size++;
buildTree(root, 1);
}
public void makeTree3(){
root = createNode(3, null);
size++;
}
public void makeTree4(){
root = createNode(2, null);
size += 13;
buildTree(root, 1);
size -= 12;
}
private void buildTree(TNode n, int i){
if (i <= 0) return;
TNode fc = addChild(n, size);
TNode sc = addChild(n, size);
TNode tc = addChild(n, size);
buildTree(fc, i - 1);
buildTree(sc, i - 2);
if (i % 2 == 0)
buildTree(tc, i - 1);
}
public long height(TNode n){
/*implement*/
if (n == null)
return 0;
else
{
/* compute height of each subtree */
long lheight = height(n.left);
long rheight = height(n.right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
// return 0; } public long height(){
return height(root);
}
public void levelOrder(){
/*implement*/
Queue<TNode> queue = new LinkedList<TNode>();
queue.add(root);
while (!queue.isEmpty())
{
TNode tempNode = queue.poll();
//System.out.print(tempNode.value + " ");
/*Enqueue left child */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/*Enqueue right child */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
} } public boolean isSubTree(Tree st){
/*implement for extra credit*/ return false;
}
}
解决方案
有了这些额外的信息，这个问题现在可以回答了：
原始类只有以下数据成员：
private int value; private TNode parent; private List<TNode> children;
height()因此，您正在尝试实现levelOrder()任意树。您已经知道如何为二叉树实现这些功能。我们需要做的是根据您拥有的数据结构调整您所知道的算法。
让我们从您拥有的左/右版本开始：
public long height(TNode n){
if (n == null) {
return 0;
} else {
/* compute height of each subtree */
long lheight = height(n.left);
long rheight = height(n.right);
/* use the larger one */
if (lheight > rheight) {
return(lheight+1);
} else {
return(rheight+1);
}
}
return 0;
}
这是对的。所需要做的就是将其从左右递归更改为使用子项的内容。该算法是相同的，如评论所示：
public long height(TNode n){
if (n == null) {
return 0;
} else {
/* compute height of each subtree */
/* use the larger one */
}
return 0;
}
我们如何计算每个子树的高度？
for (TNode child : n.children) {
/* compute height of each subtree */
long childHeight = height(child);
}
但是我们需要跟踪最大的一个。
long highest = 0;
for (TNode child : n.children) {
/* compute height of each subtree */
long childHeight = height(child);
/* use the larger one */
highest = Math.max(highest, childHeight);
}
return highest + 1;
把它们放在一起：
public long height(TNode n){
if (n == null) {
return 0;
} else {
long highest = 0;
for (TNode child : n.children) {
/* compute height of each subtree */
long childHeight = height(child);
/* use the larger one */
highest = Math.max(highest, childHeight);
}
return highest + 1;
}
return 0;
}
至于levelOrder，您可以在那里遵循相同的逻辑。我会把它作为练习留给你。
解决此评论：
请您指导我如何从非二叉树中找到子树？
由于这是一棵任意树，而不是 BST，我们对孩子的顺序一无所知，所以我们不能去寻找特定的值。因此，要找到子树，我们必须检查每个孩子。
/**
* haystack represents the tree we're looking inside
* needle is the tree we're looking for
*/
private boolean isSubTree(TNode haystack, TNode needle) {
if (haystack == null && needle == null) {
// Leaf
return true;
}
if (haystack == null || needle == null) {
// One is null, the other isn't
return false;
}
if (haystack.value != needle.value) {
// No match
return false;
}
// We'll assume that order matters, and that all children need to match.
if (haystack.children.size() != needle.children.size()) {
return false;
}
// Iterate over all children and see if they match
boolean result = true;
for (int index = 0; index < haystack.children.size(); index++) {
result = result && isSubTree(
haystack.children.get(index),
needle.children.get(index));
}
return result;
}
要调用它，遍历 this.root 中的所有节点（可能通过使用levelOrder）并调用上述方法，如果任何一个调用返回 true，则返回 true。这是一个 O(n*m) 算法，其中 n 是大海捞针中的节点数，m 是针中的节点数。
推荐阅读
- scala - 案例类的无样板投影以更改枚举的数据类型
- sql-server - 从游标内的表中选择列
- java - 从文本文件中读取，然后将值分配给数组
- reactjs - 我们是否总是必须在 Reducer 中将状态视为不可变的？
- php - 在 PHP 中，有没有办法循环查询并根据值将其组织到特定的列中？
- javascript - 从 Apps Script 到 MySQL 连接失败的 jdbc 连接
- algorithm - 范围搜索算法，用于查询给定区域中二维平面中的形状
- h2o - 仅选择每个 h2o 数据帧 group_by 组中的第一行（用于合并）？
- php - 如何使用 PHP 和 DOMDocument 生成具有页面本地化版本的 Google 站点地图
- postgresql - 将本地数据库迁移到 AWS Aurora