`
finecci
  • 浏览: 7389 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
最近访客 更多访客>>
社区版块
存档分类
最新评论

C二叉树前序遍历中序遍历后续遍历递归非递归

阅读更多
///////////////////////
//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语言实现二叉树的前序、中序、后续遍历(递归法)

    ### C语言实现二叉树的前序、中序、后续遍历(递归法) #### 一、前序遍历 前序遍历是二叉树遍历的一种方式,其顺序为“根节点 -&gt; 左子树 -&gt; 右子树”。这种遍历方式在很多应用场景中都非常有用,例如构建表达式树...

    二叉树先序遍历、中序遍历和后序遍历非递归算法 C++源码

    用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法

    根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)

    在计算机科学中,二叉树是一种常见的...对于实际的编程实现,你需要根据提供的代码和数据进行调整,确保逻辑正确,并遵循二叉树遍历的规则。在进行这类问题的解决时,理解和熟悉二叉树的性质以及各种遍历方法至关重要。

    二叉树的遍历,前序遍历 中序遍历 后序遍历

    在实际应用中,"tree-traversal-master"这个压缩包可能包含了一个关于二叉树遍历的项目,其中包括了实现这些遍历方法的源代码示例。通过学习和理解这些示例,你可以更好地掌握二叉树遍历的原理和技巧,从而在解决...

    二叉树前序、中序、后序三种遍历的非递归算法(C语言)

    以上介绍了二叉树前序、中序和后序遍历的非递归实现。通过使用栈,这些算法避免了递归带来的潜在问题,如栈溢出,同时保持了良好的空间和时间效率。理解并掌握这些非递归遍历算法,对于深入学习数据结构和算法设计...

    二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法

    本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...

    二叉树遍历-前序中序后序层次遍历

    本文将深入探讨四种常见的二叉树遍历方法:前序遍历、中序遍历、后序遍历以及层次遍历,并以C++编程语言为例,阐述如何实现这些遍历算法。 1. **前序遍历**(Preorder Traversal) 前序遍历的顺序是根节点 -&gt; 左...

    关于二叉树前序和后序的非递归遍历算法.rar

    **前序遍历**是二叉树遍历的一种,其顺序为:根节点 -&gt; 左子树 -&gt; 右子树。在非递归实现中,我们可以使用栈来辅助完成。首先将根节点压入栈中,然后进入一个循环。在循环中,如果栈不为空,就弹出栈顶元素并访问,...

    二叉树先序、中序、后序遍历非递归算法

    ### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中,二叉树是一种常见的数据结构,它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础,通常有三种主要的遍历方式:...

    C语言二叉树的前序遍历程序及实验报告

    总的来说,C语言实现的二叉树前序遍历程序提供了一个清晰的示例,让我们能够亲手实践并理解二叉树遍历的逻辑。无论是对初学者还是经验丰富的程序员,这样的实践都对提升编程技能和理解数据结构有极大的帮助。

    二叉树的各种遍历,二叉搜索树的建立,前中序构建二叉树

    **前序序列和中序序列构建二叉树**:给定一个二叉树的前序和中序遍历序列,可以唯一确定该二叉树。前序遍历的第一个元素是树的根,中序遍历中根节点左边的元素是左子树的中序遍历,右边的是右子树的中序遍历。通过...

    二叉树前序,中序,后序,和求深度的递归和非递归实现

    二叉树前序,中序,后序,求深度的递归和非递归方法

    递归建立二叉树与前序中序后续遍历

    通过理解递归和二叉树遍历的概念,我们可以有效地处理各种二叉树问题。在实际编程中,递归是一种强大的工具,可以简化复杂的问题,但同时需要注意递归深度可能导致的栈溢出问题。在某些情况下,非递归的迭代解决方案...

    C++ 二叉树的先序遍历、中序遍历和后序遍历非递归算法

    用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。

    非递归二叉树前序遍历.zip_C语言_SPO _数据结构 递归

    本主题主要关注非递归的二叉树前序遍历算法,它是数据结构学习的重要部分,尤其对于C语言编程者而言。 **前序遍历** 是一种遍历二叉树的方法,其顺序为:首先访问根节点,然后遍历左子树,最后遍历右子树。递归方法...

    python实现二叉树的创建、前序遍历、中序遍历以及层次遍历

    本教程将深入探讨如何在Python中实现二叉树的创建、前序遍历、中序遍历以及层次遍历。 首先,我们来理解二叉树的链式存储结构。在Python中,我们可以用类来表示二叉树的节点,每个节点包含一个值、一个指向左子节点...

    已知二叉树的前序和中序遍历,打印后序遍历

    这里我们将重点讨论如何在已知二叉树的前序和中序遍历的情况下,通过非递归算法实现后序遍历。 **前序遍历**:根节点 -&gt; 左子树 -&gt; 右子树 **中序遍历**:左子树 -&gt; 根节点 -&gt; 右子树 **后序遍历**:左子树 -&gt; 右子...

    二叉树的前序中序后序遍历MFC

    在计算机科学中,二叉树遍历是访问二叉树所有节点的一种方法,常用于搜索、排序和数据组织等任务。本主题主要探讨的是在MFC(Microsoft Foundation Classes)环境中如何实现二叉树的前序、中序和后序遍历。 首先,...

    二叉树的前序中序后序遍历

    ### 二叉树的前序、中序与后序遍历 #### 一、引言 在计算机科学中,二叉树是一种常见的数据结构,它由一个根节点以及最多两个子节点(左子节点和右子节点)组成,每个子节点也可以是二叉树。在对二叉树进行操作时...

Global site tag (gtag.js) - Google Analytics