Повторный обход двоичного дерева без рекурсии
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каков алгоритм для выполнения обхода бинарного дерева после упорядочения БЕЗ используя рекурсию?
Решение
Вот ссылка, которая предоставляет два других решения без использования каких-либо посещенных флагов.
https://leetcode.com/problems/binary-tree-postorder-traversal/
Очевидно, что это решение на основе стека из-за отсутствия родительского указателя в дереве.(Нам не понадобился бы стек, если бы был родительский указатель).
Сначала мы бы поместили корневой узел в стек.Пока стек не пуст, мы продолжаем выталкивать левый дочерний элемент узла из верхней части стека.Если левый дочерний элемент не существует, мы нажимаем на его правый дочерний элемент.Если это конечный узел, мы обрабатываем узел и удаляем его из стека.
Мы также используем переменную для отслеживания ранее пройденного узла.Цель состоит в том, чтобы определить, является ли обход нисходящим / восходящим по дереву, и мы также можем узнать, поднимается ли он слева / справа.
Если мы поднимемся по дереву слева, мы бы не хотели снова помещать его левый дочерний элемент в стек и должны продолжить подъем вниз по дереву, если его правый дочерний элемент существует.Если мы поднимемся по дереву справа, мы должны обработать его и удалить из стека.
Мы бы обработали узел и извлекли его из стека в этих 3 случаях:
- Узел является конечным узлом (без дочерних элементов)
- Мы просто проходим вверх по дереву слева, и никакого правого дочернего элемента не существует.
- Мы просто обходим дерево справа.
Другие советы
Вот версия с одним стеком и без флага посещенных:
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();
}
}
}
Объяснение:
Вы можете подумать о таких шагах следующим образом:
- Попробуй НАЛЕВО
- если левый узел существует:Попробуй еще раз НАЛЕВО
- если левый узел не существует:Попробуй ПРАВИЛЬНО
- Попробуй ПРАВИЛЬНО
- Если существует правильный узел:Попробуйте ОТТУДА ПОВЕРНУТЬ НАЛЕВО
- Если никакого права не существует, вы находитесь на грани:Попробуйте CURR
- Попробуйте CURR
- Печать текущего узла
- Все нижеприведенные узлы были выполнены (после заказа):Попробуй ПОДНЯТЬСЯ
- Попробуй ПОДНЯТЬСЯ
- Если узел является корневым, то UP отсутствует, поэтому ВЫЙДИТЕ
- Если подходите слева, Попробуйте СПРАВА
- Если подходите справа, попробуйте CURR
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";
}
// версия java с флагом
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;
}
}
Пожалуйста, ознакомьтесь с этой полной реализацией Java.Просто скопируйте код и вставьте в свой компилятор.Это будет работать нормально.
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) для справки:(для итеративного обхода по порядку вы можете обратиться к: Помогите мне понять обход по порядку без использования рекурсии)
- вики (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (элегантный)
- Другая версия single stack (# 1 и #2:в основном использует тот факт, что при обходе после заказа правый дочерний узел посещается перед посещением фактического узла - таким образом, мы просто полагаемся на проверку того, действительно ли правый дочерний узел stack top является последним посещенным узлом обхода после заказа - я добавил комментарии к приведенным ниже фрагментам кода для деталей)
- Использование версии с двумя стеками (см.: 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()));
}
Python с 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
Я не добавил класс node, поскольку он не особенно актуален, или какие-либо тестовые примеры, оставив их в качестве упражнения для читателя и т.д.
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) - для стека дерево в наихудшем случае представляет собой список, связанный с одной строкой
Очень приятно видеть так много энергичных подходов к этой проблеме.Действительно, весьма вдохновляюще!
Я наткнулся на эту тему в поисках простого итеративного решения для удаления всех узлов в моей реализации двоичного дерева.Я попробовал некоторые из них, и я попробовал что-то подобное, найденное в другом месте в Сети, но ни одно из них мне по-настоящему не понравилось.
Дело в том, что я разрабатываю модуль индексации базы данных для очень специфической цели (индексация биткойн-блокчейна), и мои данные хранятся на диске, а не в оперативной памяти.Я меняю местами страницы по мере необходимости, занимаясь своим собственным управлением памятью.Это медленнее, но достаточно быстро для этой цели, а поскольку у меня есть хранилище на диске вместо оперативной памяти, я не имею никакого отношения к пустой трате места (жесткие диски дешевы).
По этой причине мои узлы в моем двоичном дереве имеют родительские указатели.Это (все) дополнительное пространство, о котором я говорю.Мне нужны родители, потому что мне нужно выполнять итерации как по возрастанию, так и по убыванию по дереву для различных целей.
Имея это в виду, я быстро записал небольшой фрагмент псевдокода о том, как это можно было бы сделать, то есть обход после заказа, удаляющий узлы "на лету".Это внедрено и протестировано и стало частью моего решения.И к тому же это довольно быстро.
Дело в том, что:Это становится действительно, ДЕЙСТВИТЕЛЬНО, просто, когда узлы имеют родительские указатели, и, более того, поскольку я могу обнулить родительскую ссылку на "только что ушедший" узел.
Вот псевдокод для итеративного удаления после заказа:
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://opendatastructures.org/versions/edition-0.1e/ods-java/6_2_BinarySearchTree_Unbala.html http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
Счастливого кодирования :-)
Серен Туман 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 Выполните следующие действия, пока root не равен NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Извлеките элемент из стека и установите для него значение root.
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, пока стек не опустеет.
Вот реализация Java с двумя стеками
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 и решение с помощью утс проведите дополнительные проверки и подталкивания...
Вот один классический алгоритм, переведенный на C, который сработал для меня:
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;
}
}
}
ИМХО, этому алгоритму легче следовать, чем хорошо работающему и читаемому wikipedia.org / Псевдокод Tree_traversal.Для получения более подробной информации смотрите Ответы на упражнения по бинарному дереву в томе 1 Кнута.
Вот версия Python тоже ::
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.Поэтому нам нужно сначала посетить левую секцию, прежде чем посещать другие части.Мы постараемся перейти к дереву как можно левее для каждого узла дерева.Для каждого текущего узла, если присутствует правильный дочерний элемент, вставьте его в стек, прежде чем нажимать на текущий узел, пока root не равен NULL / None.Теперь извлеките узел из стека и проверьте, существует ли правильный дочерний элемент этого узла или нет.Если он существует, то проверьте, совпадает ли он с верхним элементом или нет.Если они совпадают, то это указывает на то, что мы еще не закончили с правой частью, поэтому перед обработкой текущего узла мы должны обработать правую часть и для этого извлечь верхний элемент (правый дочерний элемент) и поместить текущий узел обратно в стек.В каждый момент времени наша голова является всплывающим элементом.Если текущий элемент не совпадает с top, а head не равен 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.Использование одного хэш-набора посещенных узлов и Одного стека для обратного отслеживания:
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(n)
Космическая Сложность: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(n)
Космическая Сложность:O(n)
Класс TreeNode ( древовидный узел ):
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Вот короткая (ходок состоит из 3 строк) версия, которую мне нужно было написать на Python для общего дерева.Конечно, это работает и для более ограниченного двоичного дерева.Дерево - это кортеж из узла и списка дочерних элементов.У него только один стек.Показан пример использования.
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', [])])]))
d c b a
Самое простое решение, оно может показаться не самым лучшим ответом, но его легко понять.И я верю, что если вы поняли решение, то вы можете изменить его, чтобы создать наилучшее возможное решение
// использование двух стеков
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;
}
