Les traverser dans l'inadorder et le niveler pour un arbre binaire ainsi que le nombre total de nœuds sont donnés dans une définition de fonction, nous devons calculer la hauteur minimale de l'arborescence binaire pour les entrées données.
pouvons-nous calculer sans construire le arbre? par exemple et attendu O / P était
{4,2,5,1,6,3,7} ,
{1,2,3,4,5,6,7} , n = 7 .
3
5 Réponses :
une approche très simple consiste à construire l'arbre puis à trouver sa hauteur.
Supposons que la structure du nœud soit: Nœud struct { clé int; struct Node * gauche, * droite; };
Node* **newNode**(int key)
{
Node *node = (Node *)malloc(sizeof(Node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
int **getHeight**(Node* root){
if(root==NULL) return 0;
return max(getHeight(root->left)+1,getHeight(root->right)+1);
}
Node* **getNode**(Node* root,int key){
if(root!=NULL){
if(root->key == key) return root;
return getNode(root->left,key) != NULL ? getNode(root->left,key):
getNode(root->right,key);
}
}
void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
Node* head = newNode(levelOrder[0]);
i++;
int comp = 0;
while(i<j){
int key = levelOrder[comp];
Node* ptr = getNode(head,key);
int k = n-1;
while(k>=0 && inorder[k]!=key) k--;
if(k>0 && inorder[k-1]!=-1){
ptr->left = newNode(levelOrder[i]);
i++;
}
if(k<n-1 && inorder[k+1]!=-1){
ptr->right = newNode(levelOrder[i]);
i++;
}
inorder[k] = -1;
comp++;
}
int height = getHeight(head);
**cout<<height<<" ";**
}
Le code consiste à construire l'arbre à l'aide des deux tableaux, puis à calculer la hauteur minimale, ce que j'avais fait dans le test. Je me demandais de calculer la hauteur sans construction d'arbre: /
oui, vous pouvez faire même sans construire l'arbre, j'ai collé ce code aussi.
yes, you can do that without even constructing the tree.
for that use two queue.
see given below code for better understanding.
void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
queue<int>q1,q2;
q1.push(levelOrder[0]);
int k = 1,height = 0;
while(!q1.empty() || !q2.empty()){
if(!q1.empty()) height++;
while(!q1.empty()){
int val = q1.front();
for(int i = 0;i<n;++i){
if(inorder[i] == val) break;
}
if(i>0 && inorder[i-1] !=-1 && k<n)
q2.push(levelOrder[k++]);
if(i<n-1 && inorder[i+1] !=-1 && k<n)
q2.push(levelOrder[k++]);
inorder[i] = -1;
q1.pop();
}
if(!q2.empty()) height++;
while(!q2.empty()){
int val = q2.front();
for(int i = 0;i<n;++i){
if(inorder[i] == val) break;
}
if(i>0 && inorder[i-1] !=-1 && k<n)
q1.push(levelOrder[k++]);
if(i<n-1 && inorder[i+1] !=-1 && k<n)
q1.push(levelOrder[k++]);
inorder[i] = -1;
q2.pop();
}
}
cout<<height<<endl;
}
La hauteur minimale possible d'un arbre binaire est log2 (n + 1) , où n est le nombre de nœuds.
L'extrait de code ci-dessous calculerait la hauteur de l'arbre sans le construire.
#include <iostream>
#include <queue>
using namespace std;
int minHeight(int inOrder[], int levelOrder[], int n)
{
int i=1;
queue<int>q1,q2;
q1.push(levelOrder[0]);
int k = 1,height = 0;
while(!q1.empty() || !q2.empty()){
if(!q1.empty()) height++;
while(!q1.empty()){
int val = q1.front();
for(int i = 0;i<n;++i){
if(inOrder[i] == val) break;
}
if(i>0 && inOrder[i-1] !=-1 && k<n)
q2.push(levelOrder[k++]);
if(i<n-1 && inOrder[i+1] !=-1 && k<n)
q2.push(levelOrder[k++]);
inOrder[i] = -1;
q1.pop();
}
if(!q2.empty()) height++;
while(!q2.empty()){
int val = q2.front();
for(int i = 0;i<n;++i){
if(inOrder[i] == val) break;
}
if(i>0 && inOrder[i-1] !=-1 && k<n)
q1.push(levelOrder[k++]);
if(i<n-1 && inOrder[i+1] !=-1 && k<n)
q1.push(levelOrder[k++]);
inOrder[i] = -1;
q2.pop();
}
}
return height;
}
int main()
{
int inOrder[] = {4,2,5,1,6,3,7}; //input1
int levelOrder[] = {1,2,3,4,5,6,7}; //input2
int n=sizeof(inOrder)/sizeof(int); ////input3
cout<<minHeight(inOrder, levelOrder, n)<<endl;
return 0;
}
Question: Si la traversée par ordre et par niveau d'un arbre est donnée, quelle est la hauteur minimale de l'arbre
Exemple 1:
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
def buildTree(level, ino):
if ino:
for i in range(0, len(level)):
if level[i] in ino:
node = Node(level[i])
io_index = ino.index(level[i])
break
if not ino:
return node
node.left = buildTree(level, ino[0:io_index])
node.right = buildTree(level, ino[io_index + 1:len(ino)])
return node
def height(root):
if root is None:
return 0
else:
return max(height(root.left),height(root.right))+1
#This is the function you have to write
def minHeight(input1,input2,input3):
global root
root = buildTree(input1, input2)
return height(root)
inorder = [4,2,5,1,6,3,7]
levelorder = [1,2,3,4,5,6,7]
print("height : ",minHeight(levelorder,inorder,len(inorder)))