前序、中序、后序递归、非递归方式打印二叉树

蔚落 2022-05-08 16:36 234阅读 0赞

### 文章目录 ###

*   *  递归
     *   *   *  前序
             *  中序
             *  后序
     *  非递归
     *   *   *  前序
             *  中序
             *  后序

## 递归 ##

#### 前序 ####

void PreOrder(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return;
    		}
    		printf("%d ", root->data); //先打印根节点
    		PreOrder(root->left); //打印左子树
    		PreOrder(root->right);//打印右子树
    	}

#### 中序 ####

void InOrder(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return;
    		}
    		PreOrder(root->left); //先打印左子树
    		printf("%d ", root->data);//打印根节点
    		PreOrder(root->right);//打印右子树
    	}

#### 后序 ####

void PostOrder(BNode *root)
    	{ 
    		if (root == NULL)
    		{ 
    			return;
    		}
    		PreOrder(root->left); //先打印左子树
    		PreOrder(root->right);//打印右子树
    		printf("%d ", root->data);//打印根节点
    	}

## 非递归 ##

#### 前序 ####

如果不用递归的话，我们能想到的一定会用到循环，那么如何来保存这些结点？可以用栈，因为用循环，肯定要从根节点开始，当循环到某一个结点时，我们只会对该结点及其子树进行操作，就利用到了栈的特性。  
在压栈的时候，一直都是先压左子树，因为在遍历中，左孩子一定在右孩子的前面  
对于前序遍历，先打印根节点，因为压栈就是从根节点开始的，一直压左孩子，当左孩子为空时，就让栈顶元素出栈，并开始压右孩子

void PreOrder(BNode *root)
    	{ 
    		Stack stack;
    		StackInit(&stack);
    		BNode *node = root;
    		BNode *top;
    		while (node != NULL || !StackEmpty(&stack))
    		{ 
    			while (node != NULL)
    			{ 
    				printf("%d ", node->data);
    				StackPush(&stack, node);
    				node = node->left;
    			}
    			top = StackTop(&stack);
    			StackPop(&stack);
    			node = top->right;
    		}
    	}

#### 中序 ####

void InOrder(BNode *root)
    	{ 
    		Stack stack;
    		StackInit(&stack);
    		BNode *node = root;
    		BNode *top;
    		while (node != NULL || !StackEmpty(&stack))
    		{ 
    			while (node != NULL)
    			{ 
    				StackPush(&stack, node);
    				node = node->left;
    			}
    			top = StackTop(&stack);
    			printf("%d ", top->data);
    			StackPop(&stack);
    			node = top->right;
    		}
    	}

#### 后序 ####

void PostOrder(BNode *root)
    	{ 
    		Stack stack;
    		StackInit(&stack);
    		BNode *node = root;
    		BNode *top;
    		BNode *last = NULL;
    		while (node != NULL || !StackEmpty(&stack))
    		{ 
    			while (node != NULL)
    			{ 
    				StackPush(&stack, node);
    				node = node->left;
    			}
    			top = StackTop(&stack);
    			if (top->right == NULL || top->right == last)
    			{ 
    				printf("%d ", top->data);
    				last = top;
    				StackPop(&stack);
    			}
    			else
    			{ 
    				node = top->right;
    			}
    		}
    	}