再帰を使用せずにバイナリツリーのポストオーダートラバーサルを実行するためのアルゴリズムは何ですか？
107546 次
30 に答える
41
スタックが 1 つあり、訪問済みフラグがないバージョンを次に示します。
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);
}
}
}
}
于 2013-04-18T20:21:24.933 に答える
33
Here's a link which provides two other solutions without using any visited flags.
https://leetcode.com/problems/binary-tree-postorder-traversal/
This is obviously a stack-based solution due to the lack of parent pointer in the tree. (We wouldn't need a stack if there's parent pointer).
We would push the root node to the stack first. While the stack is not empty, we keep pushing the left child of the node from top of stack. If the left child does not exist, we push its right child. If it's a leaf node, we process the node and pop it off the stack.
We also use a variable to keep track of a previously-traversed node. The purpose is to determine if the traversal is descending/ascending the tree, and we can also know if it ascend from the left/right.
If we ascend the tree from the left, we wouldn't want to push its left child again to the stack and should continue ascend down the tree if its right child exists. If we ascend the tree from the right, we should process it and pop it off the stack.
We would process the node and pop it off the stack in these 3 cases:
- The node is a leaf node (no children)
- We just traverse up the tree from the left and no right child exist.
- We just traverse up the tree from the right.
于 2010-10-28T17:55:55.650 に答える
29
これがウィキペディアからのサンプルです：
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()
于 2009-08-18T15:41:54.720 に答える
2
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);
}
}
于 2012-03-31T15:41:32.373 に答える
2
これは、ツリー内でブックを保持するためのストレージを必要としない C++ のソリューションです。
代わりに、2 つのスタックを使用します。1 つはトラバースを支援するためのもので、もう 1 つはノードを保存してポスト トラバーサルを実行できるようにするためのものです。
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";
}
于 2012-09-07T23:37:08.680 に答える
2
// フラグ付きの 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);
}
}
}
于 2012-12-24T05:40:21.420 に答える
0
/**
* 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();
}
}
于 2016-04-18T13:22:09.167 に答える
0
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();
}
}
}
于 2016-08-22T04:29:59.673 に答える
0
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 スタックから項目をポップし、ルートとして設定します。
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 を繰り返します。
于 2015-10-08T17:26:47.590 に答える
0
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;
}
}
于 2014-02-09T06:44:41.087 に答える
0
これらの再帰的メソッドに相当する反復を記述するために、最初に再帰的メソッド自体がプログラムのスタック上でどのように実行されるかを理解できます。ノードに親ポインターがない場合、反復バリアント用に独自の「スタック」を管理する必要があります。
開始する 1 つの方法は、再帰メソッドを確認し、呼び出しが「再開」される場所 (新しい最初の呼び出し、または再帰呼び出しが戻った後) をマークすることです。これらの下には、「RP 0」、「RP 1」など (「再開ポイント」) としてマークされています。ポストオーダー トラバーサルの場合:
void post(node *x)
{
/* RP 0 */
if(x->lc) post(x->lc);
/* RP 1 */
if(x->rc) post(x->rc);
/* RP 2 */
process(x);
}
その反復バリアント:
void post_i(node *root)
{
node *stack[1000];
int top;
node *popped;
stack[0] = root;
top = 0;
popped = NULL;
#define POPPED_A_CHILD() \
(popped && (popped == curr->lc || popped == curr->rc))
while(top >= 0)
{
node *curr = stack[top];
if(!POPPED_A_CHILD())
{
/* type (x: 0) */
if(curr->rc || curr->lc)
{
if(curr->rc) stack[++top] = curr->rc;
if(curr->lc) stack[++top] = curr->lc;
popped = NULL;
continue;
}
}
/* type (x: 2) */
process(curr);
top--;
popped = curr;
}
}
コードは、再帰メソッドの「RP 0」と「RP 2」の再開ポイントに対応しています(x: 0)。(x: 2)
lcとの両方のポインターを一緒にプッシュすることで、 が実行を完了するまで呼び出しを再開ポイント 1rcに保持する必要がなくなりました。つまり、「RP 1」をバイパスして、ノードを「RP 2」に直接シフトできます。したがって、「RP 1」段階でスタックに保持されるノードはありません。post(x)post(x->lc)
このPOPPED_A_CHILDマクロは、2 つの再開ポイント (「RP 0」または「RP 2」) のいずれかを推測するのに役立ちます。
于 2021-01-13T17:17:37.937 に答える
0
したがって、1 つのスタックを使用してポスト オーダー トラバーサルを実行できます。
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());
}
于 2018-06-30T04:49:58.410 に答える
0
最も単純な解決策です。最良の答えではないように見えるかもしれませんが、理解しやすいです。そして、解決策を理解していれば、それを修正して可能な限り最善の解決策を作成できると思います
// 2 つのスタックを使用
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;
}
于 2019-07-04T06:08:12.480 に答える