Реализация методов дерева дерева

Question

Я должен реализовать рекурсивные методы для двоичного дерева и хотел бы проверить, правильно ли реализованы методы, которые я написал, поскольку я не могу их протестировать. Это не фактические методы. Мне просто нужно написать псевдокод алгоритма.

а) граф числа узлов в дереве

countNodes(TreeNode root){ 
    if(root == null) 
     return 0; 
    else{ 
     TreeNode left = root.getLeftChild(); 
     TreeNode right = root.getRightChild(); 
     return (countNodes(left)+countNodes(right)) + 1; 
    } 
} 

б) Вычислить высоту дерева

height(TreeNode root){ 
    if(root == null) 
     return 0; 
    else{ 
     return Math.max(height(root.getLeftChild()), height(root.getRightChild()) +1; 
    } 
} 

с) Найти максимальный элемент

maxElem(TreeNode root){ 
    if(root == null) 
     return 0; 
    else{ 
     int temp = 0; 
     temp = Math.max(maxElem(root.getLeftChild()), maxElem(root.getRightChild())); 
     return Math.max(root.getValue, temp); 
    } 
} 

d) Найти сумму элементов

sum(TreeNode root){ 
    if(root == null) 
     return 0; 
    else{ 
     return (sum(root.getLeftChild()) + sum(root.getRightChild())) + root.getValue(); 
    } 
} 

е) Найти среднее значение элементов

average(TreeNode root){ 
    int sum = sum(root); 
    int elems = countNodes(root); 
    return sum/elems; 
} 

е) Найти конкретный пункт

search(int i, TreeNode root){ 
    if(root == null) 
     return false; 
    else if(root.getValue == i) 
     return true; 
    else{ 
     search(i, root.getLeftChild); 
     search(i, root.getRightChild); 
    } 
} 

г) Определите элемент, является ли предком другого

isAncestor(TreeNode p, NodeNode c){ 
    if(p==null) 
     return false; 
    else 
     return (c in p.getLeftChild() || c in p.getRightChild()) 
} 

h) Определите самый высокий уровень, который заполнен

maxFull(TreeNode root) 
    if(root == null) 
     return 0; 
    else{ 
     return(numNodes in level h == 2^h - 1) 
    } 
} 

Answer 1

Есть несколько незначительных вопросов:

1) asMTilsted предлагает, если ваше дерево содержит только отрицательные значения, maxElem не работает
2) Среднее значение не может быть правильным, так как это является INT, а не двойной , попробуйте наброски типов на сумму и количество элементов дерева, а затем верните их коэффициент.
3) в вашем поиске функции вы ничего не возвращаете в последнем заявлении else. Попробуйте: return search(i, root.getLeftChild()) || search(i, root.getRightChild()); (также в остальной части вашего кода это ФУНКЦИИ, а не атрибуты ...

для остальные это кажется хорошо :)

Answer 2

Ваш метод MaxElm неверен. Он не будет работать, если все элементы имеют отрицательное значение.

Answer 3

Я должен реализовать рекурсивные методы для двоичного дерева и хотел бы увидеть, правильно ли реализованы методы, которые я написал, поскольку я не могу их протестировать. Это не фактические методы. Мне просто нужно написать псевдокод алгоритма.

Вы можете проверить их.

Напишите их как настоящий код в (скажем) Java, напишите некоторые модульные тесты, запустите их.

Если материал, который Вы должны представить в конце дня является псевдо-код не реальный код, то вы можете вручную перевести Java обратно в псевдокоде ...

---

Строго говоря, вам не может сказать, является ли псевдокод правильным, если вы не указали, что означает псевдокод.