//（递归的）
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
//#include<math.h>
typedef struct node *BiTree;
struct node{
char ch;
BiTree Lchild,Rchild;
};
BiTree root=NULL;
//创建二叉树
BiTree create(BiTree bt)
{
char ch;
scanf("%c",&ch);
if(ch=='$')
bt=NULL;
else{
bt=(BiTree)malloc(sizeof(node));
bt->ch=ch;
bt->Lchild=create(bt->Lchild);
bt->Rchild=create(bt->Rchild);
}
return bt;
}
//先序遍历二叉树
void PreOrder(BiTree bt)
{
if(bt){
printf("%c",bt->ch);
PreOrder(bt->Lchild);
PreOrder(bt->Rchild);
}
}
//中序遍历二叉树
void InOrder(BiTree bt)
{
if(bt){
InOrder(bt->Lchild);
printf("%c",bt->ch);
InOrder(bt->Rchild);
}
}
//后序遍历二叉树
void PostOrder(BiTree bt)
{
if(bt){
PostOrder(bt->Lchild);
PostOrder(bt->Rchild);
printf("%c",bt->ch);
}
}
//求m的n次方
int pow(int m,int n){
int i,dr=1;
for(i=0;i<n;i++){
dr*=m;
}
return dr;
}
//求结点总数
int NodeCount(BiTree bt){
int BiTreeNodeCount=0,btl,btr;
if(bt!=NULL){
BiTreeNodeCount++;
btl=NodeCount(bt->Lchild);
btr=NodeCount(bt->Rchild);
BiTreeNodeCount=btl+btr+1;
}
return BiTreeNodeCount;
}
//求二叉树深度
int TreeDepth(BiTree bt){
int depth=0,dl,dr;
if(bt!=NULL){
dl=TreeDepth(bt->Lchild);
dr=TreeDepth(bt->Rchild);
depth=dl>dr ? dl:dr;
return (depth+1);
}else{
return depth;
}
}
//判断该二叉树是否为满二叉树？
void IsFullBinaryTree(BiTree bt){
if(NodeCount(bt)==(pow(2,TreeDepth(bt))-1)){
printf("此二叉树是满二叉树!\n");
}else{
printf("此二叉树不是满二叉树!\n");
}
}
void main()
{
printf("请输入你要构建的二叉树序列：形如(ABC$$DE$G$$F$$$,其中'$'代表空格符)\n");
root=create(root);
printf("前序遍历二叉树：\n");
PreOrder(root);
printf("\n");
printf("中序遍历二叉树：\n");
InOrder(root);
printf("\n");
printf("后序遍历二叉树：\n");
PostOrder(root);
printf("\n");
IsFullBinaryTree(root);
}
//（非递归的）
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
typedef struct node *BiTree;
struct node{
char ch;
BiTree Lchild,Rchild;
};
BiTree root=NULL;
BiTree stack[MAX_STACK_SIZE];
int top=-1;
//入栈
void push(int *top,BiTree item)
{
if(*top>=MAX_STACK_SIZE-1)
printf("此栈已满！\n");
else
stack[++*top]=item;
}
//出栈
BiTree pop(int *top)
{
if(*top==-1)
return NULL;
return stack[(*top)--];
}
//创建二叉树
BiTree create(BiTree bt)
{
char ch;
scanf("%c",&ch);
if(ch=='$')
bt=NULL;
else{
bt=(BiTree)malloc(sizeof(node));
bt->ch=ch;
bt->Lchild=create(bt->Lchild);
bt->Rchild=create(bt->Rchild);
}
return bt;
}
//先序遍历二叉树
void iter_PreOrder(BiTree bt)
{
for(;;){
for(;bt;bt=bt->Lchild){
printf("%c",bt->ch);
push(&top,bt);
}
bt=pop(&top);
if(!bt) break;
bt=bt->Rchild;
}
}
//中序遍历二叉树
void iter_InOrder(BiTree bt)
{
for(;;){
for(;bt;bt=bt->Lchild)
push(&top,bt);
bt=pop(&top);
if(!bt) break;
printf("%c",bt->ch);
bt=bt->Rchild;
}
}
//后序遍历二叉树
void iter_PostOrder(BiTree bt)
{
int flag[MAX_STACK_SIZE];
for(;;){
for(;bt&&bt->ch;bt=bt->Lchild){
push(&top,bt);
flag[top]=1;
}
bt=pop(&top);
if(!bt) break;
if(flag[top+1]){
push(&top,bt);
flag[top]=0;
}
else{
printf("%c",bt->ch);
bt->ch=NULL;
}
bt=bt->Rchild;
}
}
//求m的n次方
int pow(int m,int n){
int i,dr=1;
for(i=0;i<n;i++){
dr*=m;
}
return dr;
}
//求结点总数
int NodeCount(BiTree bt){
int BiTreeNodeCount=0,btl,btr;
if(bt!=NULL){
BiTreeNodeCount++;
btl=NodeCount(bt->Lchild);
btr=NodeCount(bt->Rchild);
BiTreeNodeCount=btl+btr+1;
}
return BiTreeNodeCount;
}
//求二叉树深度
int TreeDepth(BiTree bt){
int depth=0,dl,dr;
if(bt!=NULL){
dl=TreeDepth(bt->Lchild);
dr=TreeDepth(bt->Rchild);
depth=dl>dr ? dl:dr;
return (depth+1);
}else{
return depth;
}
}
//判断该二叉树是否为满二叉树？
void IsFullBinaryTree(BiTree bt){
if(NodeCount(bt)==(pow(2,TreeDepth(bt))-1)){
printf("此二叉树是满二叉树!\n");
}else{
printf("此二叉树不是满二叉树!\n");
}
}
void main()
{
printf("请输入你要构建的二叉树序列：形如(ABC$$DE$G$$F$$$,其中'$'代表空格符)\n");
root=create(root);
printf("迭代的前序遍历二叉树：\n");
iter_PreOrder(root);
printf("\n");
printf("迭代的中序遍历二叉树：\n");
iter_InOrder(root);
printf("\n");
printf("迭代的后序遍历二叉树：\n");
iter_PostOrder(root);
printf("\n");
IsFullBinaryTree(root);
}
分享到：
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的，包括二叉树的构建，二叉树的先序遍历、中序遍历和后序遍历非递归算法。
下面将分别讨论后序创建、递归后序遍历、非递归堆栈后序遍历以及后序销毁。 1. **后序创建**： 在创建链式二叉树时，后序遍历可以用于构建原始输入序列。例如，如果给定一个后序遍历序列和一个中序遍历序列，我们...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中，二叉树是一种常见的数据结构，它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础，通常有三种主要的遍历方式：...
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
递归遍历是指使用递归函数来遍历二叉树的每个结点。递归遍历的优点是代码简洁易懂，但缺点是可能会导致堆栈溢出。在本文的示例代码中，我们使用了递归函数来实现先序遍历、中序遍历和后序遍历。 先序遍历是指先访问...
二叉树三种遍历非递归算法 二叉树是一种常用的数据结构，它广泛应用于计算机科学和软件工程中。二叉树的遍历是指对二叉树中的每个结点进行访问的过程。常见的二叉树遍历方法有三种：先序遍历、中序遍历和后序遍历。...
在数据结构和算法领域，二叉树遍历是基础且重要的操作，主要用于访问和处理二叉树中的所有节点。本文将详细介绍二叉树的先序、中序和后序遍历，以及如何通过递归和非递归（迭代）的方式来实现这些遍历方法。 **先序...
根据给定的文件信息，我们可以总结出以下关于二叉树创建及遍历的相关知识点： ### 一、二叉树的基本概念 二叉树是一种非线性的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。...
二叉树后序遍历的非递归算法是指在遍历二叉树时，不使用递归函数，而是使用栈来存储结点的方法。该算法的主要思想是使用一个栈来存储结点，通过标志 flag 区分同一个结点的两次出栈。 在该算法中，首先将根指针 ...
根据给定的文件信息，本文将详细介绍二叉树的基本概念及其前序、中序和后序遍历的实现原理，并对代码进行分析。 ### 一、二叉树基础概念 二叉树是一种特殊的非线性数据结构，它具有以下特点： - 每个节点最多有两...
总的来说，理解和掌握二叉树的前序、中序和后序遍历对学习数据结构和算法至关重要，它们不仅加深了对二叉树结构的理解，也为解决实际问题提供了有效的手段。在编写代码时，应结合具体情况考虑性能和资源管理，以实现...
根据提供的标题、描述以及部分代码内容，我们可以总结出关于二叉树非递归遍历算法的相关知识点。 ### 一、二叉树非递归遍历算法概述 在数据结构的学习中，二叉树是非常重要的一个概念，而遍历是访问二叉树节点的一...
在计算机科学领域，二叉树是一种...总之，二叉树的遍历是数据结构与算法的基础，掌握递归和非递归的实现方法对提升编程技能和解决复杂问题的能力大有裨益。在实践中不断优化和改进代码，可以更好地理解和运用这些概念。
**前序遍历**是二叉树遍历的一种，其顺序为：根节点 -> 左子树 -> 右子树。在非递归实现中，我们可以使用栈来辅助完成。首先将根节点压入栈中，然后进入一个循环。在循环中，如果栈不为空，就弹出栈顶元素并访问，...
遍历二叉树是指按照特定的顺序访问树中的每一个节点，常见的遍历方式有三种：先序遍历、中序遍历和后序遍历。在递归方法之外，我们还可以使用非递归方法，如栈，来实现这些遍历。本程序正是专注于非递归实现这三种...
非递归中序遍历二叉树（算法2）： 层次遍历二叉树： 递归计算单分支结点： 递归计算双分支结点： 递归计算叶子数： 二叉数的深度： 交换二叉树的左右子树： 二叉树已左右交换。 递归先序遍历二叉树： 递归...
二叉树是计算机科学中一种重要的数据结构，它由节点（或称为顶点）组成，每个节点最多有两个子节点，通常分别称为左子节点和右子节点。...通过练习和实践，你可以更好地理解和掌握二叉树遍历的技巧。
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**： - **递归算法**：首先访问根节点，然后递归地对左子树进行前序遍历，最后对右子树进行前序遍历。伪代码如下： ``` function...