У овом чланку ћемо разговарати о обиласку стабла у структури података. Термин 'прелазак стабла' значи обилазак или посету сваком чвору дрвета. Постоји један начин да се пређе линеарна структура података као што су повезана листа, ред и стек. Док постоји више начина да се пређе дрво које су наведене на следећи начин -
- Преордер траверсал
- Инордер траверсал
- Промет поштанских налога
Дакле, у овом чланку ћемо разговарати о горе наведеним техникама преласка дрвета. Сада, почнимо да разговарамо о начинима преласка стабала.
Преордер траверсал
Ова техника прати политику 'корен лево десно'. То значи да се први коренски чвор посећује након тога се рекурзивно прелази лево подстабло, а на крају се рекурзивно прелази десно подстабло. Како се основни чвор прелази пре (или пре) левог и десног подстабла, то се назива прелазак преко реда.
Дакле, у обиласку унапред, сваки чвор се посећује пре оба његова подстабла.
Примене преласка наруџбине укључују -
- Користи се за креирање копије дрвета.
- Такође се може користити за добијање префиксног израза стабла израза.
Алгоритам
Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively.
Пример
Сада, хајде да видимо пример технике преласка у претпродаји.
Сада почните да примењујете прелазак наруџбине на горе наведено стабло. Прво прелазимо преко коренског чвора А; након тога, пређите на његово лево подстабло Б , који ће се такође прећи у претпродаји.
Дакле, за лево подстабло Б, прво, коренски чвор Б сама се прелази; након тога, његово лево подстабло Д је пређено. Пошто чвор Д нема деце, помери се на десно подстабло И . Пошто чвор Е такође нема деце, обилазак левог подстабла коренског чвора А је завршен.
класа против објекта у Јави
Сада се померите према десном подстаблу коренског чвора А који је Ц. Дакле, за десно подстабло Ц, прво коренски чвор Ц прешао сам себе; након тога, његово лево подстабло Ф је пређено. Пошто чвор Ф нема деце, помери се на десно подстабло Г . Пошто чвор Г такође нема деце, обилазак десног подстабла коренског чвора А је завршен.
логика преноса регистра
Због тога се прелазе сви чворови дрвета. Дакле, резултат преласка преко претходног стабла је -
А → Б → Д → Е → Ц → Ф → Г
Да бисте сазнали више о обиласку преднаруџбине у структури података, можете пратити везу Преордер траверсал .
Промет поштанских налога
Ова техника прати политику 'лево-десно корен'. То значи да се прелази преко првог левог подстабла коренског чвора, након тога се рекурзивно прелази преко десног подстабла и на крају се прелази преко коренског чвора. Пошто се основни чвор прелази после (или пост) левог и десног подстабла, то се назива обилазак постордера.
Дакле, у обиласку постордера, сваки чвор се посећује после оба његова подстабла.
Примене постордер траверсал укључују -
- Користи се за брисање стабла.
- Такође се може користити за добијање постфиксног израза стабла израза.
Алгоритам
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node.
Пример
Сада, да видимо пример технике преласка постордера.
Сада почните да примењујете прелазак постордера на горе наведено дрво. Прво, прелазимо лево подстабло Б које ће бити пређено у постордеру. Након тога ћемо прећи десно подстабло Ц ин постордер. И коначно, коренски чвор горњег стабла, тј. А , прелази се.
Дакле, за лево подстабло Б, прво, његово лево подстабло Д је пређено. Пошто чвор Д нема деце, пређите десно подстабло И . Пошто чвор Е такође нема деце, пређите на основни чвор Б. Након преласка чвора Б, обилазак левог подстабла коренског чвора А је завршен.
Сада, померите се према десном подстаблу коренског чвора А који је Ц. Дакле, за десно подстабло Ц, прво његово лево подстабло Ф је пређено. Пошто чвор Ф нема деце, пређите десно подстабло Г . Како чвор Г такође нема деце, стога, коначно, коренски чвор десног подстабла, тј. Ц, је пређено. Прелазак десног подстабла коренског чвора А је завршен.
Најзад, пређите преко коренског чвора датог дрвета, тј. А . Након преласка преко коренског чвора, постордер обилазак датог стабла је завршен.
Због тога се прелазе сви чворови дрвета. Дакле, резултат преласка постордер-а преко горњег дрвета је -
Д → Е → Б → Ф → Г → Ц → А
гит додај све
Да бисте сазнали више о обиласку постордера у структури података, можете пратити везу Промет поштанских налога .
Инордер траверсал
Ова техника прати политику 'левог корена десно'. То значи да се прво лево подстабло посећује након што се пређе преко тог коренског чвора, а на крају се обиђе десно подстабло. Пошто се коренски чвор прелази између левог и десног подстабла, он се назива прелазак у нередовном реду.
Дакле, у обиласку у нередовном реду, сваки чвор се посећује између његових подстабала.
Примене Инордер траверсал укључују -
- Користи се за добијање БСТ чворова у растућем редоследу.
- Такође се може користити за добијање префиксног израза стабла израза.
Алгоритам
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively.
Пример
Сада, хајде да видимо пример технике преласка Инордер-а.
Сада почните да примењујете прелазак у редослед на горе наведено дрво. Прво прелазимо лево подстабло Б који ће се прећи у редоследу. Након тога ћемо прећи преко коријенског чвора А . И коначно, право подстабло Ц прелази се у редоследу.
Дакле, за лево подстабло Б , прво, његово лево подстабло Д је пређено. Пошто чвор Д нема деце, па након што га пређе, чвор Б биће пређено, и коначно, десно подстабло чвора Б, тј И , прелази се. Чвор Е такође нема деце; дакле, обилазак левог подстабла коренског чвора А је завршен.
питхон рстрип
Након тога, пређите преко коренског чвора датог дрвета, тј. А .
Најзад, померите се ка десном подстаблу коренског чвора А који је Ц. Дакле, за десно подстабло Ц; прво, његово лево подстабло Ф је пређено. Пошто чвор Ф нема деце, чвор Ц биће пређено, и коначно, десно подстабло чвора Ц, тј. Г , прелази се. Чвор Г такође нема деце; дакле, обилазак десног подстабла коренског чвора А је завршен.
Како су сви чворови стабла пређени, обилазак датог дрвета је завршен. Излаз нередовног обиласка горњег стабла је -
Д → Б → Е → А → Ф → Ц → Г
Да бисте сазнали више о нередовном обиласку у структури података, можете пратити везу Инордер Траверсал .
Сложеност техника преласка дрвета
Временска сложеност техника преласка стабла о којима се говорило је На) , где 'н' је величина бинарног стабла.
Док је просторна сложеност техника преласка стабала о којима је било речи горе О(1) ако не узмемо у обзир величину стека за позиве функција. Иначе, просторна сложеност ових техника је О(х) , где 'х' је висина дрвета.
Имплементација преласка стабла
Сада, хајде да видимо имплементацију горе описаних техника користећи различите програмске језике.
Програм: Напишите програм за имплементацију техника преласка стабла у Ц.
апстрактне методе
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Излаз
Програм: Напишите програм за имплементацију техника преласка стабла у Ц#.
using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } Излаз
Програм: Напишите програм за имплементацију техника преласка стабла у Ц++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println('
'); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> Излаз
Након извршења горњег кода, излаз ће бити -
Закључак
У овом чланку смо дискутовали о различитим типовима техника преласка стабла: прелазак по наруџбини, прелазак у редослед и обилазак после. Видели смо ове технике заједно са алгоритмом, примером, сложеношћу и имплементацијом у Ц, Ц++, Ц# и Јави.
Дакле, то је све о чланку. Надам се да ће вам бити од помоћи и информација.