Puis-je effectuer une traversée inorder d'un arbre binaire sans récursion ni pile?

Question

Quelqu'un peut-il me donner une solution pour traverser un arbre binaire en ordre sans récursivité et sans utiliser de pile?

Answer 1

Deuxième édition: I pense que c'est juste. Requiert node.isRoot, node.isLeftChild et node.parent, en plus des nœuds node.left_child et node.right_child habituels.

state = "from_parent" 
current_node = root 
while (!done) 
    switch (state) 
    case "from_parent": 
     if current_node.left_child.exists 
     current_node = current_node.left_child 
     state = "from_parent" 
     else 
     state = "return_from_left_child" 
    case "return_from_left_child" 
     if current_node.right_child.exists 
     current_node = current_node.right_child 
     state = "from_parent" 
     else 
     state = "return_from_right_child" 
    case "return_from_right_child" 
     if current_node.isRoot 
     done = true 
     else 
     if current_node.isLeftChild 
     state = "return_from_left_child" 
     else 
     state = "return_from_right_child" 
     current_node = current_node.parent 

Answer 2

Étant donné que traverser un binary tree nécessite un certain type d'état (les noeuds à retourner après la visite des successeurs) qui pourrait être fourni par la pile impliquée par la récursivité (ou explicite par un tableau).

La réponse est non, vous ne pouvez pas. (Selon la définition classique)

La chose la plus proche à un traversal arbre binaire de manière itérative utilise probablement une heap

EDIT: Ou comme cela a déjà montré une threaded binary tree,

Answer 3

Oui, vous pouvez. Pour ce faire, vous auriez besoin d'un pointeur parent pour monter dans l'arbre.

Answer 4

Comme quelqu'un l'a déjà dit, c'est possible, mais pas sans le pointeur parent. Le pointeur parent vous permet fondamentalement de parcourir "le chemin" si vous le souhaitez, et donc d'imprimer les nœuds. Mais pourquoi la récursivité fonctionne-t-elle sans pointeur parent? Eh bien, si vous comprenez récursivité il va quelque chose comme ça (imaginez la pile de récursion):

recursion //going into 
    recursion 
    recursion 
    recursion 
    recursion //going back up 
    recursion 
    recursion 
    recursion 

Alors, quand alors récursion se termine, vous avez imprimé le côté choisi de l'arbre binaire dans l'ordre inverse.

Answer 5

Commencez par tree_first(), continuez avec tree_next() jusqu'à obtenir NULL. code complet: https://github.com/virtan/tree_closest

struct node { 
    int value; 
    node *left; 
    node *right; 
    node *parent; 
}; 

node *tree_first(node *root) { 
    while(root && root->left) 
     root = root->left; 
    return root; 
} 

node *tree_next(node *p) { 
    if(p->right) 
     return tree_first(p->right); 
    while(p->parent) { 
     if(!p->parent->right || p->parent->right != p) 
      return p->parent; 
     else p = p->parent; 
    } 
    return 0; 
}