二叉樹的迭代有序遍歷


難度級別
二叉樹 樹遍歷

在“二叉樹的迭代有序遍歷”問題中,我們得到一個 二叉樹。 我們需要以有序的方式遍歷它 “反复地”,無需遞歸。

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

算法

  1. 初始化變量 “ curNode” 作為二叉樹的根
  2. 初始化一個空棧, 包含節點 當他們被遍歷
  3. 執行以下操作,直到堆棧不為空或 節點 尚未成為 空值:
    • 節點 is 空值:
      1. 節點 進入堆棧
      2. 通過將當前節點更改為 curNode = curNode->左
    • 現在,堆棧中的頂部節點是當前子樹的最左側節點,因此我們打印堆棧中頂部節點的值
    • 分配 節點 作為堆棧中頂部節點的右子元素,如 curNode = stack.top()->右 
    • 通過將當前節點更改為 curNode = curNode->左 處理這個最左邊節點的右邊子樹
    • 從堆棧中彈出一個元素

解釋

該程序使用堆棧彈出最近添加的元素的想法,在上面解釋的算法中,我們簡單地推斷出,如果當前節點(最初是節點的根) )有一個左孩子,然後我們繼續將其左孩子推入堆棧,直到不再有剩餘的左孩子為止。

當出現這種情況使得當前節點沒有左子節點時,很顯然堆棧中的頂部節點是 “最近的最左邊的節點” 添加。 因此,它應以其餘遍歷順序排在第一位。 因此,我們開始將其打印/添加到我們的訂單列表中,然後將其彈出堆棧。 完成後,我們現在清楚以下事實: Left-curNode-Right(順序順序),Left 節點 部分被遍歷。 因此,節點的正確子樹已進入流程!

直觀地講,由於我們想對當前節點的右子樹應用相同的過程,因此可以將其概括為: curNode = curNode->正確。

二叉樹的迭代有序遍歷

履行

二叉樹的迭代有序遍歷的C ++程序

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}
4 1 5 2 3 

二叉樹迭代有序遍歷的Java程序

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

複雜度分析

時間複雜度 二叉樹的迭代有序遍歷

時間複雜度是 上),因為我們只訪問每個節點一次。 在此,N是二叉樹中的節點數。

空間複雜度 二叉樹的迭代有序遍歷

空間複雜度是 上)。 考慮到最壞的情況,即樹可能是傾斜的樹,空間複雜度將等於二叉樹中的節點數。