V tej vadnici boste spoznali različne tehnike prečkanja dreves. Prav tako boste našli delovne primere različnih načinov prečkanja dreves v C, C ++, Java in Python.
Prehod drevesa pomeni obisk vsakega vozlišča v drevesu. Morda boste na primer želeli dodati vse vrednosti v drevesu ali najti največjo. Za vse te operacije boste morali obiskati vsako vozlišče drevesa.
Linearne podatkovne strukture, kot so nizi, skladi, čakalne vrste in povezani seznam, imajo samo en način za branje podatkov. Toda hierarhično strukturo podatkov, kot je drevo, je mogoče prehoditi na različne načine.
Prehod dreves
Pomislimo, kako lahko beremo elemente drevesa na zgornji sliki.
Začenši od zgoraj, od leve proti desni
1 -> 12 -> 5 -> 6 -> 9
Od spodaj levo desno
5 -> 6 -> 12 -> 9 -> 1
Čeprav je ta postopek nekoliko enostaven, ne spoštuje hierarhije drevesa, temveč le globino vozlišč.
Namesto tega uporabljamo metode prečkanja, ki upoštevajo osnovno strukturo drevesa, tj
struct node ( int data; struct node* left; struct node* right; )
Vozlišče struct, na katero kažeta leva in desna, ima lahko druge leve in desne podrejene otroke, zato bi jih morali imeti kot poddrevesa namesto kot podvozla.
V skladu s to strukturo je vsako drevo kombinacija
- Vozlišče s podatki
- Dve drevesi
Levo in desno poddrevo
Ne pozabite, da je naš cilj obiskati vsako vozlišče, zato moramo obiskati vsa vozlišča v poddrevesu, obiskati korensko vozlišče in obiskati tudi vsa vozlišča v desnem poddrevesu.
Glede na vrstni red, v katerem to počnemo, lahko obstajajo tri vrste prečkanja.
Notranji prehod
- Najprej obiščite vsa vozlišča v levem poddrevesu
- Nato korensko vozlišče
- Obiščite vsa vozlišča v desnem poddrevesu
inorder(root->left) display(root->data) inorder(root->right)
Prehod pred naročilom
- Obiščite korensko vozlišče
- Obiščite vsa vozlišča v levem poddrevesu
- Obiščite vsa vozlišča v desnem poddrevesu
display(root->data) preorder(root->left) preorder(root->right)
Prehod po naročilu
- Obiščite vsa vozlišča v levem poddrevesu
- Obiščite vsa vozlišča v desnem poddrevesu
- Obiščite korensko vozlišče
postorder(root->left) postorder(root->right) display(root->data)
Predstavljajmo si prehod po vrstnem redu. Začnemo od korenskega vozlišča.
Levo in desno poddrevo
Najprej prehodimo levo poddrevo. Ko je to drevo končano, si moramo zapomniti tudi obisk korenskega vozlišča in desnega poddrevesa.
Dajmo vse to v kup, da se bomo spomnili.
Stack
Zdaj preidemo na poddrevo, usmerjeno na VRH sklada.
Spet sledimo istemu pravilu inorderja
Levo poddrevo -> koren -> desno poddrevo
Po prehodu levega poddrevesa nam ostane
Končni kup
Ker vozlišče "5" nima nobenega poddrevesa, ga natisnemo neposredno. Nato natisnemo njegov nadrejeni "12" in nato pravega otroka "6".
Dati vse v sklad je bilo koristno, ker zdaj, ko je prehodno levo poddrevo korenskega vozlišča prepisano, ga lahko natisnemo in gremo v desno poddrevo.
Po prehodu skozi vse elemente dobimo prehod v vrstnem redu kot
5 -> 12 -> 6 -> 1 -> 9
Ni nam treba ustvariti sklada sami, ker rekurzija ohranja pravilen vrstni red za nas.
Primeri Python, Java in C / C ++
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);
