你好CSDN

老鐵們，這是我第一次寫博客，我先學學奧

自我介紹

額，，大家就叫我Frank吧，來自黑龍江哈爾濱，最喜歡的音樂人是梁博（一個幾憾訓所有樂器的男人），最喜歡的籃球明星是凱里歐文（一個幾憾訓所有進攻手段的球員），最喜歡吃的是我姥爺做的土豆燉牛肉，最喜歡的學校是哈三中，最喜歡的課程是演算法，最后我特別希望有朝一日成為全堆疊工程師…這…說的都什么亂七八糟的，總之我是個熱愛生活、熱愛學習的人，

整點代碼康康

最近做資料結構演算法的助教，重寫了遍歷二叉樹的演算法
遞回的比較簡單，直接上非遞回了奧~
建議先看中序的，理解透了之后，一分鐘就能寫出另外兩個了

//就資料結構，很簡單
typedef struct node
{
    int value;
    struct node *leftchild;
    struct node *rightchild;
} BTnode, *BTtree;

typedef struct stack
{
    BTnode data[N];
    int meetTimes[N];//元素被瞧到的次數
    int top;
} MyStack;

//先序遍歷二叉樹
void Porder(BTnode *root) {
    MyStack s;
    s.top = -1;
    //在當前節點非空，且當前的堆疊不空時才回圈
    while (root || s.top != -1)
    {
        //當前節點不空，先輸出，再入堆疊，接著走左子樹
        if (root)
        {
            printf("%d ", root->value);
            s.data[++s.top] = *root;
            root = root->leftchild;
        }
        //當前節點為空，彈堆疊一個，走右子樹
        else
        {
            root = &s.data[s.top--];

            root = root->rightchild;
        }
    } }
    
//中序遞回
void inorder(BTnode *root)
{
    if (root)
    {
        //根節點擱置，走左子樹
        inorder(root->leftchild);
        //↙走不通時 回來輸出根
        printf("%d\n", root->value);
        //走這個根的右子樹
        inorder(root->rightchild);
    }
    return;
}
//中序非遞回遍歷二叉樹
//非遞回都是針對當前節點而言，不要判斷當前節點的左和右
void Inorder(BTnode *root)
{
    MyStack s;
    s.top = -1;
    //在當前節點非空，且當前的堆疊不空時才回圈
    while (root || s.top != -1)
    {
        //當前節點如果不空，即刻入堆疊，走左子樹，
        if (root)
        {
            s.data[++s.top] = *root;
            root = root->leftchild;
        }
        //當前節點為空，代表↙走不通了，去堆疊里找一個節點
        //彈堆疊輸出它的值，并且從它右子樹開始
        else
        {
            root = &s.data[s.top--];
            printf("%d ", root->value);
            root = root->rightchild;
        }
    }
}
    
    
//后序遍歷二叉樹
void Eorder(BTnode *root) {
    MyStack s;
    s.top = -1;
    //在當前節點非空，且當前的堆疊不空時才回圈
    while (root || s.top != -1)
    {
        //當前節點不空，即刻入堆疊，接著走左子樹
        if (root)
        {

            s.data[++s.top] = *root;
            s.meetTimes[s.top] = 1;
            root = root->leftchild;
        }
        //當前節點為空，左走不動了
        else
        {
            //堆疊頂元素只被瞧到過一次，走堆疊頂元素的右子樹，不彈堆疊
            if (s.meetTimes[s.top] == 1)
            {
                root = &s.data[s.top];
                root = root->rightchild;
                s.meetTimes[s.top] = 2;
            }
            //堆疊頂元素被瞧到的第二次，彈堆疊輸出
            else if (s.meetTimes[s.top] == 2)
            {
                printf("%d ", s.data[s.top--].value);
            }
        }
    } }

這是標題框嗎？我試一下

Frank的第一個博客

你好CSDN

自我介紹

整點代碼康康

最近在干嗎？

最后要說