求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：

创新互联建站主要业务有网站营销策划、网站设计、成都网站制作、微信公众号开发、微信小程序、H5技术、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、网络营销推广资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。 

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 btnode//二叉链表类型定义

{char data;

struct btnode *lchild,*rchild;

}bintree,*Bintree;

typedef struct LinkQueueNode//链队列类型定义

{bintree *data;

struct LinkQueueNode *next;

}LKQueNode;

typedef struct LKQueue

{LKQueNode *front,*rear;

}LKQue;

void InitQueue(LKQue *LQ)//初始化队列

{LKQueNode *p;

p=(LKQueNode*)malloc(sizeof(LKQueNode));

LQ-front=p;

LQ-rear=p;

(LQ-front)-next=NULL;

}

int EmptyQueue(LKQue *LQ)//判断队列是否为空

{if(LQ-front==LQ-rear)

return 1;

else return 0;

}

void EnQueue(LKQue *LQ,Bintree x)//入队列

{LKQueNode *p;

p=(LKQueNode*)malloc(sizeof(LKQueNode));

p-data=x;

p-next=NULL;

(LQ-rear)-next=p;

LQ-rear=p;

}

int OutQueue(LKQue *LQ)//出队列

{LKQueNode *s;

if ( EmptyQueue(LQ))

{exit(0);return 0;}

else

{s=(LQ-front)-next;

(LQ-front)-next=s-next;

if(s-next==NULL)

LQ-rear=LQ-front;

free(s);

return 1;}

}

Bintree GetHead(LKQue *LQ)//取队列首元素

{LKQueNode *p;bintree *q;//q-data=-1; 错误在这里没有分配空间就赋值

if(EmptyQueue(LQ))

return q;

else {p=LQ-front-next;

return p-data;

}

} 

Bintree initiate()//建二叉树 

{char ch;Bintree t;

ch=getchar();    

if(ch=='#') t=NULL;

else

{t=(Bintree)malloc(sizeof(bintree));

t-data=ch;

t-lchild=initiate();

t-rchild=initiate();

}

return t;

}

void Visit(Bintree p)//访问节点

{printf("%c",p-data); //输出是char

}

int height(Bintree t)

{int ld,rd;

if(t==NULL) return 0;

else 

{ld=height(t-lchild);

rd=height(t-rchild);

return 1+(ldrd?ld:rd);

}

}

void levelorder(Bintree bt)//层次遍历

{LKQue Q;Bintree p;

InitQueue(Q);

if(bt!=NULL)

{EnQueue(Q,bt);

while(!EmptyQueue(Q))

{p=GetHead(Q);

OutQueue(Q);

Visit(p);

if(p-lchild!=NULL)  EnQueue(Q,p-lchild);

if(p-rchild!=NULL)  EnQueue(Q,p-rchild);

}

}

}

void main()

{Bintree T;

T=initiate();

printf("%d",height(T));

levelorder(T);

}

C语言二叉树的遍历。

二叉树的前中后遍历（递归与非递归）

#includestdio.h

#includestdlib.h

typedef struct NODE

{

char value;

struct NODE *LChild;

struct NODE *RChild;

}BiTNode,*BiTree; //二叉树数据结构

BiTree root;

typedef struct node

{

BiTNode *pointer;

struct node *link;

}LinkStackNode,*LinkStack; //链栈数据结构

LinkStack S;

int count = 0;

//BiTNode * InitTree(BiTree Tree);

BiTNode *CreateTree(BiTree Tree); //创建二叉树

void PreOrder(BiTree Tree); //递归前序遍历二叉树

void MidOrder(BiTree Tree); //递归中序遍历二叉树

void PostOrder(BiTree Tree); //递归后序遍历二叉树

void NPreOrder(BiTree Tree); //非递归前序遍历二叉树

void NMidOrder(BiTree Tree); //非递归中序遍历二叉树

void NPostOrder(BiTree Tree); //非递归后序遍历二叉树

//---------------------------------------------------

LinkStackNode *InitLinkStack(LinkStack top); //初始化链栈

void Push(LinkStack top,BiTNode *p); //进栈操作

BiTNode * Pop(LinkStack top); //出栈操作

//int IsEmpty(LinkStack S); //判断栈是否为空

void main()

{

//BiTree tree;

//root = InitTree(tree);

root = CreateTree(root);

PreOrder(root);

printf("\n");

MidOrder(root);

printf("\n");

PostOrder(root);

printf("\n");

NPreOrder(root);

printf("\n");

NMidOrder(root);

printf("\n");

NPostOrder(root);

printf("\n");

}

/*BiTNode * InitTree(BiTree Tree)

{

//BiTNode *root;

//root = Tree;

Tree = (BiTNode *)malloc(sizeof(BiTNode));

Tree = NULL;

//Tree-LChild = NULL;

//Tree-RChild = NULL;

return Tree;

}*/

//二叉树的扩展先序遍历的创建

BiTNode * CreateTree(BiTree Tree)

{

char ch;

ch = getchar();

if(ch == '.')

Tree = NULL;

else

{

Tree = (BiTNode *)malloc(sizeof(BiTNode));

if(Tree)

{

Tree-value = ch;

Tree-LChild = CreateTree(Tree-LChild);

Tree-RChild = CreateTree(Tree-RChild);

}

}

return Tree;

}

//递归前序遍历二叉树

void PreOrder(BiTree Tree)

{

if(Tree)

{

printf("%c",Tree-value);

PreOrder(Tree-LChild);

PreOrder(Tree-RChild);

}

}

//递归中序遍历二叉树

void MidOrder(BiTree Tree)

{

if(Tree)

{

MidOrder(Tree-LChild);

printf("%c",Tree-value);

MidOrder(Tree-RChild);

}

}

//递归后序遍历二叉树

void PostOrder(BiTree Tree)

{

if(Tree)

{

PostOrder(Tree-LChild);

PostOrder(Tree-RChild);

printf("%c",Tree-value);

}

}

//非递归前序遍历二叉树

void NPreOrder(BiTree Tree)

{

BiTNode *p;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

if(p-RChild)

Push(S,p-RChild);

printf("%c",p-value);

p = p-LChild;

}

else

p = Pop(S);

}

}

//非递归中序遍历二叉树

void NMidOrder(BiTree Tree)

{

//char ch;

BiTNode *p;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

Push(S,p);

p = p-LChild;

}

else

{

p = Pop(S);

printf("%c",p-value);

p = p-RChild;

}

}

}

//非递归后序遍历二叉树

void NPostOrder(BiTree Tree)

{

BiTNode *p,*q = NULL;

S = InitLinkStack(S);

p = Tree;

while(p || count != 0)

{

if(p)

{

Push(S,p);

p = p-LChild;

}

else

{

p = S-link-pointer;

if(p-RChild == NULL || p-RChild == q)

{

p = Pop(S);

printf("%c",p-value);

q = p;

p = NULL;

}

else

{

//p = Pop(S);

p = p-RChild;

}

}

}

}

//初始化链栈

LinkStackNode *InitLinkStack(LinkStack top)

{

top = (LinkStackNode *)malloc(sizeof(LinkStackNode));

return top;

}

//进栈操作

void Push(LinkStack top,BiTNode *p)

{

LinkStackNode *temp;

temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));

if(temp)

{

temp-pointer = p;

temp-link = top-link;

top-link = temp;

count++;

}

}

//出栈操作

BiTNode * Pop(LinkStack top)

{

//char ch;

BiTNode *p;

LinkStackNode *temp;

p = (BiTNode *)malloc(sizeof(BiTNode));

temp = top-link;

if(temp)

{

top-link = temp-link;

p = temp-pointer;

free(temp);

count--;

}

return p;

}

急求C语言写二叉树的遍历

BinaryTree.h:

/********************************************************************

created: 2006/07/04

filename: BinaryTree.h

author: 李创

purpose: 演示二叉树的算法

*********************************************************************/

#ifndef BinaryTree_H

#define BinaryTree_H

＃i nclude stdlib.h

＃i nclude stack

class BinaryTree

{

private:

typedef int Item;

typedef struct TreeNode

{

Item Node;

TreeNode* pRight;

TreeNode* pLeft;

TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)

: Node(node)

, pRight(pright)

, pLeft(pleft)

{

}

}TreeNode, *PTreeNode;

public:

enum TraverseType

{

PREORDER = 0, // 前序

INORDER = 1, // 中序

POSTORDER = 2, // 后序

LEVELORDER = 3 // 层序

};

BinaryTree(Item Array[], int nLength);

~BinaryTree();

PTreeNode GetRoot()

{

return m_pRoot;

}

// 遍历树的对外接口

// 指定遍历类型和是否是非递归遍历,默认是递归遍历

void Traverse(TraverseType traversetype, bool bRec = true);

private:

PTreeNode CreateTreeImpl(Item Array[], int nLength);

void DetroyTreeImpl(PTreeNode pTreenode);

void PreTraverseImpl(PTreeNode pTreenode); // 递归前序遍历树

void InTraverseImpl(PTreeNode pTreenode); // 递归中序遍历树

void PostTraverseImpl(PTreeNode pTreenode); // 递归后序遍历树

void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非递归前序遍历树

void NoRecInTraverseImpl(PTreeNode pTreenode); // 非递归中序遍历树

void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非递归后序遍历树

void LevelTraverseImpl(PTreeNode pTreenode);

PTreeNode m_pRoot; // 根结点

// 采用STL里面的stack作为模拟保存链表结点的stack容器

typedef std::stackBinaryTree::PTreeNode TreeNodeStack;

};

#endif

BinaryTree.cpp:

/********************************************************************

created: 2006/07/04

filename: BinaryTree.cpp

author: 李创

purpose: 演示二叉树的算法

*********************************************************************/

＃i nclude iostream

＃i nclude assert.h

＃i nclude queue

＃i nclude "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)

: m_pRoot(NULL)

{

assert(NULL != Array);

assert(nLength 0);

m_pRoot = CreateTreeImpl(Array, nLength);

}

BinaryTree::~BinaryTree()

{

DetroyTreeImpl(m_pRoot);

}

// 按照中序递归创建树

BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)

{

int mid = nLength / 2;

PTreeNode p = new TreeNode(Array[mid]);

if (nLength 1)

{

p-pLeft = CreateTreeImpl(Array, nLength / 2);

p-pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);

}

return p;

}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)

{

if (NULL != pTreenode-pLeft)

{

DetroyTreeImpl(pTreenode-pLeft);

}

if (NULL != pTreenode-pRight)

{

DetroyTreeImpl(pTreenode-pRight);

}

delete pTreenode;

pTreenode = NULL;

}

// 遍历树的对外接口

// 指定遍历类型和是否是非递归遍历,默认是递归遍历

void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)

{

switch (traversetype)

{

case PREORDER: // 前序

{

if (true == bRec)

{

std::cout "递归前序遍历树\n";

PreTraverseImpl(m_pRoot);

}

else

{

std::cout "非递归前序遍历树\n";

NoRecPreTraverseImpl(m_pRoot);

}

}

break;

case INORDER: // 中序

{

if (true == bRec)

{

std::cout "递归中序遍历树\n";

InTraverseImpl(m_pRoot);

}

else

{

std::cout "非递归中序遍历树\n";

NoRecInTraverseImpl(m_pRoot);

}

}

break;

case POSTORDER: // 后序

{

if (true == bRec)

{

std::cout "递归后序遍历树\n";

PostTraverseImpl(m_pRoot);

}

else

{

std::cout "非递归后序遍历树\n";

NoRecPostTraverseImpl(m_pRoot);

}

}

break;

case LEVELORDER: // 层序

{

std::cout "层序遍历树\n";

LevelTraverseImpl(m_pRoot);

}

}

std::cout std::endl;

}

// 递归前序遍历树

void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

std::cout "Item = " pTreenode-Node std::endl;

PreTraverseImpl(pTreenode-pLeft);

PreTraverseImpl(pTreenode-pRight);

}

// 非递归前序遍历树

void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

TreeNodeStack NodeStack;

PTreeNode pNode;

NodeStack.push(pTreenode);

while (!NodeStack.empty())

{

while (NULL != (pNode = NodeStack.top())) // 向左走到尽头

{

std::cout "Item = " pNode-Node std::endl; // 访问当前结点

NodeStack.push(pNode-pLeft); // 左子树根结点入栈

}

NodeStack.pop(); // 左子树根结点退

栈

if (!NodeStack.empty())

{

pNode = NodeStack.top();

NodeStack.pop(); // 当前结点退栈

NodeStack.push(pNode-pRight); // 当前结点的右子树根结点入栈

}

}

}

// 中序遍历树

// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致

void BinaryTree::InTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

if (NULL != pTreenode-pLeft)

{

InTraverseImpl(pTreenode-pLeft);

}

std::cout "Item = " pTreenode-Node std::endl;

if (NULL != pTreenode-pRight)

{

InTraverseImpl(pTreenode-pRight);

}

}

// 非递归中序遍历树

void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

TreeNodeStack NodeStack;

PTreeNode pNode;

NodeStack.push(pTreenode);

while (!NodeStack.empty())

{

while (NULL != (pNode = NodeStack.top())) // 向左走到尽头

{

NodeStack.push(pNode-pLeft);

}

NodeStack.pop();

if (!NodeStack.empty() NULL != (pNode = NodeStack.top()))

{

std::cout "Item = " pNode-Node std::endl;

NodeStack.pop();

NodeStack.push(pNode-pRight);

}

}

}

// 后序遍历树

void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

if (NULL != pTreenode-pLeft)

{

PostTraverseImpl(pTreenode-pLeft);

}

if (NULL != pTreenode-pRight)

{

PostTraverseImpl(pTreenode-pRight);

}

std::cout "Item = " pTreenode-Node std::endl;

}

// 非递归后序遍历树

void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

TreeNodeStack NodeStack;

PTreeNode pNode1, pNode2;

NodeStack.push(pTreenode);

pNode1 = pTreenode-pLeft;

bool bVisitRoot = false; // 标志位,是否访问过根结点

while (!NodeStack.empty())

{

while (NULL != pNode1) // 向左走到尽头

{

NodeStack.push(pNode1);

pNode1 = pNode1-pLeft;

}

pNode1 = NodeStack.top();

NodeStack.pop();

if (NULL == pNode1-pRight) // 如果没有右子树就是叶子结点

{

std::cout "Item = " pNode1-Node std::endl;

pNode2 = pNode1;

pNode1 = NodeStack.top();

if (pNode2 == pNode1-pRight) // 如果这个叶子结点是右子树

{

std::cout "Item = " pNode1-Node std::endl;

NodeStack.pop();

pNode1 = NULL;

}

else // 否则访问右子树

{

pNode1 = pNode1-pRight;

}

}

else // 访问右子树

{

if (pNode1 == pTreenode true == bVisitRoot) // 如果已经访问过右子树那么就退出

{

std::cout "Item = " pNode1-Node std::endl;

return;

}

else

{

if (pNode1 == pTreenode)

{

bVisitRoot = true;

}

NodeStack.push(pNode1);

pNode1 = pNode1-pRight;

}

}

}

}

// 按照树的层次从左到右访问树的结点

void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)

{

if (NULL == pTreenode)

return;

// 层序遍历用于保存结点的容器是队列

std::queuePTreeNode NodeQueue;

PTreeNode pNode;

NodeQueue.push(pTreenode);

while (!NodeQueue.empty())

{

pNode = NodeQueue.front();

NodeQueue.pop();

std::cout "Item = " pNode-Node std::endl;

if (NULL != pNode-pLeft)

{

NodeQueue.push(pNode-pLeft);

}

if (NULL != pNode-pRight)

{

NodeQueue.push(pNode-pRight);

}

}

}

main.cpp

/********************************************************************

created: 2006/07/04

filename: main.cpp

author: 李创

purpose: 测试二叉树的算法

*********************************************************************/

＃i nclude "BinaryTree.h"

＃i nclude stdio.h

＃i nclude stdlib.h

＃i nclude time.h

＃i nclude iostream

void DisplayArray(int array[], int length)

{

int i;

for (i = 0; i length; i++)

{

printf("array[%d] = %d\n", i, array[i]);

}

}

void CreateNewArray(int array[], int length)

{

for (int i = 0; i length; i++)

{

array[i] = rand() % 256 + i;

}

}

int main()

{

int array[10];

srand(time(NULL));

// 创建数组

CreateNewArray(array, 10);

DisplayArray(array, 10);

BinaryTree *pTree = new BinaryTree(array, 10);

// 测试前序遍历

pTree-Traverse(BinaryTree::PREORDER);

std::cout "root = " pTree-GetRoot()-Node std::endl;

std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;

std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;

pTree-Traverse(BinaryTree::PREORDER, false);

// 测试中序遍历

pTree-Traverse(BinaryTree::INORDER);

std::cout "root = " pTree-GetRoot()-Node std::endl;

std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;

std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;

pTree-Traverse(BinaryTree::INORDER, false);

// 测试后序遍历

pTree-Traverse(BinaryTree::POSTORDER);

std::cout "root = " pTree-GetRoot()-Node std::endl;

std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;

std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;

pTree-Traverse(BinaryTree::POSTORDER, false);

// 测试层序遍历

pTree-Traverse(BinaryTree::LEVELORDER);

system("pause");

delete pTree;

return 0;

}

本文题目：c语言二叉树层遍历函数 c语言二叉树遍历代码
标题来源：http://kswjz.com/article/doicdos.html