輸出二叉樹的層次遍歷c語言,遍歷二叉樹C語言

本文目錄一覽：

• 1、急求C語言寫二叉樹的遍歷
• 2、求用C語言實現二叉樹層次遍歷的遞歸演算法，謝謝！！！
• 3、C語言 數據結構 二叉樹層次遍歷
• 4、如何用C語言實現層次遍歷二叉樹?
• 5、已知二叉樹的先序遍歷序列和中序遍歷序列，求層次遍歷 跪求大牛！（C語言）
• 6、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;

}