ساعدني في فهم inorder traversal دون استخدام العودية
-
22-09-2019 - |
سؤال
أنا قادر على فهم اجتياز ما قبل الطلب دون استخدام العودية ، لكنني أواجه صعوبة في اجتياز inorder. لا يبدو أنني أحصل عليها ، لأنني لم أفهم العمل الداخلي للروح.
هذا ما جربته حتى الآن:
def traverseInorder(node):
lifo = Lifo()
lifo.push(node)
while True:
if node is None:
break
if node.left is not None:
lifo.push(node.left)
node = node.left
continue
prev = node
while True:
if node is None:
break
print node.value
prev = node
node = lifo.pop()
node = prev
if node.right is not None:
lifo.push(node.right)
node = node.right
else:
break
لا يشعر الحلقة الداخلية في حين أن الحلقة على ما يرام. أيضا ، يتم طباعة بعض العناصر مرتين ؛ قد يكون بإمكاني حل هذا عن طريق التحقق مما إذا كانت هذه العقدة قد طُبعت من قبل ، لكن ذلك يتطلب متغيرًا آخر ، والذي ، مرة أخرى ، لا يشعر بأنه على ما يرام. هل أنا على خطأ؟
لم أحاول اجتياز postorder ، لكنني أعتقد أنه مشابه وسأواجه نفس الانسداد المفاهيمي هناك أيضًا.
شكرا على وقتك!
ملاحظة: تعريفات Lifo
و Node
:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
class Lifo:
def __init__(self):
self.lifo = ()
def push(self, data):
self.lifo = (data, self.lifo)
def pop(self):
if len(self.lifo) == 0:
return None
ret, self.lifo = self.lifo
return ret
المحلول
ابدأ بالخوارزمية العودية (رمز الكاذب):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
هذه حالة واضحة من عودة الذيل ، بحيث يمكنك تحويلها بسهولة إلى حلقة الوقت.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
تركت مكالمة متكررة. ما تقوم به المكالمة العودية هو دفع سياق جديد على المكدس ، وقم بتشغيل الرمز من البداية ، ثم استرداد السياق واستمر في القيام بما كانت تفعله. لذلك ، يمكنك إنشاء مكدس للتخزين ، وحلقة تحدد ، على كل التكرار ، سواء كنا في وضع "التشغيل الأول" (العقدة غير الفريدة) أو موقف "عائد" (NULL NOD ) ويدير الرمز المناسب:
traverse(node):
stack = []
while !empty(stack) || node != None do:
if node != None do: // this is a normal call, recurse
push(stack,node)
node = node.left
else // we are now returning: pop and print the current node
node = pop(stack)
print node.value
node = node.right
endif
endwhile
الشيء الصعب الذي يجب إدراكه هو الجزء "الإرجاع": عليك تحديد ، في حلقتك ، سواء كان الرمز الذي تقوم بتشغيله في موقف "إدخال الوظيفة" أو في حالة "العودة من مكالمة" ، وأنت سوف يكون if/else
سلسلة مع العديد من الحالات التي لديك علامات غير طرفية في الكود الخاص بك.
في هذا الموقف المحدد ، نستخدم العقدة للحفاظ على معلومات حول الموقف. هناك طريقة أخرى تتمثل في تخزين ذلك في المكدس نفسه (تمامًا كما يفعل الكمبيوتر من أجل العودة). مع هذه التقنية ، يكون الرمز أقل مثالًا ، ولكنه أسهل في المتابعة
traverse(node):
// entry:
if node == NULL do return
traverse(node.left)
// after-left-traversal:
print node.value
traverse(node.right)
traverse(node):
stack = [node,'entry']
while !empty(stack) do:
[node,state] = pop(stack)
switch state:
case 'entry':
if node == None do: break; // return
push(stack,[node,'after-left-traversal']) // store return address
push(stack,[node.left,'entry']) // recursive call
break;
case 'after-left-traversal':
print node.value;
// tail call : no return address
push(stack,[node.right,'entry']) // recursive call
end
endwhile
نصائح أخرى
فيما يلي رمز C ++ بسيط في الطلب ..
void inorder (node *n)
{
stack s;
while(n){
s.push(n);
n=n->left;
}
while(!s.empty()){
node *t=s.pop();
cout<<t->data;
t=t->right;
while(t){
s.push(t);
t = t->left;
}
}
}
def print_tree_in(root): stack = [] current = root while True: while current is not None: stack.append(current) current = current.getLeft(); if not stack: return current = stack.pop() print current.getValue() while current.getRight is None and stack: current = stack.pop() print current.getValue() current = current.getRight();
def traverseInorder(node):
lifo = Lifo()
while node is not None:
if node.left is not None:
lifo.push(node)
node = node.left
continue
print node.value
if node.right is not None:
node = node.right
continue
node = lifo.Pop()
if node is not None :
print node.value
node = node.right
ملاحظة: لا أعرف بيثون ، لذلك قد يكون هناك عدد قليل من مشكلات بناء الجملة.
فيما يلي عينة من الترتيب باستخدام المكدس في C# (.NET):
(للحصول على ترتيب ما بعد التكرار ، يمكنك الرجوع إلى: مرحلة ما بعد الترتيب عبر الشجرة الثنائية بدون عودة)
public string InOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
var iterativeNode = this._root;
while(iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
nodes.Add(iterativeNode.Element);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
iterativeNode = iterativeNode.Right.Left;
while(iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
}
}
}
return this.ListToString(nodes);
}
هنا عينة مع العلم زيارة:
public string InorderIterative_VisitedFlag()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode iterativeNode = null;
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
stack.Push(iterativeNode);
if (iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
تعريفات الثنود الثنائية ، فائدة ListToString:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
يمكن تذكر الحالة بشكل ضمني ،
traverse(node) {
if(!node) return;
push(stack, node);
while (!empty(stack)) {
/*Remember the left nodes in stack*/
while (node->left) {
push(stack, node->left);
node = node->left;
}
/*Process the node*/
printf("%d", node->data);
/*Do the tail recursion*/
if(node->right) {
node = node->right
} else {
node = pop(stack); /*New Node will be from previous*/
}
}
}
Victor ، لدي بعض الاقتراحات بشأن تنفيذك في محاولة لدفع الدولة إلى المكدس. لا أرى أنه ضروري. لأن كل عنصر تأخذه من المكدس قد تم اجتيازه بالفعل. لذا ، بدلاً من تخزين المعلومات في المكدس ، كل ما نحتاجه هو علامة للإشارة إلى ما إذا كانت العقدة التالية التي سيتم معالجتها هي من هذا المكدس أم لا. فيما يلي تنفيذي الذي يعمل بشكل جيد:
def intraverse(node):
stack = []
leftChecked = False
while node != None:
if not leftChecked and node.left != None:
stack.append(node)
node = node.left
else:
print node.data
if node.right != None:
node = node.right
leftChecked = False
elif len(stack)>0:
node = stack.pop()
leftChecked = True
else:
node = None
القليل من التحسين للإجابة من قبل emadpres
def in_order_search(node):
stack = Stack()
current = node
while True:
while current is not None:
stack.push(current)
current = current.l_child
if stack.size() == 0:
break
current = stack.pop()
print(current.data)
current = current.r_child
قد يكون هذا مفيدًا (تنفيذ Java)
public void inorderDisplay(Node root) {
Node current = root;
LinkedList<Node> stack = new LinkedList<>();
while (true) {
if (current != null) {
stack.push(current);
current = current.left;
} else if (!stack.isEmpty()) {
current = stack.poll();
System.out.print(current.data + " ");
current = current.right;
} else {
break;
}
}
}
اجتياز تكراري بسيط دون عودة
'''iterative inorder traversal, O(n) time & O(n) space '''
class Node:
def __init__(self, value, left = None, right = None):
self.value = value
self.left = left
self.right = right
def inorder_iter(root):
stack = [root]
current = root
while len(stack) > 0:
if current:
while current.left:
stack.append(current.left)
current = current.left
popped_node = stack.pop()
current = None
if popped_node:
print popped_node.value
current = popped_node.right
stack.append(current)
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
b.right = d
a.left = b
a.right = c
inorder_iter(a)
class Tree:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def insert(self,root,node):
if root is None:
root = node
else:
if root.value < node.value:
if root.right is None:
root.right = node
else:
self.insert(root.right, node)
else:
if root.left is None:
root.left = node
else:
self.insert(root.left, node)
def inorder(self,tree):
if tree.left != None:
self.inorder(tree.left)
print "value:",tree.value
if tree.right !=None:
self.inorder(tree.right)
def inorderwithoutRecursion(self,tree):
holdRoot=tree
temp=holdRoot
stack=[]
while temp!=None:
if temp.left!=None:
stack.append(temp)
temp=temp.left
print "node:left",temp.value
else:
if len(stack)>0:
temp=stack.pop();
temp=temp.right
print "node:right",temp.value
إليك حل C ++ التكراري كبديل لما نشره emadpres:
void inOrderTraversal(Node *n)
{
stack<Node *> s;
s.push(n);
while (!s.empty()) {
if (n) {
n = n->left;
} else {
n = s.top(); s.pop();
cout << n->data << " ";
n = n->right;
}
if (n) s.push(n);
}
}
فيما يلي رمز بيثون تكراري لـ inorder traversal ::
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrder(root):
current = root
s = []
done = 0
while(not done):
if current is not None :
s.append(current)
current = current.left
else :
if (len(s)>0):
current = s.pop()
print current.data
current = current.right
else :
done =1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
inOrder(root)
أعتقد أن جزءًا من المشكلة هو استخدام المتغير "السابق". لا يجب عليك تخزين العقدة السابقة التي يجب أن تكون قادرًا على الحفاظ على الحالة على المكدس (LIFO) نفسها.
من عند ويكيبيديا, ، الخوارزمية التي تهدف إليها هي:
- قم بزيارة الجذر.
- اجتياز الشجرة الفرعية اليسرى
- اجتياز الشجرة الفرعية اليمنى
في رمز Pseudo (إخلاء المسئولية ، لا أعرف Python لذا أعتذر عن رمز نمط Python/C ++ أدناه!) ستكون الخوارزمية مثل:
lifo = Lifo();
lifo.push(rootNode);
while(!lifo.empty())
{
node = lifo.pop();
if(node is not None)
{
print node.value;
if(node.right is not None)
{
lifo.push(node.right);
}
if(node.left is not None)
{
lifo.push(node.left);
}
}
}
بالنسبة إلى اجتياز postorder ، يمكنك ببساطة تبديل الطلب الذي تدفعه إلى القطع الفرعية اليسرى واليمين على المكدس.