c语言版本二叉树基本操作示例(先序 递归 非递归)
请按先序遍历输入二叉树元素（每个结点一个字符，空结点为'='）:
ABD==E==CF==G==
先序递归遍历：
A B D E C F G
中序递归遍历：
D B E A F C G
后序递归遍历：
D E B F G C A
层序递归遍历：
ABCDEFG
先序非递归遍历：
A B D E C F G
中序非递归遍历：
D B E A F C G
后序非递归遍历：
D E B F G C A
深度：
请按任意键继续. . .
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct BTNode
{
ElemType data;
struct BTNode *leftChild;
struct BTNode *rightChild;
}BTNode, *BinTree;
typedef BinTree SElemType;
typedef struct{//栈结构定义
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
BinTree CreateBinTree(BinTree T);
Status Visit(ElemType e);
Status Depth(BinTree T);
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
//定义栈的相关操作
Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(const SqStack *S);
Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
int main()
{
int depth;
BinTree Tree = NULL;
Status(*visit)(ElemType e) = Visit;
printf_s("请按先序遍历输入二叉树元素（每个结点一个字符，空结点为'='）:\n");
Tree = CreateBinTree(Tree);
printf_s("\n先序递归遍历：\n");
PreOrderRecursionTraverse(Tree,visit);
printf_s("\n中序递归遍历：\n");
InOrderRecursionTraverse(Tree,visit);
printf_s("\n后序递归遍历：\n");
PostOrderRecursionTraverse(Tree,visit);
printf_s("\n层序递归遍历：\n");
LevelOrderRecursionTraverse(Tree,visit);
printf_s("\n先序非递归遍历：\n");
PreOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n中序非递归遍历：\n");
InOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n后序非递归遍历：\n");
PostOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n深度：\n");
depth = Depth(Tree);
printf_s("%d\n", depth);
system("pause");
return 0;
}
//创建二叉树
BinTree CreateBinTree(BinTree T)
{
char ch;
scanf_s("%c", &ch);
if (ch == '=')
{
T = NULL;
}
else
{
if (!(T=(BTNode *) malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
T->data = ch; //生成根结点
T->leftChild = CreateBinTree(T->leftChild);
T->rightChild = CreateBinTree(T->rightChild);
}
return T;
}
//访问二叉树
Status Visit(ElemType e)
{
if (e == '\0')
{
return ERROR;
}
else
{
printf_s("%c ", e);
}
return OK;
}
//先序遍历递归算法
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
if (!Visit(T->data))
{
return ERROR;
}
PreOrderRecursionTraverse(T->leftChild, Visit);
PreOrderRecursionTraverse(T->rightChild, Visit);
}
return OK;
}
//中序遍历递归算法
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
InOrderRecursionTraverse(T->leftChild, Visit);
if (!Visit(T->data))
{
return ERROR;
}
InOrderRecursionTraverse(T->rightChild, Visit);
}
return OK;
}
//后序遍历递归算法
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
PostOrderRecursionTraverse(T->leftChild, Visit);
PostOrderRecursionTraverse(T->rightChild, Visit);
if (!Visit(T->data))
{
return ERROR;
}
}
return OK;
}
//层序遍历递归算法
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
BTNode *Q[100];//假设不溢出
int front = -1,rear = -1;
if (T)
{
Q[++rear] = T;
printf_s("%c", T->data);
while (front != rear)
{
BTNode *p;
if (!(p = (BTNode *)malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
p = Q[++front];
if (p->leftChild)
{
Q[++rear] = p->leftChild;
printf("%c",p->leftChild->data);
}
if (p->rightChild)
{
Q[++rear] = p->rightChild;
printf("%c",p->rightChild->data);
}
}
}
}
return OK;
}
Status Depth(BinTree T)
{
int a,b;
if (!T)
{
return ERROR;
}
else
{
a = Depth(T->leftChild) + 1;
b = Depth(T->rightChild) + 1;
return a > b ? a : b;
}
}
//先序遍历非递归算法
Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p;
InitStack(&S);
Push(&S, T);
while (!StackEmpty(S))
{
Pop(&S, &p);
if (!Visit(p->data))
{
return ERROR;
}
if (p->leftChild)
{
Push(&S, p->rightChild);
}
if (p->rightChild)
{
Push(&S, p->leftChild);
}
}
DestroyStack(&S);
return OK;
}
//中序遍历非递归算法
Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p;
InitStack(&S);
Push(&S, T);
while (!StackEmpty(S))
{
while (GetTop(S,&p) && p)
{
Push(&S, p->leftChild);
}
Pop(&S, &p);
if (!StackEmpty(S))
{
Pop(&S, &p);
if (!Visit(p->data))
{
return ERROR;
}
Push(&S, p->rightChild);
}
}
DestroyStack(&S);
return OK;
}
//后序便利非递归算法
Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p, q;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p&&(p->leftChild||p->rightChild))
{
Push(&S,p->rightChild);
Push(&S,p->leftChild);
}
if(!StackEmpty(S)){
Pop(&S,&p);
if (p)
{
if(!Visit(p->data))
{
return ERROR;
}
}
else
{
Pop(&S,&p);
if(!Visit(p->data))
{
return ERROR;
}
}
while (GetTop(S,&q)&&q&&p==q->rightChild)
{
Pop(&S,&p);
if(!Visit(p->data))
{
return ERROR;
}
GetTop(S,&q);
}
}
}
DestroyStack(&S);
return OK;
}
//-----------栈的相关操作--------------//
Status InitStack(SqStack *S){
S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base)
{
exit(0);
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S){
if(!S)
{
exit(0);
}
free(S->base);
return OK;
}
Status ClearStack(SqStack *S){
if(!S)
{
return FALSE;
}
S->top = S->base;
return OK;
}
Status StackEmpty(SqStack S){
if(S.top==S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
int StackLength(SqStack S){
return S.stacksize;
}
Status GetTop(SqStack S,SElemType *e){
if(S.top == S.base)
{
return FALSE;
}
else
{
*e = *(S.top-1);
return OK;
}
}
Status Push(SqStack *S,SElemType e){
if(S->top-S->base>=S->stacksize)
{
S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!S->base)
{
exit(0);
}
S->top = S->base+S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
return OK;
}
Status Pop(SqStack *S,SElemType *e){
if(S->top==S->base)
{
return ERROR;
}
*e = *(--S->top);
return OK;
}
 |
相关推荐
-
C语言二叉排序（搜索）树实例
本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下 /**1.实现了递归 非递归插入(创建)二叉排序(搜索)树: 分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 : 分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNod
-
C语言中计算二叉树的宽度的两种方式
C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo
-
用C语言判断一个二叉树是否为另一个的子结构
1.问题描述: 如何判断一个二叉树是否是另一个的子结构? 比如: 2 / \ 9 8 / \ / 2 3 5 / 6 有个子结构是 9 / \ 2 3 2.分析问题: 有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr
-
举例讲解C语言程序中对二叉树数据结构的各种遍历方式
二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输
-
使用C语言求二叉树结点的最低公共祖先的方法
算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树. 这中条件下可以使用二叉排序树的搜索功能找到最低
-
C语言实现找出二叉树中某个值的所有路径的方法
本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; vector<int> result; struct Node { Node(int i = 0, Node *pl
-
C语言 二叉树的链式存储实例
二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl
-
C语言实现二叉树遍历的迭代算法
本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le
-
C语言二叉树的非递归遍历实例分析
本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus
-
使用C语言构建基本的二叉树数据结构
二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r