树的构造

# include <stdio.h>
# include <stdlib.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *create(struct TreeNode *tree)
{
    int ch;

    scanf("%d", &ch);
    if(ch == 0)
    {
        tree = NULL;
    }
    else
    {
        tree = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
        tree -> val = ch;
        tree -> left  = create(tree -> left);
        tree -> right = create(tree -> right);
    }

    return tree;
}

void printorder(struct TreeNode *tree)
{
    if(tree)
    {
        printf("%d ", tree -> val);
        printorder(tree -> left);
        printorder(tree -> right);
    }
}

main()
{
    struct TreeNode *tree = NULL;
    
    tree = create(tree);
    printf("xianxu ->> ");
    printorder(tree);
    printf("\n\n");
}

验证程序正确

• 二叉树前序、中序、后序遍历非递归写法的透彻解析
  

// 中序遍历非递归实现
void zhong(TreeNode* root){
    if(root == NULL){
        cout<<"树为空";
        return ;
    }
    
    TreeNode* p = root;
    stack<TreeNode*> sk;
    while(!s.empty() || p){
        if(p){
            sk.push(p);
            p = p->lchild;
        }
        else{
            p = sk.top();
            sk.pop();
            cout<<p->data<<" ";
            p = p->rchild;
        }
    }
}

// 前序遍历非递归实现
void qian(TreeNode* root){
    if(root == NULL){
        cout<<"树为空";
        return ;
    }
    
    TreeNode* p = root;
    stack<TreeNode* > sk;
    while(!s.empty() || p){
        if(p){
            cout<<p->data<<" ";
            sk.push(p);
            p = p->lchild;
        }
        else{
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
}

// 后序遍历非递归实现
void hou(TreeNode* root){
    if(root == NULL){
        cout<<"树为空";
        return ;
    }
    
    TreeNode* p = root;
    stack<TreeNode* > sk;
    
    //pCur:当前访问节点，pLastVisit:上次访问节点
    BTNode* pCur, *pLastVisit;
    //pCur = root;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur)
    {
        s.push(pCur);
        pCur = pCur->lchild;
    }
    while (!s.empty())
    {
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        pCur = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        {
            cout << setw(4) << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        /*这里的else语句可换成带条件的else if:
        else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
        因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
        */
        else
        {
            //根节点再次入栈
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->rchild;
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->lchild;
            }
        }
    }
    cout << endl;
}

题目

LeetCode 617. Merge Two Binary Trees