非递归方式建树并按任一种非递归遍历次序输出二叉树中

stack<BiTree> s;
BiTree curr = T->lchild; // 指向当前要检查的节点
s.push(T);
while(curr != NULL || !s.empty())
{
while(curr != NULL) // 一直向左走
if(queue[front]->rchild!=NULL)
{
queue[rear]=queue[front]->rchild; //将队首结点的右孩子指针入队列
rear++; //队尾指针后移一位
}
printf("| 5.退出程序 |\n");
printf("|--------------------------------------------------------------|\n");
printf("| 1.递归先序遍历 |\n");
printf("| 2.非递归中序遍历 |\n");
printf("| 二叉树的基本操作如下: |\n");
printf("| 0.创建二叉树 |\n");
PostOrder(root->rchild); //递归调用，前序遍历右子树
printf("%c ", root->data); //输出数据
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
{
printf("非递归中序遍历二叉树：");

一、设计思想1. 用递归算法遍历设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历前序遍历：先判断节点是否为空，如果不为空，则输出。

再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。

接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。

如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。

中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。

如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。

后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。

此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。

2. 用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。

先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。

然后判断左子树是否为空，如果不为空，则将左子树压栈。

接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。

中序遍历：通过循环实现。

将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。

输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。

后序遍历：通过循环和标记栈实现。

将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。

当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。

然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。

用递归、非递归两种方法遍历二叉树一、设计思想1. 用递归算法遍历设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历前序遍历：先判断节点是否为空，如果不为空，则输出。

再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。

接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。

如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。

中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。

如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。

后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。

此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。

2. 用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。

先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。

然后判断左子树是否为空，如果不为空，则将左子树压栈。

接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。

中序遍历：通过循环实现。

将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。

输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。

后序遍历：通过循环和标记栈实现。

将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。

当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。

一、设计思想递归实现二叉树遍历的思想:1.要遍历二叉树首先的问题是创建二叉树。

二叉树的创建可以采用很多的方法。

例如：先序，中序，后序，还可以采用层次的方法创建二叉树。

本程序采用的是先序递归的方式创建的二叉树。

2.然后是中序，先序，后序递归遍历二叉树。

递归的思想是一直调用方法本身。

3.中序递归遍历二叉树的思想是先访问左子树，然后访问根节点，最后访问右子树。

当访问左子树或是右子树的时候，实际上调用的是函数本身。

在这里就体现了递归的思想，当函数的返回值是0的时候，则返回上一次的程序，继续执行下面的语句。

4.先序递归遍历二叉树的思想是先访问根节点，然后访问左子树，最后访问右子树。

同样如步骤3的方式相同，当访问左子树或者是右子树的收，实际上调用的是函数本身，直到返回值是0的时候，返回上一层的程序继续执行。

5.后序递归遍历二叉树的思想是先访问左子树，然后访问右子树，最后访问根节点。

同样跟步骤3的方式相同，当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序，继续执行.非递归实现二叉树遍历的思想:1.跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。

2.然后是中序，先序，后序非递归遍历二叉树。

3.中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。

直到左子树为空的时候，不再压栈。

将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。

当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。

重复上面的操作，直到栈空的时候。

4.先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。

同时将出栈元素的右子树进栈，左子树进栈。

重复上面的操作，直到栈为空。

5.后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。

⾮递归实现⼆叉树先序、中序和后序遍历⽤递归⽅式实现⼆叉树先序、中序和后序遍历很简单。

⽤递归⽅法解决的问题都能⽤⾮递归的⽅法实现。

递归就是利⽤函数栈来保存信息，如果⽤⾃⼰申请的数据结构来代替函数栈，也可以实现相同的功能。

⽤⾮递归的⽅式实现⼆叉树的先序遍历（LeetCode144）：1、申请⼀个栈stack，然后将头节点压⼊stack中。

2、从stack中弹出栈顶节点，打印，再将其右孩⼦节点（不为空的话）先压⼊stack中，最后将其左孩⼦节点（不为空的话）压⼊stack中。

3、不断重复步骤2，直到stack为空，全部过程结束。

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode(int x) { val = x; }8 * }9*/10import java.util.*;11class Solution {12public List<Integer> preorderTraversal(TreeNode root) {13 List<Integer> list=new ArrayList<Integer>();14 Stack<TreeNode> stack=new Stack<TreeNode>();15if (root!=null) {16 stack.push(root);17while(!stack.empty()) {18 TreeNode tr=stack.pop();19 list.add(tr.val);20if(tr.right!=null) {21 stack.push(tr.right);22 }23if(tr.left!=null) {24 stack.push(tr.left);25 }26 }27 }28return list;29 }30 }⽤⾮递归的⽅式实现⼆叉树的中序遍历（LeetCode94）：1、申请⼀个栈stack，初始时令cur=head2、先把cur压⼊栈中，依次把左边界压⼊栈中，即不停的令cur=cur.left，重复步骤23、不断重复2，直到为null，从stack中弹出⼀个节点，记为node，打印node的值，并令cur=node.right,重复步骤24、当stack为空且cur为空时，整个过程停⽌。

二叉树中序遍历的非递归算法实现二叉树的中序遍历是指先遍历左子树，再遍历根节点，最后遍历右子树的过程。

下面我们将通过非递归算法来实现二叉树的中序遍历。

首先，我们需要定义一个栈来辅助我们进行中序遍历。

接着，我们从根节点开始，将所有左子节点入栈直至没有左子节点为止。

然后弹出栈顶节点并输出，再将其右子节点入栈。

接着继续对右子节点进行相同的操作，直至栈为空为止。

下面我们来详细讲解一下如何使用非递归算法实现二叉树的中序遍历。

首先，我们定义一个栈用于辅助遍历：stack<TreeNode*> s;然后，我们定义一个指针p指向根节点，并进行循环操作直至栈为空：while(p || !s.empty()) {while(p) {s.push(p); //将当前节点入栈p = p->left; //继续遍历左子树}p = s.top(); //弹出栈顶节点并输出s.pop();cout << p->val << " ";p = p->right; //将右子节点入栈}我们先来看一下这个算法的流程。

首先，我们定义一个栈s和一个指针p，指针p初始指向二叉树的根节点。

然后我们进入一个while 循环，条件是指针p不为空或者栈不为空。

在循环内部，我们首先对左子树进行遍历，将遇到的节点依次入栈。

当左子树遍历完毕后，我们弹出栈顶节点并输出，然后将指针p指向当前节点的右子节点，继续遍历右子树。

直至栈为空，说明遍历结束。

这种非递归算法实现二叉树的中序遍历的时间复杂度为O(n)，其中n为节点的个数。

空间复杂度为O(n)，因为栈中最多同时保存树中所有节点。

算法的实现比较简单，代码也比较清晰易懂，适合在实际应用中使用。

下面我们将通过一个具体的例子来演示这个算法是如何工作的。

假设我们有如下的二叉树：1/ \2 3/ \4 5首先，我们定义一个根节点指针p指向根节点1。

c语言非递归遍历二叉树C语言非递归遍历二叉树二叉树是一种常见的数据结构，其遍历方式有前序遍历、中序遍历和后序遍历三种。

在C语言中，我们可以使用递归和非递归两种方式来实现二叉树的遍历。

本文将介绍如何使用非递归方式来实现二叉树的遍历。

1. 前序遍历前序遍历的顺序是先访问根节点，然后访问左子树，最后访问右子树。

使用非递归方式实现前序遍历可以使用栈来辅助实现。

具体步骤如下：1. 将根节点入栈。

2. 当栈不为空时，弹出一个节点并访问它。

3. 如果该节点有右子节点，则将右子节点入栈。

4. 如果该节点有左子节点，则将左子节点入栈。

5. 重复步骤2-4直到所有节点都被访问过。

以下是代码示例：```cvoid preOrderTraversal(TreeNode* root) { if (root == NULL) {return;}Stack* stack = createStack();push(stack, root);while (!isEmpty(stack)) {TreeNode* node = pop(stack);printf("%d ", node->val);if (node->right != NULL) {push(stack, node->right);}if (node->left != NULL) {push(stack, node->left);}}destroyStack(stack);}```2. 中序遍历中序遍历的顺序是先访问左子树，然后访问根节点，最后访问右子树。

使用非递归方式实现中序遍历同样可以使用栈来辅助实现。

具体步骤如下：1. 将根节点入栈。

2. 如果该节点有左子节点，则将左子节点入栈。

3. 如果该节点没有左子节点，则弹出一个节点并访问它，如果该节点有右子节点，则将右子节点入栈。

4. 重复步骤2-3直到所有节点都被访问过。

C语言二叉树的非递归创建介绍二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。

在C 语言中，我们可以使用递归或非递归的方式来创建二叉树。

本文将介绍如何使用非递归的方式创建二叉树，并提供相应的代码示例。

非递归创建二叉树的思路非递归创建二叉树的思路是使用栈来辅助实现。

我们可以按照先序遍历的方式输入节点的值，如果输入的值不为空，则创建一个新节点，并将其压入栈中。

然后从栈中取出一个节点，再次输入左子节点的值，如果不为空则创建新节点，并将其作为当前节点的左子节点，同时将新节点压入栈中。

接着输入右子节点的值，如果不为空则创建新节点，并将其作为当前节点的右子节点，同时将新节点压入栈中。

重复以上步骤，直到栈为空。

代码示例下面是一个用C语言实现的非递归创建二叉树的代码示例：#include <stdio.h>#include <stdlib.h>typedef struct TreeNode {int value;struct TreeNode* left;struct TreeNode* right;} TreeNode;typedef struct StackNode {TreeNode* treeNode;struct StackNode* next;} StackNode;void push(StackNode** top, TreeNode* treeNode) {StackNode* stackNode = (StackNode*)malloc(sizeof(StackNode));stackNode->treeNode = treeNode;stackNode->next = *top;*top = stackNode;}TreeNode* pop(StackNode** top) {if (*top == NULL) {return NULL;}TreeNode* treeNode = (*top)->treeNode;StackNode* temp = *top;*top = (*top)->next;free(temp);return treeNode;}TreeNode* createBinaryTree() {int value;TreeNode* root = NULL;printf("请输入根节点的值（-1表示空节点）：");scanf("%d", &value);if (value == -1) {return NULL;}root = (TreeNode*)malloc(sizeof(TreeNode));root->value = value;root->left = root->right = NULL;StackNode* stack = NULL;push(&stack, root);while (stack != NULL) {TreeNode* currentNode = pop(&stack);printf("请输入节点%d的左子节点的值（-1表示空节点）：", currentNode->v alue);scanf("%d", &value);if (value != -1) {TreeNode* leftNode = (TreeNode*)malloc(sizeof(TreeNode));leftNode->value = value;leftNode->left = leftNode->right = NULL;currentNode->left = leftNode;push(&stack, leftNode);}printf("请输入节点%d的右子节点的值（-1表示空节点）：", currentNode->v alue);scanf("%d", &value);if (value != -1) {TreeNode* rightNode = (TreeNode*)malloc(sizeof(TreeNode));rightNode->value = value;rightNode->left = rightNode->right = NULL;currentNode->right = rightNode;push(&stack, rightNode);}}return root;}void preOrderTraversal(TreeNode* root) {if (root == NULL) {return;}printf("%d ", root->value);preOrderTraversal(root->left);preOrderTraversal(root->right);}int main() {TreeNode* root = createBinaryTree();printf("先序遍历结果：");preOrderTraversal(root);printf("\n");return 0;}使用说明1.运行程序后，按照提示输入根节点的值。

c语言非递归层次遍历二叉树层次遍历二叉树是指按照树的层次，从上往下、从左往右的顺序遍历二叉树的所有节点。

具体实现层次遍历二叉树的方法是使用队列数据结构，首先将根节点入队列，然后循环遍历队列中的节点，并将每个节点的左右孩子节点入队列，直到队列为空为止。

下面我将详细介绍如何在C语言中实现非递归层次遍历二叉树。

首先，我们需要定义二叉树的数据结构，如下所示：ctypedef struct node{int data; 节点数据struct node *left; 左孩子节点指针struct node *right; 右孩子节点指针}Node;创建新节点Node* createNode(int data){Node* newNode = (Node*)malloc(sizeof(Node));if(newNode == NULL){printf("内存分配失败！\n");exit(1);}newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;}构建二叉树Node* buildTree(){Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->left = createNode(6);root->right->right = createNode(7);return root;}接下来，我们需要使用队列来实现非递归层次遍历二叉树。

下面是实现代码：cvoid levelOrderTraversal(Node* root){if(root == NULL){return;}Queue* queue = createQueue(); 创建队列enqueue(queue, root); 根节点入队列while(!isEmpty(queue)){Node* current = dequeue(queue); 出队列printf("%d ", current->data); 打印当前节点的数据将当前节点的左右孩子节点依次入队列if(current->left != NULL){enqueue(queue, current->left);}if(current->right != NULL){enqueue(queue, current->right);}}}创建队列typedef struct queue{int front; 队头指针int rear; 队尾指针int size; 队列大小Node array; 存储节点指针的数组}Queue;Queue* createQueue(){Queue* queue = (Queue*)malloc(sizeof(Queue));if(queue == NULL){printf("内存分配失败！\n");exit(1);}queue->front = 0;queue->rear = -1;queue->size = 0;queue->array = (Node)malloc(MAX_SIZE * sizeof(Node*));if(queue->array == NULL){printf("内存分配失败！\n");exit(1);}return queue;}判断队列是否为空int isEmpty(Queue* queue){return queue->size == 0;}入队列void enqueue(Queue* queue, Node* node){if(queue->rear == MAX_SIZE - 1){printf("队列已满！\n");exit(1);}queue->array[++queue->rear] = node;queue->size++;}出队列Node* dequeue(Queue* queue){if(isEmpty(queue)){printf("队列为空！\n");exit(1);}Node* node = queue->array[queue->front];queue->front++;queue->size;return node;}以上就是在C语言中实现非递归层次遍历二叉树的方法。

⽤⾮递归的⽅法中序遍历⼆叉树写这篇纯属个⼈兴趣了要遍历⼆叉树的话优先推荐⽤递归的⽅法在传统的遍历⼆叉树时，如果要使⽤递归的⽅法前序遍历：void FrontOrder(biTree *s){ if(s){ printf("%d",s->data); FrontOrder(s->lchild); FrontOrder(s->rchild); }}中序遍历：void InOrder(biTree *s){ if(s){ InOrder(s->lchild); printf("%d",s->data); InOrder(s->rchild); }}后续遍历：void PostOrder(biTree *s){ if(s){ PostOrder(s->lchild); PostOrder(s->rchild); printf("%d",s->data); }}⽤栈的话 ，话不多说，上代码#include <stdio.h>#define maxsize 24typedef struct node{char data;struct node *lchild;struct node *rchild;}biTree;biTree * Q[maxsize];biTree * Creat(){char ch;int front,rear;biTree *root,*s;root = NULL;// ----------front = 1;rear = 0;// ----------置空队列ch = getchar();while(ch!='#'){s = NULL;if(ch!='@'){s = (biTree*)malloc(sizeof(biTree)); s->data = ch;s->lchild = NULL;s->rchild = NULL;}rear++;Q[rear] = s;if(rear==1)root = s;else{if(s&&Q[front]){if(rear%2==0)Q[front]->lchild = s;else Q[front]->rchild = s;}if(rear%2==1)front++;}ch = getchar();}return root;}typedef struct{biTree data[maxsize];int top;}seq;void setnull(seq *s){s->top = -1;}seq *PUSH(seq *s,biTree x){if(s->top==maxsize-1){printf("overflow\n");return (NULL);}else{s->top++;s->data[s->top] = x;}return s;}int empty(seq *s){if(s->top>=0)return0;else return1;}biTree POP(seq *s){biTree *emp = NULL;if(empty(s)){printf("underflow.\n");return *emp;}else{s->top--;return (s->data[s->top+1]);}}biTree *top(seq *s){biTree *emp = NULL;if(empty(s)){printf("stack is empty.\n");return emp;}else return (&s->data[s->top]);}void inOrder(biTree *t){biTree *root = t;seq s;setnull(&s);if(t){while(root||!empty(&s)){while(root){PUSH(&s, *root);root = root->lchild;}if(!empty(&s)){printf("%c ",s.data[s.top].data);root = top(&s);root = root->rchild;POP(&s);}}}}int main(){biTree *root = Creat();inOrder(root);printf("\n");return0;}解释⼀下函数的运⾏过程void inOrder(biTree *t){biTree *root = t;seq s;setnull(&s);if(t){while(root||!empty(&s)){while(root){PUSH(&s, *root);root = root->lchild;}if(!empty(&s)){printf("%c ",s.data[s.top].data);root = top(&s);root = root->rchild;POP(&s);}}}}1、当节点 t ⾮空的话读如⼆叉树2、如果当前节点不为 “空或者栈⾮空” 开始循环3、内部循环： 当前节点⾮空时，把当前节点压⼊栈，然后⼀直找到它的左孩⼦为空 找完左孩⼦，开始你要进⾏的操作 当栈⾮空时，输出当前节点的数据 根结点指向右孩⼦，根结点出栈4、下⼀步就开始找右孩⼦的左⼦树，开始下⼀步循环直到栈空并且当前节点为NULL ⼤家也可以⾃⼰搜索流程图辅助理解。

⼆叉树的遍历：先序中序后序遍历的递归与⾮递归实现及层序遍历 对于⼀种数据结构⽽⾔，遍历是常见操作。

⼆叉树是⼀种基本的数据结构，是⼀种每个节点的⼉⼦数⽬都不多于2的树。

⼆叉树的节点声明如下：1 typedef struct TreeNode *PtrToNode;2 typedef struct TreeNode *BinTree;34struct TreeNode5{6int Data; //为简单起见，不妨假设树节点的元素为int型7 BinTree Left;8 BinTree Right;9 }; ⼆叉树的遍历主要有先序遍历，中序遍历，后序遍历，层序遍历四种⽅式，下⾯⼀⼀介绍。

1. 先序遍历 在先序遍历中，对节点的访问⼯作是在它的左右⼉⼦被访问之前进⾏的。

换⾔之，先序遍历访问节点的顺序是根节点-左⼉⼦-右⼉⼦。

由于树可以通过递归来定义，所以树的常见操作⽤递归实现常常是⽅便清晰的。

递归实现的代码如下：1void PreOrderTraversal(BinTree BT)2{3if( BT )4 {5 printf(“%d\n”, BT->Data); //对节点做些访问⽐如打印6 PreOrderTraversal(BT->Left); //访问左⼉⼦7 PreOrderTraversal(BT->Right); //访问右⼉⼦8 }9 } 由递归代码可以看出，该递归为尾递归（即递归形式在函数末尾或者说在函数即将返回前）。

尾递归的递归调⽤需要⽤栈存储调⽤的信息，当数据规模较⼤时容易越出栈空间。

虽然现在⼤部分的编译器能够⾃动去除尾递归，但是即使如此，我们不妨⾃⼰去除。

⾮递归先序遍历算法基本思路：使⽤堆栈 a. 遇到⼀个节点，访问它，然后把它压栈，并去遍历它的左⼦树； b. 当左⼦树遍历结束后，从栈顶弹出该节点并将其指向右⼉⼦，继续a步骤； c. 当所有节点访问完即最后访问的树节点为空且栈空时，停⽌。

【经典⾯试题⼆】⼆叉树的递归与⾮递归遍历（前序、中序、后序）【写在前⾯】 ⼆叉树是⼀种⾮常重要的数据结构，很多其它数据结构都是基于⼆叉树的基础演变⽽来的。

对于⼆叉树，有前序、中序以及后序三种遍历⽅法。

因为树的定义本⾝就是递归定义，因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很简洁。

⽽对于树的遍历若采⽤⾮递归的⽅法，就要采⽤栈去模拟实现。

在三种遍历中，前序和中序遍历的⾮递归算法都很容易实现，⾮递归后序遍历实现起来相对来说要难⼀点。

⼀.前序遍历 前序遍历按照“根结点-左孩⼦-右孩⼦”的顺序进⾏访问。

1.递归实现1void preOrder1(BinTree *root) //递归前序遍历2 {3if(root!=NULL)4 {5 cout<<root->data<<"";6 preOrder1(root->lchild);7 preOrder1(root->rchild);8 }9 } 2.⾮递归实现 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩⼦和右孩⼦。

即对于任⼀结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩⼦不为空，按相同规则访问它的左⼦树；当访问其左⼦树时，再访问它的右⼦树。

因此其处理过程如下： 对于任⼀结点P：1)访问结点P，并将结点P⼊栈;2)判断结点P的左孩⼦是否为空，若为空，则取栈顶结点并进⾏出栈操作，并将栈顶结点的右孩⼦置为当前的结点P，循环⾄1);若不为空，则将P的左孩⼦置为当前的结点P;3)直到P为NULL并且栈为空，则遍历结束。

1void preOrder2(BinTree *root) //⾮递归前序遍历2 {3 stack<BinTree*> s;4 BinTree *p=root;5while(p!=NULL||!s.empty())6 {7while(p!=NULL)8 {9 cout<<p->data<<"";10 s.push(p);11 p=p->lchild;12 }13if(!s.empty())14 {15 p=s.top();16 s.pop();17 p=p->rchild;18 }19 }20 }⼆.中序遍历 中序遍历按照“左孩⼦-根结点-右孩⼦”的顺序进⾏访问。

C语⾔数据结构之⼆叉树的⾮递归后序遍历算法C语⾔数据结构之⼆叉树的⾮递归后序遍历算法前⾔：前序、中序、后序的⾮递归遍历中，要数后序最为⿇烦，如果只在栈中保留指向结点的指针，那是不够的，必须有⼀些额外的信息存放在栈中。

⽅法有很多，这⾥只举⼀种，先定义栈结点的数据结构typedef struct{Node * p; int rvisited;}SNode //Node 是⼆叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。

lastOrderTraverse(BiTree bt){ //⾸先，从根节点开始，往左下⽅⾛，⼀直⾛到头，将路径上的每⼀个结点⼊栈。

p = bt; while(bt){ push(bt, 0); //push到栈中两个信息，⼀是结点指针，⼀是其右结点是否被访问过 bt = bt.lchild; } //然后进⼊循环体 while(!Stack.empty()){ //只要栈⾮空 sn = Stack.getTop(); // sn是栈顶结点 //注意，任意⼀个结点N，只要他有左孩⼦，则在N⼊栈之后，N的左孩⼦必然也跟着⼊栈了(这个体现在算法的后半部分)，所以当我们拿到栈顶元素的时候，可以确信这个元素要么没有左孩⼦，要么其左孩⼦已经被访问过，所以此时我们就不关⼼它的左孩⼦ //若其右孩⼦已经被访问过，或是该元素没有右孩⼦，则由后序遍历的定义，此时可以visit这个结点了。

if(!sn.p.rchild || sn.rvisited){ p = pop(); visit(p); } else //若它的右孩⼦存在且rvisited为0，说明以前还没有动过它的右孩⼦，于是就去处理⼀下其右孩⼦。

{ //此时我们要从其右孩⼦结点开始⼀直往左下⽅⾛，直⾄⾛到尽头，将这条路径上的所有结点都⼊栈。

//当然，⼊栈之前要先将该结点的rvisited设成1，因为其右孩⼦的⼊栈意味着它的右孩⼦必将先于它被访问(这很好理解，因为我们总是从栈顶取出元素来进⾏visit)。

二叉树的中序非递归遍历算法
1. 什么是二叉树
二叉树是一种常见的树状数据结构，它由一组节点组成，每个节点最多有两个子节点。

每个节点都包含一个值和指向其子节点的引用。

2. 什么是中序遍历
中序遍历是一种遍历二叉树的方式，它按照左子树、根节点、右子树的顺序访问二叉树的所有节点。

3. 什么是非递归遍历
非递归遍历是指不使用递归的方法进行遍历，而是使用循环和栈等数据结构来模拟递归的过程。

现在，我将介绍二叉树的中序非递归遍历算法：
1. 创建一个栈来辅助遍历。

2. 初始化指针cur指向根节点，并将cur入栈。

3. 当栈不为空时，执行以下操作：
a. 如果cur的左子节点不为空，将cur指向其左子节点，并将cur 入栈。

b. 如果cur的左子节点为空，表示已经到达最左边的节点，可以
开始访问节点。

弹出栈顶元素并输出。

c. 如果cur的右子节点不为空，将cur指向其右子节点，并将cur 入栈。

d. 如果cur的右子节点为空，表示该节点及其左子树已经访问完毕，继续弹出栈顶元素并输出。

4. 重复步骤3直到栈为空。

这个算法的思想是利用栈的先进后出特性来模拟递归的过程，通过不断将节点入栈和出栈来实现中序遍历。

通过以上算法，我们可以实现二叉树的中序非递归遍历。

这种方法的时间复杂度是O(n)，其中n是二叉树节点的个数，空间复杂度是O(h)，其中h是二叉树的高度。

void POrder(struct User* pRoot) //非递归前序调用{//（1）将根作为当前节点//（2）若当前节点不为空，则打印当前节点，并将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。

//（3）否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。

stack<struct User*> s1;struct User *pRootTemp=pRoot; //位置指针//（1）将根作为当前节点while(1){//（2）若当前节点不为空，则打印当前节点，并将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。

if (pRootTemp!=NULL){printf("%s",pRootTemp->cName);s1.push(pRootTemp);pRootTemp=pRootTemp->pNext[0];}else{//（3）否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。

pRootTemp=s1.top();s1.pop();pRootTemp=pRootTemp->pNext[1];if ((pRootTemp==NULL) && (s1.empty())) break;}}}void MOrder(struct User* pRoot) //非递归完成中序遍历{//（1）将根作为当前节点//（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。

//（3）否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。

stack<struct User*> s1;struct User *pRootTemp=pRoot; //位置指针//（1）将根作为当前节点while(1){//（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。

⼆叉树的三种遍历⾮递归实现1.⼆叉树前序遍历的⾮递归实现* 实现思路，先序遍历是要先访问根节点，然后再去访问左⼦树以及右⼦树，这明显是递归定义，但这⾥是⽤栈来实现的* ⾸先需要先从栈顶取出节点，然后访问该节点，如果该节点不为空，则访问该节点，同时把该节点的右⼦树先⼊栈，然后* 左⼦树⼊栈。

循环结束的条件是栈中不在有节点。

即 !s.empty()public void preOrder(Node root) {Stack<Node> s = new Stack<Node>();s.push(root);Node p = null;while (!s.empty()) {p = s.pop();if (p != null) {System.out.print(p.val+" ");s.push(p.right);s.push(p.left);}}}2.⼆叉树的中序遍历⾮递归实现* 实现思路，中序遍历是要先遍历左⼦树，然后跟节点，最后遍历右⼦树。

所以需要先把跟节点⼊栈然后在⼀直把左⼦树⼊栈* 直到左⼦树为空，此时停⽌⼊栈。

栈顶节点就是我们需要访问的节点，取栈顶节点p并访问。

然后改节点可能有右⼦树，所以* 访问完节点p后还要判断p的右⼦树是否为空，如果为空则接下来要访问的节点在栈顶，所以将p赋值为null。

如果不为空则* 将p赋值为其右⼦树的值。

循环结束的条件是p不为空或者栈不为空。

public void inOrder(Node root) {Stack<Node> s = new Stack<Node>();Node p = root;do {while (p != null) {s.push(p);p = p.left;}p = s.pop();System.out.print(p.val+" ");if (p.right != null) {p = p.right;}else p = null;} while(p != null || !s.empty());}3.⼆叉树的后序遍历⾥⾮递归实现* 实现思路，在进⾏后序遍历的时候是先要遍历左⼦树，然后在遍历右⼦树，最后才遍历根节点。

#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define STACK_INT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2typedef char TElemType;typedef int Status;typedef char SElemType;//二叉树的二叉链表存储表示typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild; //左右孩子指针}BiTNode, *BiTree;//用于存储二叉树结点的栈typedef struct{BiTree *base;BiTree *top;int stacksize; //当前已分配的存储空间}SqStack;//定义链式队列结点typedef struct QNode{BiTree Queuedata;struct QNode * next;}QNode,* QueuePtr;//定义链式队列typedef struct{QueuePtr front; //QueuePtr rear;}LinkQueue;//创建存储二叉树结点的空栈Status InitStack(SqStack &S){S.base = (BiTree *) malloc(sizeof(BiTree));if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INT_SIZE;return OK;}//存储二叉树结点的栈的取栈顶元素Status GetTop(SqStack &S, BiTree &e){//若栈不空，则用e返回S的栈顶元素if(S.top == S.base) return ERROR;e = *(S.top-1);return OK;}//存储二叉树结点的栈的入栈操作Status Push(SqStack &S, BiTree e){//插入元素e为栈顶元素if(S.top - S.base >= S.stacksize){ //若栈满，则追加存储空间S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree));if(!S.base) return ERROR;S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top = e;S.top++;return OK;}//用于存储二叉树结点的栈出栈操作Status Pop(SqStack &S,BiTree &e){//删除S的栈顶元素，并用e返回if(S.base == S.top) return ERROR;S.top--;e = *S.top;return OK;}//判断存储二叉树结点的栈是否为空Status StackEmpty(SqStack S){// 若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top == S.base) return TRUE;else return FALSE;//先序顺序创建一颗二叉树Status PreOrderCreateBiTree(BiTree &T){//按先序次序输入二叉树中结点的值//构造二叉链表表示的二叉树Tchar ch;scanf("%c",&ch);if(ch == '0') T = NULL;else{//if(!(T = (BiTree ) malloc(sizeof(BiTree)))) exit(OVERFLOW);//作用和下一语句的作用相同，注意两者的区别if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data = ch; //生成根结点PreOrderCreateBiTree(T->lchild); //构造左子树PreOrderCreateBiTree(T->rchild); //构造右子树}return OK;} //CreateBiTree//递归先序遍历二叉树void PreOrder ( BiTree bt ){if ( bt ){printf("%c",bt->data); //先访问根节点PreOrder ( bt->lchild );//遍历左子树PreOrder ( bt->rchild ); //遍历右子树}}//递归中序遍历二叉树void Inorder ( BiTree bt ){if ( bt ){Inorder ( bt->lchild ); //遍历左子树printf("%c",bt->data);//访问根节点Inorder ( bt->rchild );//遍历右子树}}//递归后序遍历二叉树void LastOrder ( BiTree bt ){if ( bt )LastOrder( bt->lchild );//遍历左子树LastOrder( bt->rchild );//遍历右子树printf("%c",bt->data);//访问根节点}}//非递归先序遍历二叉树方法一：Status PreOrderTraverse(BiTree T){SqStack s;BiTree P=T;InitStack(s);while ( P!=NULL || !StackEmpty(s)){if (P!=NULL){printf("%c",P->data);Push(s,P); //访问完之后将根节点入栈P=P->lchild;}else{Pop(s,P);P=P->rchild;}}return OK;}//非递归先序遍历二叉树方法二：Status PreOrderTraverse2(BiTree T){SqStack s;BiTree P=T;InitStack(s);Push(s,P); //先将根节点入栈while ( !StackEmpty(s)){Pop(s,P);if (P!=NULL){printf("%c",P->data);//访问根节点Push(s,P->rchild);// 先进栈，后访问，所以这里先让右子树进栈Push(s,P->lchild);}return OK;}//非递归中序遍历二叉树Status InOrderTraverse(BiTree T){//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit,也就是printf()函数SqStack S;InitStack(S);BiTree p;p = T;/**/while(p || !StackEmpty(S)){if(p){Push(S,p);p = p->lchild; //根指针进栈，遍历左子树}else{ //根指针退栈，访问根结点，遍历右子树Pop(S,p);printf("%c",p->data);p = p->rchild;}}//while/*和上面的while开始的操作完全等同，可以视为方法二：Push(S,p);while (!StackEmpty(S)){while (GetTop(S,p) && p){Push(S,p->lchild);}Pop(S,p);if (!StackEmpty(S)){Pop(S,p);printf("%c",p->data);Push(S,p->rchild);}*/return OK;} //InOrderTraverse/**///非递归后序遍历二叉树：Status LastOrderTraverse(BiTree T){//后序遍历时，分别从左子树和右子树共两次返回根结点，//只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。