Genom ett binärt träd, skriv en iterativ och rekursiv lösning för att genomkorsa trädet med hjälp av inorder traversal i C++, Java och Python.
Till skillnad från länkade listor, endimensionella matriser och andra linjära datastrukturer, som genomkorsas i linjär ordning, kan träd genomkorsas på flera olika sätt i djup första ordning (preorder, inorder och postorder) eller bredd första ordning (level order traversal). Utöver dessa grundläggande traverser är olika mer komplexa eller hybrida system möjliga, t.ex. djupbegränsade sökningar som iterativ fördjupande djupförsta sökning. I det här inlägget diskuteras inorder tree traversal i detalj.
Traversing a tree involves iterating over all nodes in some way. Eftersom trädet inte är en linjär datastruktur kan det finnas mer än en möjlig nästa nod från en given nod, så vissa noder måste skjutas upp, dvs. lagras på något sätt för senare besök. Traverseringen kan göras iterativt där de uppskjutna noderna lagras i stacken, eller så kan den göras genom rekursion, där de uppskjutna noderna lagras implicit i anropsstacken.
För att traversera ett (icke-tomt) binärt träd i en inorder måste vi göra dessa tre saker för varje nod n med början från trädets rot:
(L) Rekursivt traversera dess vänstra underträd. När detta steg är avslutat är vi tillbaka vid n igen.(N) Behandla n i sig själv.(R) Återkommande genomkorsa dess högra delträd. När detta steg är avslutat är vi tillbaka vid n igen.I normal inorder traversal besöker vi det vänstra delträdet före det högra delträdet. Om vi besöker det högra delträdet innan vi besöker det vänstra delträdet kallas det för reverse inorder traversal.
Som vi kan se, innan vi behandlar en nod, behandlas det vänstra delträdet först, följt av noden, och det högra delträdet behandlas till sist. Dessa operationer kan definieras rekursivt för varje nod. Den rekursiva implementeringen kallas DFS (Depth-first search), eftersom sökträdet fördjupas så mycket som möjligt på varje barn innan man går vidare till nästa syskon.
Nedan följer programmet i C++, Java och Python som demonstrerar det:
Iterativ implementering –
För att omvandla ovanstående rekursiva procedur till en iterativ procedur behöver vi en explicit stack. Nedan följer en enkel stackbaserad iterativ algoritm för att utföra inorder traversal.
iterativeInorder(node)
Algoritmen kan implementeras enligt följande i C++, Java och 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 för att utföra inordertraversering av trädet
void inorderIterative(Node *root)
{
// skapa en tom stapel
stack<Node*> stack;
// börja från rotnoden (sätt aktuell nod till rotnoden)
Node *curr = root;
// om den aktuella noden är noll och stapeln också är tom är vi färdiga
while (!stack.empty() || curr != nullptr)
{
// om den aktuella noden finns, skjut in den i stapeln (skjuta upp den)
// och flytta till dess vänstra barn
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// annars, om den aktuella noden är noll, plocka upp ett element från stapeln,
// skriv ut det och sätt slutligen den aktuella noden till dess högra barn
curr = stack.top();
stack.pop();
cout << curr->data << ” ”;
curr = curr->right;
}
}
}
|
Download Run Complete Code
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 för att utföra inorder traversal på trädet
public static void inorderIterative(TreeNode root)
{
// skapa en tom stapel
Stack<TreeNode> stack = new Stack();
// börja från rotnoden (sätt aktuell nod till rotnoden)
TreeNode curr = root;
// om den aktuella noden är noll och stapeln också är tom är vi färdiga
while (!stack.empty() || curr != null)
{
// om den aktuella noden finns, lägg den i stapeln (skjuta upp den)
// och flytta till dess vänstra underbarn
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// annars, om den aktuella noden är noll, plocka upp ett element från stapeln,
// skriv ut det och sätt slutligen den aktuella noden till dess högra underordnade
curr = stack.pop();
System.out.print(curr.data + ” ”);
curr = curr.right;
}
}
}
|
Nedladdning kör fullständig kod
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 för att utföra inorder traversal på trädet
def inorderIterative(root):
# skapa en tom stapel
stack = deque()
# starta från rotnoden (sätt aktuell nod till rotnoden)
curr = root
# om den aktuella noden är None och stapeln också är tom, är vi klara
while stack or curr:
# om den aktuella noden existerar, skjut in den i stapeln (skjuta upp den)
# och flytta till dess vänstra barn
if curr:
stack.append(curr)
curr = curr.left
else:
# annars, om den aktuella noden är None, plocka upp ett element från stapeln,
# skriv ut det och sätt slutligen den aktuella noden till dess högra barn
curr = stack.pop()
print(curr.data, end=’ ”)
curr = curr.right
|
Download Run Complete Code
Tidskomplexiteten för ovanstående lösningar är O(n), där n är det totala antalet noder i det binära trädet. Programmets utrymmeskomplexitet är O(n) eftersom utrymmesbehovet är proportionellt mot trädets höjd, som i värsta fall kan vara lika med det totala antalet noder i trädet för snedställda träd.