///////////////////////
//bt.h
///////////////////////
#include <stdio.h>
#include "stack.h"
#ifndef _BT_H_
#define _BT_H_
typedef struct node{
struct node *left, *right;
int value;
}NODE, *P_NODE;
P_NODE initNode(P_NODE target);
void printNode(P_NODE target);
P_NODE init();
P_NODE addLeft(P_NODE target);
P_NODE addRight(P_NODE target);
void pre_re(P_NODE current);
void in_re(P_NODE current);
void post_re(P_NODE current);
void pre(P_NODE current);
void pre_f(P_NODE current);
void pre_lr(P_NODE current);
#endif
///////////////////////
//bt.c
///////////////////////
#include <stdio.h>
#include "stack.h"
#include "bt.h"
P_NODE root;
P_NODE initNode(P_NODE target){
target -> left = NULL;
target -> right = NULL;
target -> value = 0;
return target;
}
void printNode(P_NODE target){
printf("%p,%p,%d\n",target -> left, target -> right, target -> value);
}
P_NODE init(){
root = ((P_NODE)malloc(sizeof(NODE)));
//printNode(root);
initNode(root);
//printNode(root);
return root;
}
P_NODE addLeft(P_NODE target){
return initNode(target -> left = ((P_NODE)malloc(sizeof(NODE))));
}
P_NODE addRight(P_NODE target){
return initNode(target -> right = ((P_NODE)malloc(sizeof(NODE))));
}
void pre_re(P_NODE current){
if(current == NULL){
return;
}
printf("%d ", current -> value);
pre_re(current -> left);
pre_re(current -> right);
}
void in_re(P_NODE current){
if(current == NULL){
return;
}
in_re(current -> left);
printf("%d ", current -> value);
in_re(current -> right);
}
void post_re(P_NODE current){
if(current == NULL){
return;
}
post_re(current -> left);
post_re(current -> right);
printf("%d ", current -> value);
}
void pre(P_NODE current){
clear();
while(current != NULL || getPos() != -1){
if(current != NULL){
printf("%d ", current -> value);
push(current);
current = current -> left;
}else{
current = ((P_NODE)pop()) -> right;
}
}
clear();
}
void pre_f(P_NODE current){
if(current == NULL){
return;
}
clear();
push(current);
while(getPos() != -1){
printf("%d ", current -> value);
if(current -> right != NULL){
push(current -> right);
}
if(current -> left != NULL){
current = current -> left;
}else{
current = (P_NODE)pop();
}
}
clear();
}
void pre_lr(P_NODE current){
if(current == NULL){
return;
}
clear();
push(current);
while(getPos() != -1){
current = (P_NODE)pop();
printf("%d ", current -> value);
if(current -> right != NULL){
push(current -> right);
}
if(current -> left != NULL){
push(current -> left);
}
}
clear();
}
///////////////////////
//cc.c
///////////////////////
#include <stdio.h>
#include "bt.h"
extern P_NODE root;
int main(){
init();
P_NODE n1, n2, n3, n4, n5, n6;
n1 = root;
n1 -> value = 1;
n2 = addLeft(n1);
n2 -> value = 2;
n3 = addRight(n1);
n3 -> value = 3;
n4 = addLeft(n2);
n4 -> value = 4;
n5 = addRight(n2);
n5 -> value = 5;
n6 = addRight(n3);
n6 -> value = 6;
int n = 6;
void (*visitors[])(P_NODE current) = {pre_re, in_re, post_re, pre, pre_f, pre_lr};
int i;
for(i = 0; i < n; i++){
(visitors[i])(root);
printf("\n");
}
return 0;
}
分享到:
相关推荐
在深入探讨C语言实现二叉树的前序遍历(非递归)之前,我们首先应当理解何为二叉树以及前序遍历的基本概念。 ### 二叉树简介 二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常称为左子节点和右子...
### C语言实现二叉树的前序、中序、后续遍历(递归法) #### 一、前序遍历 前序遍历是二叉树遍历的一种方式,其顺序为“根节点 -> 左子树 -> 右子树”。这种遍历方式在很多应用场景中都非常有用,例如构建表达式树...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
在计算机科学中,二叉树是一种常见的...对于实际的编程实现,你需要根据提供的代码和数据进行调整,确保逻辑正确,并遵循二叉树遍历的规则。在进行这类问题的解决时,理解和熟悉二叉树的性质以及各种遍历方法至关重要。
在实际应用中,"tree-traversal-master"这个压缩包可能包含了一个关于二叉树遍历的项目,其中包括了实现这些遍历方法的源代码示例。通过学习和理解这些示例,你可以更好地掌握二叉树遍历的原理和技巧,从而在解决...
以上介绍了二叉树前序、中序和后序遍历的非递归实现。通过使用栈,这些算法避免了递归带来的潜在问题,如栈溢出,同时保持了良好的空间和时间效率。理解并掌握这些非递归遍历算法,对于深入学习数据结构和算法设计...
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...
本文将深入探讨四种常见的二叉树遍历方法:前序遍历、中序遍历、后序遍历以及层次遍历,并以C++编程语言为例,阐述如何实现这些遍历算法。 1. **前序遍历**(Preorder Traversal) 前序遍历的顺序是根节点 -> 左...
**前序遍历**是二叉树遍历的一种,其顺序为:根节点 -> 左子树 -> 右子树。在非递归实现中,我们可以使用栈来辅助完成。首先将根节点压入栈中,然后进入一个循环。在循环中,如果栈不为空,就弹出栈顶元素并访问,...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中,二叉树是一种常见的数据结构,它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础,通常有三种主要的遍历方式:...
总的来说,C语言实现的二叉树前序遍历程序提供了一个清晰的示例,让我们能够亲手实践并理解二叉树遍历的逻辑。无论是对初学者还是经验丰富的程序员,这样的实践都对提升编程技能和理解数据结构有极大的帮助。
**前序序列和中序序列构建二叉树**:给定一个二叉树的前序和中序遍历序列,可以唯一确定该二叉树。前序遍历的第一个元素是树的根,中序遍历中根节点左边的元素是左子树的中序遍历,右边的是右子树的中序遍历。通过...
二叉树前序,中序,后序,求深度的递归和非递归方法
通过理解递归和二叉树遍历的概念,我们可以有效地处理各种二叉树问题。在实际编程中,递归是一种强大的工具,可以简化复杂的问题,但同时需要注意递归深度可能导致的栈溢出问题。在某些情况下,非递归的迭代解决方案...
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
本主题主要关注非递归的二叉树前序遍历算法,它是数据结构学习的重要部分,尤其对于C语言编程者而言。 **前序遍历** 是一种遍历二叉树的方法,其顺序为:首先访问根节点,然后遍历左子树,最后遍历右子树。递归方法...
本教程将深入探讨如何在Python中实现二叉树的创建、前序遍历、中序遍历以及层次遍历。 首先,我们来理解二叉树的链式存储结构。在Python中,我们可以用类来表示二叉树的节点,每个节点包含一个值、一个指向左子节点...
这里我们将重点讨论如何在已知二叉树的前序和中序遍历的情况下,通过非递归算法实现后序遍历。 **前序遍历**:根节点 -> 左子树 -> 右子树 **中序遍历**:左子树 -> 根节点 -> 右子树 **后序遍历**:左子树 -> 右子...
在计算机科学中,二叉树遍历是访问二叉树所有节点的一种方法,常用于搜索、排序和数据组织等任务。本主题主要探讨的是在MFC(Microsoft Foundation Classes)环境中如何实现二叉树的前序、中序和后序遍历。 首先,...
### 二叉树的前序、中序与后序遍历 #### 一、引言 在计算机科学中,二叉树是一种常见的数据结构,它由一个根节点以及最多两个子节点(左子节点和右子节点)组成,每个子节点也可以是二叉树。在对二叉树进行操作时...