اجتياز أمر ما بعد الشجرة الثنائية دون التكرار
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
ما هي الخوارزمية المستخدمة في اجتياز أمر ما بعد الشجرة الثنائية بدون باستخدام العودية؟
المحلول
إليك رابط يوفر حلولا أخرى دون استخدام أي أعلام زيارة.
https://leetcode.com/problems/binary-tree-postordord-traversal/
من الواضح أن هذا هو الحل القائم على المكدس بسبب عدم وجود مؤشر الأم في الشجرة. (لن نحتاج إلى مكدس إذا كان هناك مؤشر الأم).
سوف ندفع عقدة الجذر إلى المكدس أولا. في حين أن المكدس غير فارغ، إلا أننا نستمر في دفع الطفل الأيسر من العقدة من أعلى المكدس. إذا كان الطفل الأيسر غير موجود، فإننا ندفع طفلها الصحيح. إذا كانت عقدة ورقة، فإننا نعالج العقدة ويبوبها من المكدس.
نحن نستخدم أيضا متغيرا لتتبع عقدة تعرض مسبقا. والغرض منه هو تحديد ما إذا كانت الجواب ينحدر / تصاعدي الشجرة، ويمكننا أيضا معرفة ما إذا كان يصعد من اليسار / اليمين.
إذا صعدنا الشجرة من اليسار، فلن نريد دفع طفلها الأيسر مرة أخرى إلى المكدس، وينبغي أن تستمر في الصعود أسفل الشجرة إذا كان طفلها الصحيح موجود. إذا صعدنا الشجرة من اليمين، يجب علينا معالجة ذلك ويبوبه من المكدس.
سنقوم بمعالجة العقدة ويبوبها من المكدس في هذه الحالات الثلاثة:
- العقدة هي عقدة ورقة (لا أطفال)
- نحن فقط اجرس الشجرة من اليسار ولا يوجد طفل مناسب.
- نحن فقط اجرس الشجرة من اليمين.
نصائح أخرى
إليك النسخة باستخدام مكدس واحد وبدون العلم الذي تمت زيارته:
private void postorder(Node head) {
if (head == null) {
return;
}
LinkedList<Node> stack = new LinkedList<Node>();
stack.push(head);
while (!stack.isEmpty()) {
Node next = stack.peek();
boolean finishedSubtrees = (next.right == head || next.left == head);
boolean isLeaf = (next.left == null && next.right == null);
if (finishedSubtrees || isLeaf) {
stack.pop();
System.out.println(next.value);
head = next;
}
else {
if (next.right != null) {
stack.push(next.right);
}
if (next.left != null) {
stack.push(next.left);
}
}
}
}
ها هي عينة من ويكيبيديا:
nonRecursivePostorder(rootNode)
nodeStack.push(rootNode)
while (! nodeStack.empty())
currNode = nodeStack.peek()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push(currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push(currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop()
هذا هو النهج الذي أستخدمه مقابل اجتياز تكراري وترتيب آخر. أنا أحب هذا النهج لأن:
- إنه يتعامل فقط بنقل واحد لكل دورة حلقة، لذلك من السهل اتباعه.
- حلا مماثلا يعمل من أجل اجتيازات داخلية وقائمة مسبقا
رمز:
enum State {LEFT, RIGHT, UP, CURR}
public void iterativePostOrder(Node root) {
Deque<Node> parents = new ArrayDeque<>();
Node curr = root;
State state = State.LEFT;
while(!(curr == root && state == State.UP)) {
switch(state) {
case LEFT:
if(curr.left != null) {
parents.push(curr);
curr = curr.left;
} else {
state = RIGHT;
}
break;
case RIGHT:
if(curr.right != null) {
parents.push(curr);
curr = curr.right;
state = LEFT;
} else {
state = CURR;
}
break;
case CURR:
System.out.println(curr);
state = UP;
break;
case UP:
Node child = curr;
curr = parents.pop();
state = child == curr.left ? RIGHT : CURR;
break;
default:
throw new IllegalStateException();
}
}
}
تفسير:
يمكنك التفكير في الخطوات مثل هذا:
- حاول اليسار
- إذا كانت العقدة اليسرى موجودة: حاول اليسار مرة أخرى
- إذا كانت العقدة اليسرى غير موجودة: حاول الصحيح
- جرب الحق
- إذا كانت العقدة اليمنى موجودة: حاول أن تترك من هناك
- إذا لم يكن هناك حق، فأنت في ورقة: حاول
- جرب ذلك
- طباعة العقدة الحالية
- تم تنفيذ جميع العقد أدناه (بعد الترتيب): جرب
- حاول بجهد
- إذا كانت العقدة جذر، فلا يوجد، حتى الخروج
- إذا كان الخروج من اليسار، فجرب اليمين
- إذا خرج من اليمين، حاول
import java.util.Stack;
public class IterativePostOrderTraversal extends BinaryTree {
public static void iterativePostOrderTraversal(Node root){
Node cur = root;
Node pre = root;
Stack<Node> s = new Stack<Node>();
if(root!=null)
s.push(root);
System.out.println("sysout"+s.isEmpty());
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=null){
s.push(cur.left);
}
else if(cur.right!=null){
s.push(cur.right);
}
if(cur.left==null && cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=null){
s.push(cur.right);
}else if(cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.right){// we are traversing up the tree from the right
System.out.println(s.pop().data);
}
pre=cur;
}
}
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
Node root = bt.generateTree();
iterativePostOrderTraversal(root);
}
}
فيما يلي حلا في C ++ التي لا تتطلب أي تخزين لحجز حفظ في الشجرة.
بدلا من ذلك يستخدم مداخن. واحد لمساعدتنا في اجتياز وآخر لتخزين العقد حتى نتمكن من القيام بعمل آخر منهم.
std::stack<Node*> leftStack;
std::stack<Node*> rightStack;
Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
if( currentNode )
{
leftStack.push( currentNode );
currentNode = currentNode->m_left;
}
else
{
currentNode = leftStack.top();
leftStack.pop();
rightStack.push( currentNode );
currentNode = currentNode->m_right;
}
}
while( !rightStack.empty() )
{
currentNode = rightStack.top();
rightStack.pop();
std::cout << currentNode->m_value;
std::cout << "\n";
}
// إصدار جافا مع العلم
public static <T> void printWithFlag(TreeNode<T> root){
if(null == root) return;
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.add(root);
while(stack.size() > 0){
if(stack.peek().isVisit()){
System.out.print(stack.pop().getValue() + " ");
}else{
TreeNode<T> tempNode = stack.peek();
if(tempNode.getRight()!=null){
stack.add(tempNode.getRight());
}
if(tempNode.getLeft() != null){
stack.add(tempNode.getLeft());
}
tempNode.setVisit(true);
}
}
}
void postorder_stack(Node * root){
stack ms;
ms.top = -1;
if(root == NULL) return ;
Node * temp ;
push(&ms,root);
Node * prev = NULL;
while(!is_empty(ms)){
temp = peek(ms);
/* case 1. We are nmoving down the tree. */
if(prev == NULL || prev->left == temp || prev->right == temp){
if(temp->left)
push(&ms,temp->left);
else if(temp->right)
push(&ms,temp->right);
else {
/* If node is leaf node */
printf("%d ", temp->value);
pop(&ms);
}
}
/* case 2. We are moving up the tree from left child */
if(temp->left == prev){
if(temp->right)
push(&ms,temp->right);
else
printf("%d ", temp->value);
}
/* case 3. We are moving up the tree from right child */
if(temp->right == prev){
printf("%d ", temp->value);
pop(&ms);
}
prev = temp;
}
}
يرجى الاطلاع على هذا تنفيذ جافا الكامل. فقط قم بنسخ الرمز والصقه في برنامج التحويل البرمجي الخاص بك. سوف تعمل بشكل جيد.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Node
{
Node left;
String data;
Node right;
Node(Node left, String data, Node right)
{
this.left = left;
this.right = right;
this.data = data;
}
public String getData()
{
return data;
}
}
class Tree
{
Node node;
//insert
public void insert(String data)
{
if(node == null)
node = new Node(null,data,null);
else
{
Queue<Node> q = new LinkedList<Node>();
q.add(node);
while(q.peek() != null)
{
Node temp = q.remove();
if(temp.left == null)
{
temp.left = new Node(null,data,null);
break;
}
else
{
q.add(temp.left);
}
if(temp.right == null)
{
temp.right = new Node(null,data,null);
break;
}
else
{
q.add(temp.right);
}
}
}
}
public void postorder(Node node)
{
if(node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.print(node.getData()+" --> ");
}
public void iterative(Node node)
{
Stack<Node> s = new Stack<Node>();
while(true)
{
while(node != null)
{
s.push(node);
node = node.left;
}
if(s.peek().right == null)
{
node = s.pop();
System.out.print(node.getData()+" --> ");
if(node == s.peek().right)
{
System.out.print(s.peek().getData()+" --> ");
s.pop();
}
}
if(s.isEmpty())
break;
if(s.peek() != null)
{
node = s.peek().right;
}
else
{
node = null;
}
}
}
}
class Main
{
public static void main(String[] args)
{
Tree t = new Tree();
t.insert("A");
t.insert("B");
t.insert("C");
t.insert("D");
t.insert("E");
t.postorder(t.node);
System.out.println();
t.iterative(t.node);
System.out.println();
}
}
أنا هنا لصق إصدارات مختلفة في C # (.NET) للرجوع إليها: (بالنسبة إلى اجتياز التكرار داخل الترتيب، قد تشير إلى: ساعدني في فهم اجتياز inorder دون استخدام العودية)
- ويكي (http://en.wikipedia.org/wiki/post-order٪5ftraversal#immentations.) (أنيق)
- إصدار آخر من مكدس مفرد (# 1 و # 2: يستخدم في الأساس حقيقة أنه في ترتيب البريد يتم زيارة عقدة الطفل المناسبة قبل زيارة العقدة الفعلية - لذلك، فإننا ببساطة نعتمد على التحقق من أنه إذا كان الطفل الأيمن من أعلى المكدس هو في الواقع آخر عقدة ترتيب ترتيب تم زيارة ذلك - لقد أضفت تعليقات في مختطفات رمز أدناه للحصول على التفاصيل)
- باستخدام إصدار اثنين من المداخن (المرجع: http://www.geeksforgeeks.org/iterative-postorder-traversal/) (أسهل: عكس ترتيب البريد الأساسي في الأساس لعكس عكس سوى اجتياز مسبق مع قرص بسيط تم زيارة العقدة اليمنى أولا، ثم عقدة اليسار)
- باستخدام علم الزوار (سهل)
- اختبارات الوحدة
~
public string PostOrderIterative_WikiVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = this._root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while ((stack.Count > 0)//stack is not empty
|| (iterativeNode != null))
{
if (iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
else
{
var stackTop = stack.Peek();
if((stackTop.Right != null)
&& (stackTop.Right != lastPostOrderTraversalNode))
{
//i.e. last traversal node is not right element, so right sub tree is not
//yet, traversed. so we need to start iterating over right tree
//(note left tree is by default traversed by above case)
iterativeNode = stackTop.Right;
}
else
{
//if either the iterative node is child node (right and left are null)
//or, stackTop's right element is nothing but the last traversal node
//(i.e; the element can be popped as the right sub tree have been traversed)
var top = stack.Pop();
Debug.Assert(top == stackTop);
nodes.Add(top.Element);
lastPostOrderTraversalNode = top;
}
}
}
}
return this.ListToString(nodes);
}
هنا هو آخر ترتيب اجتياز مع كومة واحدة (الإصدار الخاص بي)
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if ((iterativeNode.Left == null)
&& (iterativeNode.Right == null))
{
nodes.Add(iterativeNode.Element);
lastPostOrderTraversalNode = iterativeNode;
//make sure the stack is not empty as we need to peek at the top
//for ex, a tree with just root node doesn't have to enter loop
//and also node Peek() will throw invalidoperationexception
//if it is performed if the stack is empty
//so, it handles both of them.
while(stack.Count > 0)
{
var stackTop = stack.Peek();
bool removeTop = false;
if ((stackTop.Right != null) &&
//i.e. last post order traversal node is nothing but right node of
//stacktop. so, all the elements in the right subtree have been visted
//So, we can pop the top element
(stackTop.Right == lastPostOrderTraversalNode))
{
//in other words, we can pop the top if whole right subtree is
//traversed. i.e. last traversal node should be the right node
//as the right node will be traverse once all the subtrees of
//right node has been traversed
removeTop = true;
}
else if(
//right subtree is null
(stackTop.Right == null)
&& (stackTop.Left != null)
//last traversal node is nothing but the root of left sub tree node
&& (stackTop.Left == lastPostOrderTraversalNode))
{
//in other words, we can pop the top of stack if right subtree is null,
//and whole left subtree has been traversed
removeTop = true;
}
else
{
break;
}
if(removeTop)
{
var top = stack.Pop();
Debug.Assert(stackTop == top);
lastPostOrderTraversalNode = top;
nodes.Add(top.Element);
}
}
}
else
{
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
باستخدام اثنين من المداخن
public string PostOrderIterative_TwoStacksVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
rightLeftPreOrderStack.Push(this._root);
while(rightLeftPreOrderStack.Count > 0)
{
var top = rightLeftPreOrderStack.Pop();
postOrderStack.Push(top);
if(top.Left != null)
{
rightLeftPreOrderStack.Push(top.Left);
}
if(top.Right != null)
{
rightLeftPreOrderStack.Push(top.Right);
}
}
while(postOrderStack.Count > 0)
{
var top = postOrderStack.Pop();
nodes.Add(top.Element);
}
}
return this.ListToString(nodes);
}
مع العلم الذي تمت زيارته في C # (.NET):
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
//reset the flag, for further traversals
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
التعاريف:
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public bool visted;
}
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
اختبارات الوحدة
[TestMethod]
public void PostOrderTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
string s1 = bst.PostOrderRecursive();
string s2 = bst.PostOrderIterativeWithVistedFlag();
string s3 = bst.PostOrderIterative();
string s4 = bst.PostOrderIterative_WikiVersion();
string s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
bst.Add(e);
bst.Delete(e);
bst.Add(e);
s1 = bst.PostOrderRecursive();
s2 = bst.PostOrderIterativeWithVistedFlag();
s3 = bst.PostOrderIterative();
s4 = bst.PostOrderIterative_WikiVersion();
s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
}
Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
}
بيثون مع 1 مكدس وليس العلم:
def postorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if previous and ((previous is current) or (previous is current.left) or (previous is current.right)):
ret.append(current.val)
else:
stack.append(current)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return ret
وما هو أفضل مع عبارات مماثلة، من أجل أعمال اجتياز أيضا
def inorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if None == previous or previous.left is current or previous.right is current:
if current.right:
stack.append(current.right)
stack.append(current)
if current.left:
stack.append(current.left)
else:
ret.append(current.val)
return ret
لم أضيف فئة العقدة كحالات غير ذات صلة خاصة أو أي حالات اختبار، مما يترك أولئك كمرض للقارئ وما إلى ذلك.
void postOrderTraversal(node* root)
{
if(root == NULL)
return;
stack<node*> st;
st.push(root);
//store most recent 'visited' node
node* prev=root;
while(st.size() > 0)
{
node* top = st.top();
if((top->left == NULL && top->right == NULL))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
else
{
//we can check if we are going back up the tree if the current
//node has a left or right child that was previously outputted
if((top->left == prev) || (top->right== prev))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
if(top->right != NULL)
st.push(top->right);
if(top->left != NULL)
st.push(top->left);
}
}
cerr<<endl;
}
وقت التشغيل O (n) - يجب زيارة جميع العقدات والفضاء O (n) - للحصول على مكدس، أسوأ حالة شجرة هي قائمة مرتبطة بخط واحد
من الجيد جدا أن نرى الكثير من الأساليب الحميمة لهذه المشكلة. ملهمة تماما بالفعل!
صادفت هذا الموضوع يبحث عن حل تكراري بسيط لحذف جميع العقد في تنفيذ الأشجار الثنائية. لقد جربت بعضهم، وقد حاولت شيئا مشابها وجدت في أماكن أخرى من الشبكة، لكن لا شيء منهم كان حقا رغبتي.
الشيء هو، وأنا أقدم وحدة فهرسة قاعدة بيانات لغرض محدد للغاية (فهرسة Bitcoin Blockchain)، ويتم تخزين بياناتي على القرص، وليس في ذاكرة الوصول العشوائي. أنا مبادلة في الصفحات حسب الحاجة، قم بإدارة الذاكرة الخاصة بي. إنه أبطأ، ولكن بسرعة كافية لهذا الغرض، ومع وجود تخزين على القرص بدلا من ذاكرة الوصول العشوائي، ليس لدي محامل دينية ضد مساحة هدر (الأقراص الصلبة رخيصة).
لهذا السبب العقد في شجرة ثنائي لها مؤشرات الأم. هذا (كل) المساحة الإضافية التي أتحدث عنها. أحتاج إلى الوالدين لأنني بحاجة إلى تكرار الصعود والتنزح عبر الشجرة لأغراض مختلفة.
بعد ذلك في ذهني، كتبت بسرعة قطعة صغيرة من الكود الزائفي حول كيفية القيام به، وهذا هو، حذف اجتياز آخر ترتيب العقد على الطاير. يتم تنفيذها واختبارها، وأصبحت جزءا من الحل الخاص بي. وهو سريع جدا أيضا.
الشيء هو: إنه حقا، حقا، حقا، بسيطة عندما تكون العقد مؤشرات الأم، وعلاوة على ذلك، لا أستطيع إخراج رابط الوالدين إلى العقدة "المغادر" فقط.
إليك الرمز الزائدي للحذف التكراري بعد الترتيب:
Node current = root;
while (current)
{
if (current.left) current = current.left; // Dive down left
else if (current.right) current = current.right; // Dive down right
else
{
// Node "current" is a leaf, i.e. no left or right child
Node parent = current.parent; // assuming root.parent == null
if (parent)
{
// Null out the parent's link to the just departing node
if (parent.left == current) parent.left = null;
else parent.right = null;
}
delete current;
current = parent;
}
}
root = null;
إذا كنت مهتما بمه مهتمين بمزيد من النهج النظري لترميز المجموعات المعقدة (مثل شجرة ثنائية الثنائية، وهي حقا شجرة حمراء ذاتية اللون الأسود)، ثم تحقق من هذه الروابط:
http://opendatsultures.org/versions/edition-0.1e/60.java/6_2_binarysearree_unbala.html. http://opendatsultures.org/versions/edition-0.1e/ods-java/9_2_redblacktree_simulation_.html. https://www.cs.auckland.ac.nz/software/alganim/red_black.html.
الترميز السعيد :-)
søren الضبابhttp://iprotus.eu/
العمق أولا، طلب آخر، غير العودية، دون كومة
عندما يكون لديك الوالد:
node_t
{
left,
right
parent
}
traverse(node_t rootNode)
{
bool backthreading = false
node_t node = rootNode
while(node <> 0)
if (node->left <> 0) and backthreading = false then
node = node->left
continue
endif
>>> process node here <<<
if node->right <> 0 then
lNode = node->right
backthreading = false
else
node = node->parent
backthreading = true
endif
endwhile
1.1 إنشاء مكدس فارغ
2.1 قم بالمتابعة بينما الجذر ليس فارغًا
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 قم بإخراج عنصر من المكدس وقم بتعيينه كجذر.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 كرر الخطوتين 2.1 و2.2 عندما لا يكون المكدس فارغًا.
هنا هو تنفيذ جافا مع اثنين من المداخن
public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
if (root == null) {
return Collections.emptyList();
}
List<T> result = new ArrayList<T>();
Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
firstLevel.push(root);
while (!firstLevel.isEmpty()) {
BinaryTreeNode<T> node = firstLevel.pop();
secondLevel.push(node);
if (node.hasLeftChild()) {
firstLevel.push(node.getLeft());
}
if (node.hasRightChild()) {
firstLevel.push(node.getRight());
}
}
while (!secondLevel.isEmpty()) {
result.add(secondLevel.pop().getData());
}
return result;
}
هنا هي اختبارات الوحدة
@Test
public void iterativePostOrderTest() {
BinaryTreeNode<Integer> bst = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});
assertThat(BinaryTreeUtil.iPostOrder(bst).toArray(new Integer[0]), equalTo(new Integer[]{4,5,2,6,7,3,1}));
}
/**
* This code will ensure holding of chain(links) of nodes from the root to till the level of the tree.
* The number of extra nodes in the memory (other than tree) is height of the tree.
* I haven't used java stack instead used this ParentChain.
* This parent chain is the link for any node from the top(root node) to till its immediate parent.
* This code will not require any altering of existing BinaryTree (NO flag/parent on all the nodes).
*
* while visiting the Node 11; ParentChain will be holding the nodes 9 -> 8 -> 7 -> 1 where (-> is parent)
*
* 1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 7
/ \ /
/ \ /
/ \ /
/ \ /
3 6 8
/ \ /
/ \ /
4 5 9
/ \
10 11
*
* @author ksugumar
*
*/
public class InOrderTraversalIterative {
public static void main(String[] args) {
BTNode<String> rt;
String[] dataArray = {"1","2","3","4",null,null,"5",null,null,"6",null,null,"7","8","9","10",null,null,"11",null,null,null,null};
rt = BTNode.buildBTWithPreOrder(dataArray, new Counter(0));
BTDisplay.printTreeNode(rt);
inOrderTravesal(rt);
}
public static void postOrderTravesal(BTNode<String> root) {
ParentChain rootChain = new ParentChain(root);
rootChain.Parent = new ParentChain(null);
while (root != null) {
//Going back to parent
if(rootChain.leftVisited && rootChain.rightVisited) {
System.out.println(root.data); //Visit the node.
ParentChain parentChain = rootChain.Parent;
rootChain.Parent = null; //Avoid the leak
rootChain = parentChain;
root = rootChain.root;
continue;
}
//Traverse Left
if(!rootChain.leftVisited) {
rootChain.leftVisited = true;
if (root.left != null) {
ParentChain local = new ParentChain(root.left); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.left;
continue;
}
}
//Traverse RIGHT
if(!rootChain.rightVisited) {
rootChain.rightVisited = true;
if (root.right != null) {
ParentChain local = new ParentChain(root.right); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.right;
continue;
}
}
}
}
class ParentChain {
BTNode<String> root;
ParentChain Parent;
boolean leftVisited = false;
boolean rightVisited = false;
public ParentChain(BTNode<String> node) {
this.root = node;
}
@Override
public String toString() {
return root.toString();
}
}
void display_without_recursion(struct btree **b)
{
deque< struct btree* > dtree;
if(*b)
dtree.push_back(*b);
while(!dtree.empty() )
{
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
if(t->right)
dtree.push_front(t->right);
if(t->left)
dtree.push_front(t->left);
}
cout << endl;
}
import java.util.Stack;
class Practice
{
public static void main(String arr[])
{
Practice prc = new Practice();
TreeNode node1 = (prc).new TreeNode(1);
TreeNode node2 = (prc).new TreeNode(2);
TreeNode node3 = (prc).new TreeNode(3);
TreeNode node4 = (prc).new TreeNode(4);
TreeNode node5 = (prc).new TreeNode(5);
TreeNode node6 = (prc).new TreeNode(6);
TreeNode node7 = (prc).new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
postOrderIteratively(node1);
}
public static void postOrderIteratively(TreeNode root)
{
Stack<Entry> stack = new Stack<Entry>();
Practice prc = new Practice();
stack.push((prc).new Entry(root, false));
while (!stack.isEmpty())
{
Entry entry = stack.pop();
TreeNode node = entry.node;
if (entry.flag == false)
{
if (node.right == null && node.left == null)
{
System.out.println(node.data);
} else
{
stack.push((prc).new Entry(node, true));
if (node.right != null)
{
stack.push((prc).new Entry(node.right, false));
}
if (node.left != null)
{
stack.push((prc).new Entry(node.left, false));
}
}
} else
{
System.out.println(node.data);
}
}
}
class TreeNode
{
int data;
int leafCount;
TreeNode left;
TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public int getLeafCount()
{
return leafCount;
}
public void setLeafCount(int leafCount)
{
this.leafCount = leafCount;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
@Override
public String toString()
{
return "" + this.data;
}
}
class Entry
{
Entry(TreeNode node, boolean flag)
{
this.node = node;
this.flag = flag;
}
TreeNode node;
boolean flag;
@Override
public String toString()
{
return node.toString();
}
}
}
كنت أبحث عن مقتطف رمز يعمل بشكل جيد وهو بسيط لتخصيصه. الأشجار الخيوط ليست "بسيطة". يحتاج محلول المكدس المزدوج ذاكرة O (n). حل leetcode والحلول عن طريق TCB. لديك شيكات إضافية ودفع ...
فيما يلي خوارزمية واحدة كلاسيكية مترجمة إلى ج التي عملت بالنسبة لي:
void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
TreeNode *stack[40]; // simple C stack, no overflow check
TreeNode **sp = stack;
TreeNode *last_visited = NULL;
for (; p != NULL; p = p->left)
*sp++ = p;
while (sp != stack) {
p = sp[-1];
if (p->right == NULL || p->right == last_visited) {
visit(p);
last_visited = p;
sp--;
} else {
for (p = p->right; p != NULL; p = p->left)
*sp++ = p;
}
}
}
IMHO هذه الخوارزمية أسهل في اتباعها من الأداء بشكل جيد ويمكن القراءة Wikipedia.org / Tree_TraVersal Pseudocode. للحصول على تفاصيل مجيدة، انظر إجابات تمارين الأشجار الثنائية في حجم الرنوث 1.
هنا نسخة بيثون أيضا ::
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def postOrderIterative(root):
if root is None :
return
s1 = []
s2 = []
s1.append(root)
while(len(s1)>0):
node = s1.pop()
s2.append(node)
if(node.left!=None):
s1.append(node.left)
if(node.right!=None):
s1.append(node.right)
while(len(s2)>0):
node = s2.pop()
print(node.data)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)
هنا هو الناتج ::
حتى تتمكن من استخدام مكدس واحد للقيام بعمل ترتيب آخر.
private void PostOrderTraversal(Node pos) {
Stack<Node> stack = new Stack<Node>();
do {
if (pos==null && (pos=stack.peek().right)==null) {
for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
} else if(pos!=null) {
stack.push(pos);
pos=pos.left;
}
} while (!stack.isEmpty());
}
منطق اجتياز الطلب اللاحق دون استخدام العودية
في Postorder traversal, ، أمر المعالجة هو left-right-current.لذلك نحن بحاجة لزيارة القسم الأيسر أولا قبل زيارة الأجزاء الأخرى.سنحاول النزول إلى الشجرة على أقصى يسار ممكن لكل عقدة من الشجرة.بالنسبة لكل عقدة حالية، إذا كان الطفل المناسب موجودًا، فادفعه إلى المكدس قبل دفع العقدة الحالية بينما الجذر ليس NULL/None.الآن قم بإخراج عقدة من المكدس وتحقق مما إذا كان الطفل الصحيح لتلك العقدة موجودًا أم لا.إذا كان موجودًا، فتحقق مما إذا كان هو نفس العنصر العلوي أم لا.إذا كانت متماثلة، فهذا يشير إلى أننا لم ننته من الجزء الصحيح بعد، لذا قبل معالجة العقدة الحالية، يتعين علينا معالجة الجزء الصحيح ولهذا السبب، قم بإبراز العنصر العلوي (الفرع الأيمن) ودفع العقدة الحالية مرة أخرى إلى المكدس .في كل مرة يكون رأسنا هو العنصر المنبثق.إذا كان العنصر الحالي ليس هو نفسه العنصر العلوي والرأس ليس NULL، فإننا قد انتهينا من كل من القسم الأيسر والأيمن حتى نتمكن الآن من معالجة العقدة الحالية.علينا أن نكرر الخطوات السابقة حتى تصبح المكدس فارغة.
def Postorder_iterative(head):
if head is None:
return None
sta=stack()
while True:
while head is not None:
if head.r:
sta.push(head.r)
sta.push(head)
head=head.l
if sta.top is -1:
break
head = sta.pop()
if head.r is not None and sta.top is not -1 and head.r is sta.A[sta.top]:
x=sta.pop()
sta.push(head)
head=x
else:
print(head.val,end = ' ')
head=None
print()
طريقتان لأداء اجتياز آخر ترتيب دون إصداع:
1. استخدام Hathset واحد من العقد التي تمت زيارتها وكومة واحدة ل Backtracking:
private void postOrderWithoutRecursion(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
visited.add(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null || visited.contains(root.right)) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
root = root.right;
}
}
}
}
تعقيد الوقت: O (ن)
تعقيد الفضاء: O (2N)
2. استخدام طريقة تغيير الأشجار:
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
TreeNode temp = root.right;
root.right = null;
root = temp;
}
}
}
}
تعقيد الوقت: O (ن)
تعقيد الفضاء: O (ن)
فئة Tereenode:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
إليك نسخة قصيرة (The Walker هي 3 خطوط) كنت بحاجة للكتابة في بيثون لشجرة عامة. بالطبع، يعمل لشجرة ثنائية أكثر محدودية أيضا. الشجرة هي tuple من عقدة وقائمة الأطفال. لديها كومة واحدة فقط. استخدام عينة مبين.
def postorder(tree):
def do_something(x): # Your function here
print(x),
def walk_helper(root_node, calls_to_perform):
calls_to_perform.append(partial(do_something, root_node[0]))
for child in root_node[1]:
calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
calls_to_perform = []
calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
while calls_to_perform:
calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))
د ج ب
أبسط الحل، قد يبدو أنه ليس أفضل إجابة ولكن من السهل أن نفهم. وأعتقد إذا كنت قد فهمت الحل ثم يمكنك تعديله لجعل أفضل حل ممكن
// باستخدام اثنين من المداخن
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> st=new Stack<>();
Stack<TreeNode> st2=new Stack<>();
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)
return al;
st.push(root); //push the root to 1st stack
while(!st.isEmpty())
{
TreeNode curr=st.pop();
st2.push(curr);
if(curr.left!=null)
st.push(curr.left);
if(curr.right!=null)
st.push(curr.right);
}
while(!st2.isEmpty())
al.add(st2.pop().val);
//this ArrayList contains the postorder traversal
return al;
}
لا تنتمي إلى StackOverflow
