Прелазак дрвета

У овом упутству ћете научити о различитим техникама преласка дрвета. Такође ћете наћи радне примере различитих метода за прелажење стабала у Ц, Ц ++, Јава и Питхон.

Прећи дрво значи посетити сваки чвор на дрвету. На пример, можда желите да додате све вредности у дрвету или да пронађете највећу. За све ове операције мораћете да посетите сваки чвор стабла.

Линеарне структуре података попут низова, стекова, редова и повезане листе имају само један начин за читање података. Али хијерархијска структура података попут дрвета може се прелазити на различите начине.

Прелазак дрвета

Размислимо о томе како можемо читати елементе дрвета на слици приказаној горе.

Почевши од врха, Лево надесно

 1 -> 12 -> 5 -> 6 -> 9

Почевши од дна, лево надесно

 5 -> 6 -> 12 -> 9 -> 1

Иако је овај поступак донекле лак, он не поштује хијерархију стабла, већ само дубину чворова.

Уместо тога, користимо методе преласка које узимају у обзир основну структуру стабла, тј

 struct node ( int data; struct node* left; struct node* right; )

Структурни чвор на који указују лево и десно могу имати и другу леву и десну децу, па бисмо о њима требали размишљати као о подстаблима, а не о под чворовима.

Према овој структури, свако дрво је комбинација

  • Чвор који носи податке
  • Два подстабла
Лево и Десно подстабло

Имајте на уму да је наш циљ да посетимо сваки чвор, тако да морамо да посетимо све чворове у подстаблу, посетимо коријенски чвор и такође посетимо све чворове у десном подстаблу.

У зависности од редоследа којим ово радимо, могу постојати три врсте преласка.

Унутрашња обилазница

  1. Прво посетите све чворове у левом подстаблу
  2. Затим коренски чвор
  3. Посетите све чворове у десном подстаблу
 inorder(root->left) display(root->data) inorder(root->right)

Прелазак унапред

  1. Посетите роот чвор
  2. Посетите све чворове у левом подстаблу
  3. Посетите све чворове у десном подстаблу
 display(root->data) preorder(root->left) preorder(root->right)

Прелазак поштарине

  1. Посетите све чворове у левом подстаблу
  2. Посетите све чворове у десном подстаблу
  3. Посетите основни чвор
 postorder(root->left) postorder(root->right) display(root->data)

Визуелизујмо прелазак по редоследу. Полазимо од коренског чвора.

Лево и Десно подстабло

Прво прелазимо лево подстабло. Такође морамо имати на уму да посетимо основни чвор и право подстабло када је ово стабло завршено.

Ставимо све ово у хрпу да се сећамо.

Гомила

Сада прелазимо до подстабла упереног на ВРХ стека.

Опет, следимо исто правило инордер

 Лево подстабло -> роот -> десно подстабло

После преласка левог подстабла, преостаје нам

Финал Стацк

Будући да чвор "5" нема ниједно подстабло, ми га директно исписујемо. После тога исписујемо његов родитељ „12“, а затим право дете „6“.

Стављање свега у стек било је корисно јер сада, када је пређено лево подстабло основног чвора, можемо га одштампати и прећи на десно подстабло.

Након проласка кроз све елементе, добијамо унутрашњи заокрет као

 5 -> 12 -> 6 -> 1 -> 9

Не морамо сами да стварамо стек, јер рекурзија одржава исправан редослед за нас.

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц + 
 # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
 // Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
 // Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
 // Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);

Занимљиви Чланци...