【数据结构】--- 二叉树的递归遍历和非递归遍历【C语言实现】

比眉伴天荒 2023-02-27 12:17 126阅读 0赞

**目录**

1. 创建一颗二叉树

2.递归前序遍历二叉树

3.递归中序遍历二叉树

4.递归后序遍历二叉树

5. 测试递归打印二叉树代码

6. 非-递归前序遍历二叉树

7. 非-递归实现中序遍历二叉树

8. 非 - 递归实现后序遍历【较为复杂的方法】

9. 非 - 递归实现后序遍历【简单的方法】

10. 二叉树的层次遍历

11. 最后：附全部代码：

--------------------

对于二叉树的非递归 深度优先遍历，使用的都是栈

对于二叉树的层次遍历，使用的是队列

### 1. 创建一颗二叉树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

依据前序遍历创建二叉树：,树结构如上图所示

输入： ABD\#\#E\#\#C\#\#

#include <stdio.h>
    #include <stdlib.h>
    
    
    // 二叉树的实现
    
    // 定义 二叉树的 结构体
    typedef struct node{
    	char data;
    	struct node *left;
    	struct node *right;
    }Node, *Tree;
    
    // 依据前序遍历创建二叉树
    // 根左右： ABD##E##C##
    
    Tree create_tree(){
    	Node *root = NULL;
    	char ch;
    	scanf("%c", &ch); // 输入 ABD##E##C##
    
    	if (ch != '#'){
    		root = (Node*)malloc(sizeof(Node));
    		root->data = ch;
    
    		root->left = create_tree(); // 递归创建
    		root->right = create_tree();
    	}
    	else{
    		root = NULL;
    	}
    
    	return root;
    }

### 2.递归前序遍历二叉树 ###

// 递归前序遍历二叉树
    void preOrderRec(Tree root){
    	if (root != NULL){
    		printf(" %c - ", root->data);
    		preOrderRec(root->left);
    		preOrderRec(root->right);
    	}
    }

### 3.递归中序遍历二叉树 ###

// 递归中序遍历二叉树
    void inOrderRec(Tree root){
    	if (root != NULL){
    		inOrderRec(root->left);
    		printf(" %c - ", root->data);
    		inOrderRec(root->right);
    	}
    }

### 4.递归后序遍历二叉树 ###

void backOrderRec(Tree root){
    	if (root != NULL){
    		backOrderRec(root->left);
    		backOrderRec(root->right);
    		printf(" %c - ", root->data);
    		
    	}
    }

### 5. 测试递归打印二叉树代码 ###

int main(){
    
    	printf("starting ------ \n");
    
    
    	Tree root = create_tree();
    	printf("递归前序遍历--- \n");
    	preOrderRec(root);
    	printf("\n");
    	printf("递归中序遍历--- \n");
    	inOrderRec(root);
    	printf("\n");
    	printf("递归后序遍历--- \n");
    	backOrderRec(root);
    	printf("\n");
    
    
    
    
    	return 0;
    }

### 6. 非-递归前序遍历二叉树 ###

前序遍历顺序是：根-左-右

**先打印根节点的值，由于栈是先进后出，所以先将 右子树放进去，再将左子树放进去**

// 非-递归前序遍历二叉树
    void preOrderNRec(Tree root){
    	Tree stack[MAXSIZE], node;
    	int k = -1;
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	else{
    		k++;
    		// 仿照一个栈
    		stack[k] = root; // 将根节点入栈
    		while (k > -1){
    			//出栈
    			node = stack[k--];
    			printf(" %c - ", node->data);
    
    			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
    			if (node->right != NULL){
    				stack[++k] = node->right;
    			}
    			if (node->left != NULL){
    				stack[++k] = node->left;
    			}
    
    		}
    
    	}
    }

### 7. 非-递归实现中序遍历二叉树 ###

中序遍历的非递归方式实现思想是：

1. 从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，

2. 从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。

// 非-递归实现中序遍历二叉树
    void inOrderNRec(Tree root){
    	Tree stack[MAXSIZE], node;
    	int top = 0;
    	// 判断树是否为空
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	node = root;
    
    	while (node != NULL || top > 0){
    
    		// 将所有的左子树节点入栈
    		while (node != NULL){
    			stack[++top] = node;
    			node = node->left;
    		}
    		//  如果右节点为空的话，执行下列语句
    		node = stack[top--];
    		printf(" %c - ", node->data);
    
    		// 扫描右节点
    		node = node->right;
    	}
    
    }

### 8. 非 - 递归实现后序遍历【较为复杂的方法】 ###

void backOrderNRec(Tree root){
    
    	Node *p = root;
    	Node *stack[MAXSIZE];
    	int num = 0;
    	Node *have_visited = NULL;
    
    	while (NULL != p || num>0)
    	{
    		while (NULL != p)
    		{
    			stack[num++] = p;
    			p = p->left;
    		}
    		p = stack[num - 1];
    		if (NULL == p->right || have_visited == p->right)
    		{
    			printf(" %c - ", p->data);
    			num--;
    			have_visited = p;
    			p = NULL;
    		}
    		else
    		{
    			p = p->right;
    		}
    	}
    	
    }

### 9. 非 - 递归实现后序遍历【简单的方法】 ###

非递归实现后序遍历还是很复杂的，变来变去，指来指去的

**但是，我发现一种简单的方法**

我们知道 后序遍历的顺序为：

后序：左->右->根

**那么可以把后序当作：根->右->左，最后再反转回来即可。**

由于我们是使用的栈，所以先保存根节点， 然后先放进去 左节点，再放 进去 右节点

void backOrderNRecSimple(Tree root){
    	Tree stack[MAXSIZE], node;
    	int top = 0;
    	int count = 0;
    	char array[MAXSIZE]; // 使用一个数组来保存数据，方便最后数组的反转
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	else{
    		top++;
    		// 仿照一个栈
    		stack[top] = root; // 将根节点入栈
    		while (top > 0){
    			//出栈
    			node = stack[top--];
    			array[count++] = node->data; // 将其保存在一个数组当中
    
    			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
    			if (node->left != NULL){
    				stack[++top] = node->left;  // 入栈
    			}
    			if (node->right != NULL){
    				stack[++top] = node->right;
    			}
    
    		}
    
    	}
    	// 反转数组，输出
    	for (int i = count-1; i >= 0; i--){
    		printf(" %c - ", array[i]);
    	}
    
    }

**附上java代码，更为简单：**

ArrayList<Integer> postOrder(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (root != null) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                list.add(node.val);
                if (node.left != null) {
                    stack.push(node.left);
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
            }
            //反转
            Collections.reverse(list);
        }
        return list;
    }

### 10. 二叉树的层次遍历 ###

层次遍历使用的是 队列来实现

void Level_traversal(Tree root){
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    
    	Tree stack[MAXSIZE], node;
    	node = root;
    	int front = 0;  // 使用 front， rear模拟队列
    	int rear = 0;
    
    	stack[rear++] = node;
    
    	while (front != rear){
    
    		node = stack[front++]; // 模拟队列，先获取front当前元素，然后在指向 front ++ 位元素
    		printf(" %c - ", node->data);
    		
    		// 左右子树入队列
    		if (node->left != NULL){
    			stack[rear++] = node->left;
    		}
    
    		if (node->right != NULL){
    			stack[rear++] = node->right;
    		}
    	}
    
    }

### 11. 最后：附全部代码： ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 100
    
    
    // 二叉树的实现
    
    // 定义 二叉树的 结构体
    typedef struct node{
    	char data;
    	struct node *left;
    	struct node *right;
    }Node, *Tree;
    
    // 依据前序遍历创建二叉树
    // 根左右： ABD##E##C##
    
    Tree create_tree(){
    	Node *root = NULL;
    	char ch;
    	scanf("%c", &ch); // 输入 ABD##E##C##
    
    	if (ch != '#'){
    		root = (Node*)malloc(sizeof(Node));
    		root->data = ch;
    
    		root->left = create_tree(); // 递归创建
    		root->right = create_tree();
    	}
    	else{
    		root = NULL;
    	}
    
    	return root;
    }
    
    
    // 递归前序遍历二叉树
    void preOrderRec(Tree root){
    	if (root != NULL){
    		printf(" %c - ", root->data);
    		preOrderRec(root->left);
    		preOrderRec(root->right);
    	}
    }
    
    // 非-递归前序遍历二叉树
    void preOrderNRec(Tree root){
    	Tree stack[MAXSIZE], node;
    	int top = 0;
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	else{
    		top++;
    		// 仿照一个栈
    		stack[top] = root; // 将根节点入栈
    		while (top > 0){
    			//出栈
    			node = stack[top--];
    			printf(" %c - ", node->data);
    
    			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
    			if (node->right != NULL){
    				stack[++top] = node->right;  // 入栈
    			}
    			if (node->left != NULL){
    				stack[++top] = node->left;
    			}
    
    		}
    
    	}
    }
    
    
    // 递归中序遍历二叉树
    void inOrderRec(Tree root){
    	if (root != NULL){
    		inOrderRec(root->left);
    		printf(" %c - ", root->data);
    		inOrderRec(root->right);
    	}
    }
    
    // 非-递归实现中序遍历二叉树
    void inOrderNRec(Tree root){
    	Tree stack[MAXSIZE], node;
    	int top = 0;
    	// 判断树是否为空
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	node = root;
    
    	while (node != NULL || top > 0){
    
    		// 将所有的左子树节点入栈
    		while (node != NULL){
    			stack[++top] = node;
    			node = node->left;
    		}
    		//  如果右节点为空的话，执行下列语句
    		node = stack[top--];
    		printf(" %c - ", node->data);
    
    		// 扫描右节点
    		node = node->right;
    	}
    
    }
    
    
    // 递归后序遍历二叉树
    void backOrderRec(Tree root){
    	if (root != NULL){
    		backOrderRec(root->left);
    		backOrderRec(root->right);
    		printf(" %c - ", root->data);
    		
    	}
    }
    
    // 非 - 递归实现后序遍历
    void backOrderNRec(Tree root){
    
    	Node *p = root;
    	Node *stack[MAXSIZE];
    	int num = 0;
    	Node *have_visited = NULL;
    
    	while (NULL != p || num>0)
    	{
    		while (NULL != p)
    		{
    			stack[num++] = p;
    			p = p->left;
    		}
    		p = stack[num - 1];
    		if (NULL == p->right || have_visited == p->right)
    		{
    			printf(" %c - ", p->data);
    			num--;
    			have_visited = p;
    			p = NULL;
    		}
    		else
    		{
    			p = p->right;
    		}
    	}
    	
    }
    
    void backOrderNRecSimple(Tree root){
    	Tree stack[MAXSIZE], node;
    	int top = 0;
    	int count = 0;
    	char array[MAXSIZE]; // 使用一个数组来保存数据，方便最后数组的反转
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    	else{
    		top++;
    		// 仿照一个栈
    		stack[top] = root; // 将根节点入栈
    		while (top > 0){
    			//出栈
    			node = stack[top--];
    			array[count++] = node->data; // 将其保存在一个数组当中
    
    			// 先把右子树放进去，栈是先进去后出，所以下面的左子树先出
    			if (node->left != NULL){
    				stack[++top] = node->left;  // 入栈
    			}
    			if (node->right != NULL){
    				stack[++top] = node->right;
    			}
    
    		}
    
    	}
    	// 反转数组，输出
    	for (int i = count-1; i >= 0; i--){
    		printf(" %c - ", array[i]);
    	}
    
    }
    
    // 层次遍历，打印出二叉树的值
    void Level_traversal(Tree root){
    
    	if (root == NULL){
    		printf("tree is empty-- \n");
    		return;
    	}
    
    	Tree stack[MAXSIZE], node;
    	node = root;
    	int front = 0;  // 使用 front， rear模拟队列
    	int rear = 0;
    
    	stack[rear++] = node;
    
    	while (front != rear){
    
    		node = stack[front++]; // 模拟队列，先获取front当前元素，然后在指向 front ++ 位元素
    		printf(" %c - ", node->data);
    		
    		// 左右子树入队列
    		if (node->left != NULL){
    			stack[rear++] = node->left;
    		}
    
    		if (node->right != NULL){
    			stack[rear++] = node->right;
    		}
    	}
    
    }
    
    
    int main(){
    
    	printf("starting ------ \n");
    
    
    	Tree root = create_tree();
    	printf("递归前序遍历--- \n");
    	preOrderRec(root);
    	printf("\n");
    	printf("递归中序遍历--- \n");
    	inOrderRec(root);
    	printf("\n");
    	printf("递归后序遍历--- \n");
    	backOrderRec(root);
    	printf("\n");
    	printf("------------------\n");
    
    	printf("非递归实现前序遍历--- \n");
    	preOrderNRec(root);
    	printf("\n");
    
    	printf("非递归实现中序遍历--- \n");
    	inOrderNRec(root);
    	printf("\n");
    
    	printf("非递归实现后序遍历--- \n");
    	backOrderNRec(root);
    	printf("\n");
    
    	printf("非递归实现后序遍历  简单的方法 --- \n");
    	backOrderNRecSimple(root);
    	printf("\n");
    
    	printf("层次遍历 --- \n");
    	Level_traversal(root);
    	printf("\n");
    
    	
    
    	// ABD##E##C##
    
    
    	return 0;
    }

--------------------

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20230209/1556c74da9b9490b9190abed0caba9fa.png
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210105230611623.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1,size_16,color_FFFFFF,t_70#pic_center