二叉树遍历(c语言)_二叉树遍历c语言代码

leetcode 144

方法一：递归遍历

int* preorderTraversal(struct TreeNode* root,int* returnSize);
void preorder(struct TreeNode* root,int result[],int *returnSize);
 
void preorder(struct TreeNode* root,int result[],int *returnSize)
{
    if(root==NULL)
    {
        return;
    }
    result[(*returnSize)++]=root->val;
    preorder(root->left,result,returnSize);
    preorder(root->right,result,returnSize);
}
int* preorderTraversal(struct TreeNode* root,int* returnSize)
{
    int *result;
    result=(int *)malloc(2000*sizeof(int));
    (*returnSize)=0;
    preorder(root,result,returnSize);
    return result;
}

方法二：迭代遍历

int p_top=0;
struct TreeNode* stack[10010];
void push(struct TreeNode *node);
struct TreeNode *pop(void);
int isempty(void);
 
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res;
    res=(int *)malloc(2000*sizeof(int));
    (*returnSize)=0;
    while(!isempty()||root!=NULL)
    {
        while((root)!=NULL)
        {
            push(root);
            res[(*returnSize)++]=root->val;
            root=root->left;
        }
        root=pop();
        root=root->right;
    }
    return res;
}
void push(struct TreeNode *node)
{
    p_top++;
    stack[p_top]=node;
    return ;
}
struct TreeNode *pop(void)
{
    return stack[p_top--];
}
int isempty(void)
{
    if(p_top==0) return 1;
    else return 0;
}

方法三：Morris遍历

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：

新建临时节点，令该节点为 root；

如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；

如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：

        如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。

        如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。

重复步骤 2 和步骤 3，直到遍历结束。

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res;
    res=(int *)malloc(2000*sizeof(int));
    (*returnSize)=0;
     struct TreeNode *p1,*p2;
     p1=root;p2=NULL;
     while(p1!=NULL)
     {
        if(p1->left!=NULL)
        {
            p2=p1->left;
            while(p2->right!=NULL&&p2->right!=p1)
            {
                p2=p2->right;
            }
            if(p2->right==NULL)
            {
                res[(*returnSize)++]=p1->val;
                p2->right=p1;
                p1=p1->left;
                continue;
            }
            else if(p2->right==p1)
            {
                p2->right=NULL;
            }
        }
        else if(p1->left==NULL)
        {
            res[(*returnSize)++]=p1->val;
        }
        p1=p1->right;
     }
     return res;
}

理解：

Morris其实解决了一个常规循环中循环到叶子节点后难以回到根节点的问题。 我们都知道前序遍历是先左后右，那么对任一节点p1来说，其右子树p1right所有节点必然在左子树p1left之后。代码中第二个while做的是，在p1left里一直往右，直到找不到更右的点，记这一点为p2。然后把p1right接到p2的右边。 这样既保证了p1right在p1left所有点之后，又不需要再回到p1节点。 即在正常的往下循环的过程中，不断把右半部分剪下来，接到左半部分的最右下

方法四：标记遍历法

struct mystack
{
    struct TreeNode *node;
    int judge;
};
struct mystack stack[10010];
int top=0;
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *array;
    array=(int *)malloc(2000*sizeof(int));
    (*returnSize)=0;
    if(root==NULL) return NULL;
    stack[top].node=root->right;
    stack[top].judge=0;top++;
    stack[top].node=root->left;
    stack[top].judge=0;top++;
    stack[top].node=root;
    stack[top].judge=1;top++;
    while(top>0)
    {
        root=stack[--top].node;
        if(root==NULL) continue;
        else if(stack[top].judge==0)
        {
            stack[top].node=root->right;
            stack[top].judge=0;top++;
            stack[top].node=root->left;
            stack[top].judge=0;top++;
            stack[top].node=root;
            stack[top].judge=1;top++;
        }
        else if(stack[top].judge==1)
        {
            array[(*returnSize)++]=root->val;
        }
    }
    return array;
}