Giv et binært træ og skriv en iterativ og rekursiv løsning til at gennemløbe træet ved hjælp af inorder traversal i C++, Java og Python.
I modsætning til linkede lister, endimensionale arrays og andre lineære datastrukturer, som gennemløbes i lineær rækkefølge, kan træer gennemløbes på flere måder i dybde-første rækkefølge (preorder, inorder og postorder) eller bredde-første rækkefølge (level order traversal). Ud over disse grundlæggende traverseringer er forskellige mere komplekse eller hybride ordninger mulige, f.eks. dybdebegrænsede søgninger som f.eks. iterativ uddybende dybdeførste søgning. I dette indlæg behandles inorder tree traversal i detaljer.
Traversering af et træ indebærer iterering over alle knuder på en eller anden måde. Da træet ikke er en lineær datastruktur, kan der være mere end én mulig næste knude fra en given knude, så nogle knuder skal udskydes, dvs. gemmes på en eller anden måde for senere at blive besøgt. Traverseringen kan foregå iterativt, hvor de udskudte knuder gemmes i stakken, eller den kan foregå ved rekursion, hvor de udskudte knuder gemmes implicit i kaldestakken.
For at traversere et (ikke-tomt) binært træ på en inorder måde, skal vi gøre disse tre ting for hver knude n startende fra træets rod:
(L) Recursivt traverse dets venstre undertræ. Når dette trin er afsluttet, er vi tilbage ved n igen.(N) Behandler n selv.(R) Gennemgår rekursivt dens højre undertræ. Når dette trin er afsluttet, er vi tilbage ved n igen.I normal inorder traversal besøger vi den venstre undertræ før den højre undertræ. Hvis vi besøger det højre undertræ før vi besøger det venstre undertræ, kaldes det reverse inorder traversal.
Som vi kan se, behandles det venstre undertræ først, før vi behandler en hvilken som helst knude, efterfulgt af knuden, og det højre undertræ behandles til sidst. Disse operationer kan defineres rekursivt for hver enkelt knude. Den rekursive implementering kaldes en DFS (Depth-first search), da søgetræet uddybes så meget som muligt på hvert barn, før man går til den næste søskende.
Følgende er C++, Java og Python-programmet, der demonstrerer det:
Iterativ implementering –
For at konvertere ovenstående rekursive procedure til en iterativ procedure, har vi brug for en eksplicit stak. Nedenfor er en simpel stakbaseret iterativ algoritme til at udføre inorder traversal.
iterativInorder(node)
Algoritmen kan implementeres på følgende måde i C++, Java og Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Iterativ funktion til at udføre inorder-traversal på træet
void inorderIterative(Node *root)
{
// opretter en tom stak
stack<Node*> stack;
// start fra rodknuden (sæt den aktuelle knude til rodknuden)
Node *curr = root;
// hvis den aktuelle knude er nul og stakken også er tom, er vi færdige
while (!stack.empty() || curr != nullptr)
{
// hvis den aktuelle node findes, skubbes den ind i stakken (udsætter den)
// og flyttes til dens venstre underordnede
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// ellers, hvis den aktuelle knude er nul, pop et element fra stakken,
// udskriv det, og sæt endelig den aktuelle knude til dens højre barn
curr = stack.top();
stack.pop();
cout << curr->data <<< ” “;
curr = curr->right;
}
}
}
|
Download Kør komplet kode
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Iterativ funktion til at udføre inorder-traversal på træet
public static void inorderIterative(TreeNode root)
{
// opretter en tom stak
Stack<TreeNode> stack = new Stack();
// start fra rodknuden (sæt den aktuelle knude til rodknuden)
TreeNode curr = root;
// hvis den aktuelle knude er nul, og stakken også er tom, er vi færdige
while (!stack.empty() || curr != null)
{
// hvis den aktuelle node findes, skubbes den ind i stakken (udsætter den)
// og flyttes til dens venstre underordnede
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// ellers, hvis den aktuelle knude er nul, pop et element fra stakken,
// udskriv det, og sæt til sidst den aktuelle knude til dens højre barn
curr = stack.pop();
System.out.print(curr.data + ” “);
curr = curr.right;
}
}
}
|
Download Kør komplet kode
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Iterativ funktion til at udføre inorder traversal på træet
def inorderIterative(root):
# opretter en tom stak
stak = deque()
# starter fra rodknuden (sæt aktuel knude til rodknuden)
curr = root
# hvis den aktuelle knude er None og stakken også er tom, er vi færdige
while stack or curr:
# hvis den aktuelle knude findes, skubbes den ind i stakken (udsætter den)
# og flyttes til dens venstre barn
if curr:
stack.append(curr)
curr = curr.left
else:
# ellers, hvis den aktuelle knude er None, pop et element fra stakken,
# udskriv det, og sæt til sidst den aktuelle knude til dens højre barn
curr = stack.pop()
print(curr.data, end=’ ‘ ‘)
curr = curr.right
|
Download Kør komplet kode
Den tidskompleksitet for ovenstående løsninger er O(n), hvor n er det samlede antal knuder i det binære træ. Programmets rumkompleksitet er O(n), da den nødvendige plads er proportional med træets højde, som kan være lig med det samlede antal knuder i træet i værste tilfælde for skæve træer.