本文目录一览:
- 1、C语言二叉树递归算法怎么做?
- 2、c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
- 3、用递归算法先序中序后序遍历二叉树
- 4、求用C语言实现二叉树层次遍历的递归算法,谢谢!!!
- 5、急急急!求C语言的数据结构二叉树递归遍历程序!
C语言二叉树递归算法怎么做?
#include stdio.h
#include string.h
struct treenode{
int value;
treenode* left;
treenode* right;
};
typedef treenode* BiTree;
void visit(treenode* node)
{
printf("%2d ", node-value);
}
// 结点总数
int node(BiTree T)
{
if( !T ){
return 0;
}
return node(T-left) + node(T-right) + 1;
}
// 前序
void preOrder(BiTree T)
{
if( T ){
visit(T);
preOrder(T-left);
preOrder(T-right);
}
}
// 中序
void inOrder(BiTree T)
{
if( T ){
inOrder(T-left);
visit(T);
inOrder(T-right);
}
}
// 后序
void postOrder(BiTree T)
{
if( T ){
postOrder(T-left);
postOrder(T-right);
visit(T);
}
}
// 叶子节点数
int leafnode(BiTree T)
{
if( T ){
if( !T-left !T-right )
return 1;
else
leafnode(T-left) + leafnode(T-right);
}else{
return 0;
}
}
int height(BiTree T)
{
if( T ){
int lh = height(T-left);
int rh = height(T-right);
return (lhrh ? lh:rh) + 1;
}else{
return 0;
}
}
int main()
{
return 0;
}
c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#includemalloc.h // malloc()等
#includestdio.h // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#includestdlib.h // atoi(),exit()
#includemath.h // 数学函数头文件,包括floor(),ceil(),abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree T)
{ // 操作结果:构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T-data=number; // 将值赋给T所指结点
CreateBiTree(T-lchild); // 递归构造左子树
CreateBiTree(T-rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T-lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T-rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T-data); // 先访问根结点
PreOrderTraverse(T-lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T-rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T-lchild,Visit); // 先中序遍历左子树
Visit(T-data); // 再访问根结点
InOrderTraverse(T-rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T-lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T-rchild,Visit); // 再后序遍历右子树
Visit(T-data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
用递归算法先序中序后序遍历二叉树
1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT-Data); //对节点做些访问比如打印
PreOrderTraversal(BT-Left); //访问左儿子
PreOrderTraversal(BT-Right); //访问右儿子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT-Left);
printf("%d\n", BT-Data);
InOrderTraversal(BT-Right);
}
}
3、后序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT-Left);
PostOrderTraversal(BT-Right);
printf("%d\n", BT-Data);
}
}
扩展资料:
注意事项
1、前序遍历
从整棵二叉树的根结点开始,对于任意结点VV,访问结点VV并将结点VV入栈,并判断结点VV的左子结点LL是否为空。若LL不为空,则将LL置为当前结点VV;若LL为空,则取出栈顶结点,并将栈顶结点的右子结点置为当前结点VV。
2、中序遍历
从整棵二叉树的根结点开始,对于任一结点VV,判断其左子结点LL是否为空。若LL不为空,则将VV入栈并将L置为当前结点VV;若LL为空,则取出栈顶结点并访问该栈顶结点,然后将其右子结点置为当前结点VV。重复上述操作,直到当前结点V为空结点且栈为空,遍历结束。
3、后序遍历
将整棵二叉树的根结点入栈,取栈顶结点VV,若VV不存在左子结点和右子结点,或VV存在左子结点或右子结点,但其左子结点和右子结点都被访问过了,则访问结点VV,并将VV从栈中弹出。若非上述两种情况,则将VV的右子结点和左子结点依次入栈。重复上述操作,直到栈为空,遍历结束。
求用C语言实现二叉树层次遍历的递归算法,谢谢!!!
算法思想:层次遍历目前最普遍用的就是队列的那种方式,不是递归,但是用到while循环,既然题目要求用递归,可以用递归实现该while循环功能。算法如下:
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序,创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; iMAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)-ch = ch;
CreateTree(((*r)-left));
CreateTree(((*r)-right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
PrintTree(r-left);
PrintTree(r-right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
急急急!求C语言的数据结构二叉树递归遍历程序!
#include"stdio.h"//二叉树
#include"stdlib.h"
typedef
struct
node
{
char
data;
struct
node
*lchild,*rchild;
}BinTNode;
typedef
BinTNode*
BinTree;
void
GreateBinTree(BinTree
*T)//以先序遍历为依据构造二叉树,T为指向根指针的指针.
{
//空结点以空格代替.
char
ch;
if((ch=getchar())=='
')
*T=NULL;
else
{
*T=(BinTree)malloc(sizeof(BinTNode));
(*T)-data=ch;
GreateBinTree(((*T)-lchild));
GreateBinTree(((*T)-rchild));
}
}
void
Lorder(BinTree
T)//先序遍历二叉树.
{
if(T)
{
printf("%c
",T-data);
Lorder(T-lchild);
Lorder(T-rchild);
}
}
void
Morder(BinTree
T)//中序遍历二叉树.
{
if(T)
{
Morder(T-lchild);
printf("%c
",T-data);
Morder(T-rchild);
}
}
void
Rorder(BinTree
T)//后序遍历二叉树.
{
if(T)
{
Rorder(T-lchild);
Rorder(T-rchild);
printf("%c
",T-data);
}
}