您的位置:

输出二叉树的层次遍历c语言,遍历二叉树C语言

本文目录一览:

急求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语言实现二叉树层次遍历的递归算法,谢谢!!!

算法思想:层次遍历目前最普遍用的就是队列的那种方式,不是递归,但是用到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 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语言实现层次遍历二叉树?

2叉树没有层次遍历

只有先序遍历,中序遍历,和后续遍历三种

已知二叉树的先序遍历序列和中序遍历序列,求层次遍历 跪求大牛!(C语言)

typedef struct Tree_node{

    int data;

    struct Tree_node *lchild;

    struct Tree_node *rchild;

}NODE,*LINK;

//按层遍历

void LevelShow(LINK root)

{

    LINK queue[N+1],p;

    int front=0,rear=0;  //队列首尾指针

    if(root==NULL)

    {

        printf("树不存在,请创建!\n");

        return;

    }

    if(root)   //若树存在

    {

        queue[rear++]=root;                   //根结点进队

        while(front!=rear)

        {

            p=queue[front++];                 //出队

            printf("%-2d  ",p-data);

            if(p-lchild) queue[rear++]=p-lchild;       //若左子树不为空,则进队

            if(p-rchild) queue[rear++]=p-rchild;       //若右子树不为空,则进队

        }

    }

    putchar('\n');

    return;

}

用队列实现。上面是我以前写的,你改下吧!

C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历。下面有我的建树函数,有注释的。

#include"cstdio"

#include"vector"

#include"cstring"

#include"algorithm"

using namespace std;

const int maxn =30;

struct node{

int data;

node* lchild;

node* rchild;

};

int n;

int in[maxn];

bool vis[maxn]={false};

vectorint lev;

node* create(vectorint lev,int inl,int inr){

if(lev.size()==0) return NULL;

if(inlinr) return NULL;

//printf("00\n");

node* root= new node;

root-data =lev[0];

int k;

for(k=inl;k=inr;k++){

if(lev[0]==in[k])

break;

}

for(int j=inl;j=k-1;j++)

vis[in[j]]=true;

vectorint tempLeft,tempRight;//要函数体内新建

for(int i=1;ilev.size();i++){

if(vis[lev[i]]==true)

tempLeft.push_back(lev[i]);

else

tempRight.push_back(lev[i]);

}

root-lchild =create(tempLeft,inl,k-1);

root-rchild =create(tempRight,k+1,inr);

return root;

}

void preorder(node* root){

if(root==NULL)

return;

printf("%d ",root-data);

preorder(root-lchild);

preorder(root-rchild);

}

int main(){

scanf("%d",n);

int x;

for(int i=0;in;i++){

scanf("%d",x);

lev.push_back(x);

}

for(int j=0;jn;j++)

scanf("%d",in[j]);

node *root =create(lev,0,n-1);

preorder(root);

return 0;

}

输出二叉树的层次遍历c语言,遍历二叉树C语言

2023-01-04
层次遍历构建二叉树c语言,c语言二叉树的创建与遍历

2023-01-06
二叉树的前序遍历c语言,二叉树前序遍历c语言代码

2022-11-25
c语言深度优先二叉树遍历,深度优先遍历类似于二叉树的层次遍历

本文目录一览: 1、急急急!求C语言的数据结构二叉树递归遍历程序! 2、C语言二叉树的遍历。 3、C语言数据结构“遍历二叉树” 4、二叉树的创建和遍历 急急急!求C语言的数据结构二叉树递归遍历程序!

2023-12-08
c语言层序遍历创建二叉树,二叉树的建立与遍历完整代码C语言

2022-11-23
二叉树按层输出c语言,C语言二叉树怎么输入数据

2022-11-24
普通树的深度遍历c语言,树的层次遍历c语言

2023-01-04
后序遍历二叉树的递归算法c语言,实现二叉树的后序遍历的非递归

2023-01-03
java遍历二叉树,java实现二叉树遍历

2023-01-05
二叉树层序遍历递归python(递归层次遍历二叉树)

2022-11-16
java遍历二叉树,java遍历二叉树代码

2023-01-03
c语言二叉排序,c语言创建排序二叉树

2022-12-02
c语言求二叉树最大深度,c语言求二叉树高度

2022-11-25
二叉树的c语言程序求教,c语言创建二叉树代码

2023-01-06
c语言八叉树,二叉树构造c语言实现

2022-11-26
数据结构c语言二叉树的查找,数据结构c语言版二叉树代码

2022-11-22
c语言中前序遍历,先序遍历c语言

2022-12-01
用c语言将二叉树转换为双向链表,二叉树转化为二叉链表

2022-11-29
c语言遍历含义,c语言怎么遍历

2022-11-30
php实现二叉树前中后序遍历,求二叉树前序遍历

2022-11-29