이진 검색 트리에서 높이 찾기

이진 검색 트리에서 높이 찾기

---

이진 검색 트리의 높이를 찾기 위해이 방법을 다시 작업 할 수있는 사람이 있는지 궁금합니다. 지금까지 내 코드는 다음과 같습니다. 그러나 내가 얻는 대답은 실제 높이보다 1만큼 큽니다. 그러나 반환 진술에서 +1을 제거하면 실제 높이보다 1이 적습니다. 나는 여전히 재귀 주위에 머리를 감싸려고 노력하고 있습니다. 이 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;
    }
}

---

문제는 기본 케이스에 있습니다.

"트리의 높이는 루트에서 트리의 가장 깊은 노드까지의 경로 길이입니다. 노드 (루트) 만있는 (루팅 된) 트리의 높이는 0입니다." - 위키 백과

노드가없는 경우 0이 아닌 -1을 반환합니다. 이는 끝에 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;
    }
}

---

이진 검색 트리의 높이는입니다 number of layers - 1.

http://en.wikipedia.org/wiki/Binary_tree 의 다이어그램을 참조하십시오 .

재귀가 좋으므로 루트 수준에서 하나를 빼십시오.

또한 null 노드를 처리하여 함수를 약간 정리할 수 있습니다.

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));
}

---

IMO, 코드가 약간 단순화되면 이점이 있습니다. 자식 포인터가 null 일 때 재귀를 종료하려고 시도하는 대신 현재 포인터가 null 일 때만 종료합니다 . 따라서 코드 작성이 훨씬 간단 해집니다. 의사 코드에서는 다음과 같이 보입니다.

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

---

이것은 테스트되지 않았지만 분명히 정확합니다.

private int findHeight (Treenode aNode) {
  if (aNode.left == null && aNode.right == null) {
    반환 0; // 1이었다; 자식이없는 노드의 높이는 0입니다.
  } else if (aNode.left == null) {
    return 1 + findHeight (aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight (aNode.left);
  } else {
    return 1 + max (findHeight (aNode.left), findHeight (aNode.right));
  }
}

종종 코드를 단순화하는 것이 코드가 왜 하나씩 떨어져 있는지 알아내는 것보다 쉽습니다. 이 코드는 이해하기 쉽습니다. 네 가지 가능한 경우가 분명하게 올바른 방식으로 명확하게 처리됩니다.

• 왼쪽 트리와 오른쪽 트리가 모두 null이면 정의에 따라 단일 노드의 높이가 1이므로 1을 반환합니다.
• 왼쪽 또는 오른쪽 트리 (둘다는 아님)가 null이면 null이 아닌 트리의 높이에 1을 더하여 현재 노드의 추가 된 높이를 설명합니다.
• 두 트리 모두 null이 아니면 더 큰 하위 트리의 높이를 반환하고 현재 노드에 대해 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;
    }

---

한 줄 솔루션을 좋아하는 저와 같은 사람들을 위해 :

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}

---

다음은이를 표현하는 간결하고 올바른 방법입니다.

  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;
  }

현재 노드가 null이면 트리가 없습니다. 두 자식이 모두 있으면 단일 레이어가 있으며 이는 높이가 0임을 의미합니다. 이것은 높이의 정의 (Stephen이 언급 함)를 레이어 수-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 ()에 그것을 인쇄합니다.

---

위에 주어진 높이 정의가 잘못되었습니다. 그것이 깊이의 정의입니다.

" 트리에서 노드 M 의 깊이는 트리의 루트에서 M 까지의 경로 길이입니다 . 트리 의 높이는 트리에서 가장 깊은 노드의 깊이보다 하나 더 많습니다. 깊이 d의 모든 노드는 다음과 같습니다. 트리의 레벨 d 에서. 루트는 레벨 0의 유일한 노드이고 깊이는 0입니다. "

인용 : "데이터 구조 및 알고리즘 분석에 대한 실용적인 소개"Edition 3.2 (자바 버전) Clifford A. Shaffer 컴퓨터 과학과 Virginia Tech 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 height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

왼쪽과 오른쪽 하위 트리에서 최대 높이를 가져와 1을 더하면 기본 케이스도 처리됩니다 (노드가 1 개인 Tree의 높이는 0입니다).

---

이 질문은 두 가지 다른 의미를 가질 수 있습니다 ...

1. 높이는 가장 긴 분기의 노드 수입니다 .

   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; }

2. 높이는 트리 자체 의 총 노드 수입니다 .

   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;
}

---

tempHeight를 정적 변수 (처음에는 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 솔루션입니다 ..

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;
 }

---

// BST의 높이를 찾는 함수

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;
}

---

다음은 C #의 솔루션입니다.

    private static int heightOfTree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + heightOfTree(root.left);
        int right = 1 + heightOfTree(root.right);

        return Math.Max(left, right);
    }

---

이것을 읽는 다른 사람을 위해 !!!!

HEIGHT는 루트 노드에서 리프 노드까지 가장 긴 경로에있는 노드 수로 정의됩니다. 따라서 루트 노드 만있는 트리의 높이는 0이 아니라 1입니다.

주어진 노드의 LEVEL은 루트에서 1을 더한 거리입니다. 따라서 루트는 레벨 1에 있고 하위 노드는 레벨 2에 있습니다.

(Information courtesy of Data Structures: Abstraction and Design Using Java, 2nd Edition, by Elliot B. Koffman & Paul A. T. Wolfgang) - Book used in Data Structures Course I am currently taking at Columbus State University.

---

enter image description here

According to "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, following is the definition of tree height:

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf, and the height of a tree is the height of its root. The height of a tree is also equal to the largest depth of any node in the tree.

Following is my ruby solution. Most of the people forgot about height of empty tree or tree of single node in their implementation.

def height(node, current_height)
  return current_height if node.nil? || (node.left.nil? && node.right.nil?)
  return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
  return height(node.left, current_height + 1) if node.left
  return height(node.right, current_height + 1)
end

---

int maxDepth(BinaryTreeNode root) {
    if(root == null || (root.left == null && root.right == null)) {
       return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

ReferenceURL : https://stackoverflow.com/questions/2597637/finding-height-in-binary-search-tree