在二进制search树中查找高度
我想知道是否有人可以帮我修改这个方法来find二叉search树的高度。 到目前为止，我的代码看起来像这样。 但是，我得到的答案是比实际的高度大1。但是，当我从我的返回语句中删除+1，它比实际的高度小1。我仍然试图围绕recursion与我的头这些BST。 任何帮助将非常感激。
public int findHeight(){ if(this.isEmpty()){ return 0; } else{ TreeNode<T> node = root; return findHeight(node); } } private int findHeight(TreeNode<T> aNode){ int heightLeft = 0; int heightRight = 0; if(aNode.left!=null) heightLeft = findHeight(aNode.left); if(aNode.right!=null) heightRight = findHeight(aNode.right); if(heightLeft > heightRight){ return heightLeft+1; } else{ return heightRight+1; } } 问题在于你的基本情况。
“树的高度是树中从根到最深节点的path的长度，只有一个节点（根）的（根）树的高度为零。 – 维基百科
如果没有节点，则要返回-1而不是0.这是因为您在结尾处添加1。
因此，如果没有节点，则返回-1，从而取消+1。
int findHeight(TreeNode<T> aNode) { if (aNode == null) { return -1; } int lefth = findHeight(aNode.left); int righth = findHeight(aNode.right); if (lefth > righth) { return lefth + 1; } else { return righth + 1; } }
二叉search树的高度等于number of layers - 1 。
请参阅http://en.wikipedia.org/wiki/Binary_tree上的图表;
你的recursion是好的，所以只需要在根目录下减去一个。
还要注意，你可以通过处理空节点来清理这个函数：
int findHeight(node) { if (node == null) return 0; return 1 + max(findHeight(node.left), findHeight(node.right)); }
int getHeight(Node node) { if (node == null) return -1; return 1 + Math.max(getHeight(node.left), getHeight(node.right)); }
国际海事组织，你的代码将受益于简化一点。 当一个子指针为空时，不要试图结束recursion，而只能在当前指针为空时结束它。 这使得代码更容易编写。 在伪代码中，它看起来像这样：
if (node = null) return 0; else left = height(node->left); right = height(node->right); return 1 + max(left, right);
这里有一个简洁和希望正确的方式来expression它：
private int findHeight(TreeNode<T> aNode){ if(aNode == null || (aNode.left == null && aNode.right == null)) return 0; return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1; }
如果当前节点为空，则不存在树。 如果两个孩子都有，就有一个单层，这意味着0高度。 这使用高度的定义（由Stephen提到）作为层数 – 1
class Solution{ public static int getHeight(Node root) { int height = -1; if (root == null) { return height; } else { height = 1 + Math.max(getHeight(root.left), getHeight(root.right)); } return height; }
这是未经testing的，但相当明显是正确的：
private int findHeight（Treenode aNode）{
if（aNode.left == null && aNode.right == null）{
返回0; //是1; 显然没有孩子的节点的高度为0。
} else if（aNode.left == null）{
返回1 + findHeight（aNode.right）;
} else if（aNode.right == null）{
返回1 + findHeight（aNode.left）;
} else {
return 1 + max（findHeight（aNode.left），findHeight（aNode.right））;
}
}
通常简化你的代码比找出为什么closures它简单得多。 这段代码很容易理解：四种可能的情况明显地以正确的方式处理：
- 如果左边和右边的树都为空，则返回1，因为根据定义，单个节点的高度为1。
- 如果左树或右树（但不是两个！）为空，则返回非空树的高度加1以考虑当前节点的添加高度。
- 如果两个树都不为空，则返回较高子树的高度，再加一个用于当前节点的高度。
public void HeightRecursive() { Console.WriteLine( HeightHelper(root) ); } private int HeightHelper(TreeNode node) { if (node == null) { return -1; } else { return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode)); } }
C＃代码。 在BST类中包含这两个方法。 你需要两种方法来计算树的高度。 HeightHelper计算它，＆HeightRecursive在main（）中打印它。
对于像我这样喜欢一线解决scheme的人：
public int getHeight(Node root) { return Math.max(root.left != null ? getHeight(root.left) : -1, root.right != null ? getHeight(root.right) : -1) + 1; }
上面给出的高度定义是不正确的。 这是深度的定义。
“树中节点M的深度是从树根到M的path长度，树的高度比树中最深节点的深度大1深度d的所有节点都是在树中的第d级，根是0级的唯一节点，其深度为0。
引用 ：“数据结构和algorithm分析的实用介绍”第3.2版（Java版本）Clifford A. Shaffer弗吉尼亚理工学院计算机科学系弗吉尼亚理工大学Blacksburg，VA 24061
public int height(){ if(this.root== null) return 0; int leftDepth = nodeDepth(this.root.left, 1); int rightDepth = nodeDepth(this.root.right, 1); int height = leftDepth > rightDepth? leftDepth: rightDepth; return height; } private int nodeDepth(Node node, int startValue){ int nodeDepth = 0; if(node.left == null && node.right == null) return startValue; else{ startValue++; if(node.left!= null){ nodeDepth = nodeDepth(node.left, startValue); } if(node.right!= null){ nodeDepth = nodeDepth(node.right, startValue); } } return nodeDepth; }
我想这个问题可能意味着两件不同的事情…
-
高度是最长分支中的节点数量 ： –
int calcHeight(node* root){ if(root==NULL) return 0; int l=calcHeight(root->left); int r=calcHeight(root->right); if(l>r) return l+1; else return r+1; } -
高度是树本身中的节点总数 ：
int calcSize(node* root){ if(root==NULL) return 0; return(calcSize(root->left)+1+calcSize(root->right)); }
public int getHeight(Node node) { if(node == null) return 0; int left_val = getHeight(node.left); int right_val = getHeight(node.right); if(left_val > right_val) return left_val+1; else return right_val+1; }
这里是C＃中的解决scheme
private static int height_Tree(Node root) { if (root == null) { return 0; } int left = 1 + height_Tree(root.left); int right = 1 + height_Tree(root.right); return Math.Max(left, right); }
将tempHeight设置为静态variables（最初为0）。
static void findHeight（Node node，int count）{
if (node == null) { return; } if ((node.right == null) && (node.left == null)) { if (tempHeight < count) { tempHeight = count; } } findHeight(node.left, ++count); count--; //reduce the height while traversing to a different branch findHeight(node.right, ++count); }
这里有一个Java的解决scheme有点冗长，但工程..
public static int getHeight (Node root){ int lheight = 0, rheight = 0; if(root==null) { return 0; } else { if(root.left != null) { lheight = 1 + getHeight(root.left); System.out.println("lheight" + " " + lheight); } if (root.right != null) { rheight = 1+ getHeight(root.right); System.out.println("rheight" + " " + rheight); } if(root != null && root.left == null && root.right == null) { lheight += 1; rheight += 1; } } return Math.max(lheight, rheight); }
int getHeight(Node* root) { if(root == NULL) return -1; else return max(getHeight(root->left), getHeight(root->right)) + 1; }
//findBST的高度
int height(Node* root) { if(root == NULL){ return -1; } int sum=0; int rheight = height(root->right); int lheight = height(root->left); if(lheight>rheight){ sum = lheight +1; } if(rheight > lheight){ sum = rheight + 1; } return sum; }
对于任何读这个的人！
HEIGHT定义为从根节点到叶子节点的最长path中的节点数量。 因此：只有根节点的树的高度为1而不是0。
给定节点的LEVEL是从根加上1的距离。因此：根在1级，其子节点在2级，依此类推。
（信息由Data Structures提供：使用Java进行抽象和devise，第二版，Elliot B. Koffman和Paul AT Wolfgang编着） – 我正在哥伦布州立大学学习数据结构课程。
