您的位置: 首页  >  文章  >  非递归实现二叉树的遍历（C语言）

非递归实现二叉树的遍历（C语言）

分类: 文章 • 2023-11-16 11:25:10

一、二叉树的前序遍历LeetCode144题

1.1 题目描述
给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

1.2 解题思路
非递归实现二叉树的遍历（C语言）
1.3 代码实现

// 支持动态增长的栈
typedef struct TreeNode* STDataType;

typedef struct Stack
{
	STDataType* _array;
	int _top;//栈顶
	int _capacity;//容量
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_array = NULL;
	ps->_capacity = ps->_top = 0;
}
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->_array);
	ps->_array = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		ps->_array = (STDataType*)realloc(ps->_array, sizeof(STDataType)*newcapacity);
		assert(ps->_array);
		ps->_capacity = newcapacity;
	}
	ps->_array[ps->_top] = x;
	++ps->_top;   

}
void StackPop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	--ps->_top;
}
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return ps->_array[ps->_top -1];
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	Stack st;
	StackInit(&st);

	struct TreeNode* cur = root;
	while (StackEmpty(&st) != 0 || cur != NULL)
	{
		//访问左路节点并入栈
		while (cur != NULL)
		{
			//printf("%d ",cur->val);

			++(*returnSize);
			StackPush(&st, cur);
			cur = cur->left;
		}

		//取栈顶元素，并访问其右子树
		struct TreeNode* top = StackTop(&st);
		StackPop(&st);

		//子问题：访问对应左路节点的右子树
		cur = top->right;

	}

	int* prearray = (int*)malloc(sizeof(int)*(*returnSize));
	int i = 0;
	cur = root;
	while (StackEmpty(&st) != 0 || cur != NULL)
	{
		// 1.访问坐路节点并入栈
		while (cur != NULL)
		{
			printf("%d ", cur->val);
			prearray[i++] = cur->val;

			StackPush(&st, cur);
			cur = cur->left;
		}

		struct TreeNode* top = StackTop(&st);
		StackPop(&st);

		// 子问题：访问右子树
		cur = top->right;
	}

	return prearray;
}

二、二叉树的中序遍历LeetCode94题

2.1 题目描述
给定一个二叉树，返回它的 中序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,3,2]

2.2 解题思路
中序遍历实现思想与前序基本相似，只是先将左路节点压入栈中，再取节点的时候再将节点值放入创建的数组中，如此出来的即是二叉树中序遍历的结果。
2.3 代码实现
// 支持动态增长的栈
typedef struct TreeNode* STDataType;

typedef struct Stack
{
	STDataType* _array;
	int _top;//栈顶
	int _capacity;//容量
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_array = NULL;
	ps->_capacity = ps->_top = 0;
}
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->_array);
	ps->_array = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		ps->_array = (STDataType*)realloc(ps->_array, sizeof(STDataType)*newcapacity);
		assert(ps->_array);
		ps->_capacity = newcapacity;
	}
	ps->_array[ps->_top] = x;
	++ps->_top;   

}
void StackPop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	--ps->_top;
}
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return ps->_array[ps->_top -1];
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    Stack st;
    StackInit(&st);
    struct TreeNode* cur = root;
    while(StackEmpty(&st) != 0 || cur != NULL)
    {
        // 1.访问坐路节点并入栈
        while(cur != NULL)
        {
            //printf("%d ", cur->val);
            ++(*returnSize);
            
            StackPush(&st, cur);
            cur = cur->left;
        }
        
        struct TreeNode* top = StackTop(&st);
        StackPop(&st);
        
        // 子问题：访问右子树
        cur = top->right;        
    }
    
    int* inarray = (int*)malloc(4*(*returnSize));
    int i = 0;
    cur = root;
    while(StackEmpty(&st) != 0 || cur != NULL)
    {
        // 1.访问坐路节点并入栈
        while(cur != NULL)
        {
            StackPush(&st, cur);
            cur = cur->left;
        }
        
        struct TreeNode* top = StackTop(&st);
        printf("%d ", top->val);
        inarray[i++] = top->val;
        StackPop(&st);
        
        // 子问题：访问右子树
        cur = top->right;        
    }
    
    return inarray;  
}

三、二叉树的后序遍历LeetCode145题

3.1 题目描述
给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

3.2 解题思路
解题思路也相似，只是需要解决一个问题，就是在先遍历左路节点的右子树时，走回该节点时，是访问完成了其右子树，还是未访问，无法判断，此时我们定义了一个节点prev，来记录cur的前一个值，若prev是该节点的右子树中的节点，则此时已访问了右子树，继续取左路节点，访问右子树即可。
3.3 代码实现

// 支持动态增长的栈
typedef struct TreeNode* STDataType;

typedef struct Stack
{
	STDataType* _array;
	int _top;//栈顶
	int _capacity;//容量
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_array = NULL;
	ps->_capacity = ps->_top = 0;
}
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->_array);
	ps->_array = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		ps->_array = (STDataType*)realloc(ps->_array, sizeof(STDataType)*newcapacity);
		assert(ps->_array);
		ps->_capacity = newcapacity;
	}
	ps->_array[ps->_top] = x;
	++ps->_top;   

}
void StackPop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	--ps->_top;
}
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return ps->_array[ps->_top -1];
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    Stack st;
    StackInit(&st);
   
    //确定遍历的二叉树有几个节点
    struct TreeNode* prev = NULL;
    struct TreeNode* cur = root;
    while(StackEmpty(&st) != 0 || cur != NULL)
    {
        while(cur != NULL)
        {
        //从一直入栈到最左的根节点
        StackPush(&st,cur);
        cur = cur->left;   
    }
    
    //访问所有节点确定节点个数（即returnSize的大小）用以开辟存储节点的数组
    struct TreeNode* top = StackTop(&st);
        if(top->right == NULL || top->right == prev)
        {
            printf("%d ",top->val);
            StackPop(&st);
            prev = top;
            ++(*returnSize);
        }
        else
        {
             // 子问题：访问右子树
            cur = top->right; 
        } 
    }
    //开辟一个数组存储后序遍历的节点
 int* postarray = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    prev = NULL;
    cur = root;
    while(StackEmpty(&st) != 0 || cur != NULL)
    {
        // 1.访问左路节点并入栈
        while(cur != NULL)
        {
            StackPush(&st, cur);
            cur = cur->left;
        }
        
        struct TreeNode* top = StackTop(&st);
         if(top->right == NULL || top->right == prev)
        {
            StackPop(&st);
            postarray[i++] = top->val;
            prev = top; 
        }
        else
        {
             // 子问题：访问右子树
            cur = top->right; 
        }         
    }
    
    return postarray;
}

相关推荐