<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
// BTree.cpp : Defines the entry point for the console application.
/*
作者：成晓旭
时间：2001年7月2日(9:00:00-14:00:00)
内容：完成二叉树的创建、前序遍历、中序遍历、后序遍历
时间：2001年7月2日(14:00:00-16:00:00)
内容：完成二叉树的叶子节点访问，交换左、右孩子
*/
#include "stdafx.h"
#include "stdlib.h"
#define MAX_NODE 100
#define NODE_COUNT1 8
#define NODE_COUNT2 15
int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
int TreeValue2[NODE_COUNT2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
struct BTree
{
int data;
int order;
BTree *lchild;
BTree *rchild;
};
void Swap(int *p1,int *p2)
{
int t;
t = *p1;
*p1 = *p2;
*p2 = t;
}
/*
function CreateBTree()功能：创建一颗二叉树，并返回一个指向其根的指针
*/
BTree *CreateBTree(int data[][2],int n)
{
BTree *Addr[MAX_NODE];
BTree *p,
*head;
int nodeorder,//节点序号
noderoot, //节点的双亲
i;
if(n>MAX_NODE)
{
printf("参数错误！\n");
return(0);
}
for(i=1;i{
p = (BTree *)malloc(sizeof(BTree));
if(p==NULL)
{
printf("内存溢出错误！\n");
return(0);
}
else
{
p->data = data[i][0];
p->lchild = NULL;
p->rchild = NULL;
nodeorder = data[i][1];
p->order = nodeorder;
Addr[nodeorder] = p;
if(nodeorder>1)
{
noderoot = nodeorder/2;
if(nodeorder %2 == 0)
Addr[noderoot]->lchild = p;
else
Addr[noderoot]->rchild = p;
}
else
head = p;
printf("BTree[%d] = %c\t",p->order,p->data);
}
//free(p);
}
return(head);
}
/*
function FirstOrderAccess0()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess0(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
top = top+1;
stack[top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top];
top = top-1;
p = p->rchild;//继续搜索节点P的右子树
}
}while((top!=0)||(p!=NULL));
}
/*
function FirstOrderAccess1()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点的非空右孩子]进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess1(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);
if(p->rchild!=NULL)
stack[++top] = p->rchild;
p = p->lchild;
}
if(top!=0)
p = stack[top--];
}while((top>0)||(p!=NULL));
}
/*
function MiddleOrderAccess()功能：实现二叉树的中序遍历
二叉树中序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点并访问它，
此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void MiddleOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P进栈
p = p->lchild; //继续搜索其左子树
}
if(top!=0)
{
p = stack[top--];//节点P出栈
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = p->rchild;//继续搜索其左子树
}
}while((top!=0)||(p!=NULL));
}
/*
function LastOrderAccess()功能：实现二叉树的后序遍历
二叉树后序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址第一次进栈；
当找到没有左孩子的节点时，此节点的左子树已访问完毕；
从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再
将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到
没有右孩子的节点为止，如否，则访问该节点；此时，该节点的
左、右子树都已完全遍历，且令指针p = NULL;
如此重复到栈空为止。
*/
void LastOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];//节点的指针栈
int count[MAX_NODE];//节点进栈次数数组
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P首次进栈
count[top] = 0;
p = p->lchild; //继续搜索节点P的左子树
}
p = stack[top--];//节点P出栈
if(count[top+1]==0)
{
stack[++top] = p;//节点P首次进栈
count[top] = 1;
p = p->rchild; //继续搜索节点P的左子树
}
else
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = NULL;
}
}while((top>0));
}
/*
function IsLeafNode()功能：判断给定二叉树的节点是否是叶子节点
*/
int IsLeafNode(BTree *node)
{
if((node->lchild==NULL)&&(node->rchild==NULL))
return(1);
else
return(0);
}
/*
function PrintLeafNode()功能：输出给定二叉树的叶子节点
*/
void PrintLeafNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(IsLeafNode(p))
printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}
/*
function HasTwoChildNode()功能：判断给定二叉树的节点是否存在两个孩子节点
*/
int HasTwoChildNode(BTree *node)
{
if((node->lchild!=NULL)&&(node->rchild!=NULL))
return(1);
else
return(0);
}
/*
function SwapChildNode()功能：交换给定二叉树的所有节点的左、右孩子
*/
void SwapChildNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(HasTwoChildNode(p))
Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}
int main(int argc, char* argv[])
{
BTree * TreeHeader;
printf("二叉树创建数据结果：\n");
TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);
//TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);
if (TreeHeader==0)
{
printf("二叉树创建失败！\n");
return(0);
}
else
{
printf("\n二叉树前序遍历结果：\n");
FirstOrderAccess1(TreeHeader);
printf("\n二叉树中序遍历结果：\n");
MiddleOrderAccess(TreeHeader);
printf("\n二叉树后序遍历结果：\n");
LastOrderAccess(TreeHeader);
//printf("\n二叉树的所有叶子节点：\n");
//PrintLeafNode(TreeHeader);
//SwapChildNode(TreeHeader);
//printf("\n二叉树交换孩子的结果：\n");
//MiddleOrderAccess(TreeHeader);
printf("\n程序运行完毕!\n");
return 0;
}
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935423
相关推荐
本文将深入探讨四种常见的二叉树遍历方法：前序遍历、中序遍历、后序遍历以及层次遍历，并以C++编程语言为例，阐述如何实现这些遍历算法。 1. **前序遍历**（Preorder Traversal） 前序遍历的顺序是根节点 -> 左...
在计算机科学中，二叉树是一种重要的数据结构，它的遍历是解决许多问题的基础。前序、中序和后序遍历是二叉树三种...理解这个算法不仅有助于解决这个问题，还能加深对二叉树遍历的理解，为解决其他类似问题打下基础。
前序遍历是二叉树遍历的一种方式，其顺序为“根节点 -> 左子树 -> 右子树”。这种遍历方式在很多应用场景中都非常有用，例如构建表达式树、查找树中的特定节点等。 **算法实现一：** 1. **定义二叉树结点结构体** ...
二叉树已知后序和中序遍历求前序遍历，C++编写已通过编译
常见的遍历方法包括：前序遍历、中序遍历和后序遍历。 #### 4.1 前序遍历 前序遍历的顺序是先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。实现代码如下： ```c void Preoder...
前序遍历是二叉树遍历的一种方式，其顺序为“根节点 -> 左子树 -> 右子树”。具体而言，在遍历过程中，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。对于非递归的前序遍历，通常会利用栈来辅助实现...
在计算机科学中，二叉树是一种常见的...对于实际的编程实现，你需要根据提供的代码和数据进行调整，确保逻辑正确，并遵循二叉树遍历的规则。在进行这类问题的解决时，理解和熟悉二叉树的性质以及各种遍历方法至关重要。
本节将详细介绍二叉树的前序、中序和后序遍历，以及如何求解二叉树的深度和叶节点数量。 **前序遍历（Preorder Traversal）** 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。在代码实现中，通常采用递归的方式...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
在计算机科学中，二叉树遍历是访问二叉树所有节点的一种方法，常用于搜索、排序和数据组织等任务。本主题主要探讨的是在MFC（Microsoft Foundation Classes）环境中如何实现二叉树的前序、中序和后序遍历。 首先，...
### 二叉树的前序、中序与后序遍历 #### 一、引言 在计算机科学中，二叉树是一种常见的数据结构，它由一个根节点以及最多两个子节点（左子节点和右子节点）组成，每个子节点也可以是二叉树。在对二叉树进行操作时...
java实现 二叉树的遍历 前序遍历用到递归， 中序和后序遍历用到栈， 其实还是有一定难度的
二叉树的遍历，全部用递归实现，很有规律！ 二叉树的遍历，全部用递归实现，很有规律
我们首先定义了二叉树结点的结构体，然后实现了创建二叉树、先序遍历、中序遍历和后序遍历的函数。最后，我们使用switch语句来选择不同的遍历方式。 在实际应用中，二叉树的遍历有很多应用，如数据库查询、图形遍历...
用C++写的，包括二叉树的构建，二叉树的先序遍历、中序遍历和后序遍历非递归算法。
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**： - **递归算法**：首先访问根节点，然后递归地对左子树进行前序遍历，最后对右子树进行前序遍历。伪代码如下： ``` function...
根据给定的文件信息，本文将详细介绍二叉树的基本概念及其前序、中序和后序遍历的实现原理，并对代码进行分析。 ### 一、二叉树基础概念 二叉树是一种特殊的非线性数据结构，它具有以下特点： - 每个节点最多有两...
二叉树遍历是访问二叉树中所有节点的一种方法，通常有三种主要的遍历策略：前序遍历、中序遍历和后序遍历。这些遍历方式在C语言编程中尤为重要，因为它们是理解和实现数据结构算法的基础。 **前序遍历（Preorder ...
首先，我们要了解二叉树的三种基本遍历方式：前序遍历、中序遍历和后序遍历。这些遍历方法主要通过递归和非递归两种方式实现。 1. **前序遍历**（根-左-右）：首先访问根节点，然后递归地遍历左子树，最后遍历右子...
二叉树的遍历主要有三种方式：前序遍历、中序遍历和后序遍历。 1. **前序遍历**： - 访问根节点； - 遍历左子树； - 遍历右子树。 这种遍历方式通常用于复制二叉树或构建一个新的与原二叉树结构相同的二叉树...