Šioje pamokoje sužinosite apie įvairias medžių perėjimo technikas. Taip pat rasite skirtingų medžių perėjimo metodų C, C ++, Java ir Python pavyzdžių.
Keliauti medžiu reiškia aplankyti kiekvieną medžio mazgą. Pavyzdžiui, galite pridėti visas medžio reikšmes arba rasti didžiausią. Atlikdami visas šias operacijas turėsite aplankyti kiekvieną medžio mazgą.
Linijinės duomenų struktūros, tokios kaip masyvai, kaminai, eilės ir susietas sąrašas, turi tik vieną būdą duomenims nuskaityti. Tačiau hierarchinę duomenų struktūrą, pavyzdžiui, medį, galima kirsti įvairiai.
Medžių perėjimas
Pagalvokime, kaip mes galime perskaityti medžio elementus aukščiau pateiktame paveikslėlyje.
Pradedant nuo viršaus, iš kairės į dešinę
1 -> 12 -> 5 -> 6 -> 9
Pradedant nuo apačios, iš kairės į dešinę
5 -> 6 -> 12 -> 9 -> 1
Nors šis procesas yra šiek tiek lengvas, jis nepaiso medžio hierarchijos, tik mazgų gylio.
Vietoj to, mes naudojame perėjimo metodus, kurie atsižvelgia į pagrindinę medžio struktūrą, t
struct node ( int data; struct node* left; struct node* right; )
Struktūrinis mazgas, į kurį nukreipta kairė ir dešinė, gali turėti kitų kairiųjų ir dešiniųjų vaikų, todėl turėtume juos galvoti kaip apie medžius, o ne po mazgus.
Pagal šią struktūrą kiekvienas medis yra derinys
- Mazgas, nešantis duomenis
- Du potemiai
Kairysis ir dešinysis potisiai
Atminkite, kad mūsų tikslas yra aplankyti kiekvieną mazgą, todėl turime aplankyti visus mazgo medžius, aplankyti šakninį mazgą ir aplankyti visus mazgus dešiniajame potemyje.
Priklausomai nuo to, kokia tvarka mes tai darome, gali būti trijų rūšių perėjimas.
Užsakymo perėjimas
- Pirmiausia aplankykite visus kairiojo potemio mazgus
- Tada šaknies mazgas
- Aplankykite visus mazgus dešiniajame poskyryje
inorder(root->left) display(root->data) inorder(root->right)
Iš anksto užsisakyti
- Apsilankykite šakniniame mazge
- Aplankykite visus mazgo kairiojo poskyrio mazgus
- Aplankykite visus mazgus dešiniajame poskyryje
display(root->data) preorder(root->left) preorder(root->right)
Pašto pervažiavimas
- Aplankykite visus mazgo kairiojo poskyrio mazgus
- Aplankykite visus mazgus dešiniajame poskyryje
- Apsilankykite šaknies mazge
postorder(root->left) postorder(root->right) display(root->data)
Vizualizuokime tvarkingą perėjimą. Mes pradedame nuo šaknies mazgo.
Kairysis ir dešinysis potisiai
Pirmiausia kertame kairįjį potemį. Taip pat turime nepamiršti aplankyti šaknies mazgą ir dešinįjį medį, kai šis medis bus padarytas.
Įdėkime visa tai į kaminą, kad prisimintume.
Sukrauti
Dabar mes einame į poskyrį, nukreiptą į kamino viršų.
Vėlgi laikomės tos pačios tvarkos
Kairysis potis -> šaknis -> dešinysis potis
Perėję kairįjį potvynį, mes likome su
Galutinis krūva
Kadangi mazge „5“ nėra potemių, jį spausdiname tiesiogiai. Po to atspausdiname jo tėvą „12“, o tada tinkamą vaiką „6“.
Visko įdėjimas į rietuvę buvo naudingas, nes dabar, kai perėjo šaknies mazgo kairysis pogrindis, galime jį atspausdinti ir pereiti prie dešiniojo pogrindžio.
Perėję visus elementus, mes gauname vidinį perėjimą kaip
5 -> 12 -> 6 -> 1 -> 9
Mums nereikia patiems kurti kamino, nes rekursija palaiko mums tinkamą tvarką.
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„Python Java C C +“ # 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);
