本文目錄一覽：
- 1、如何用C語言實現層次遍歷二叉樹?
- 2、用c語言編一個演算法 按層次遍歷二叉樹的結點?
- 3、由中序遍歷和層次遍歷還原二叉樹。C語言實現
- 4、求用C語言實現二叉樹層次遍歷的遞歸演算法，謝謝！！！
- 5、C語言 層次遍歷二叉樹
如何用C語言實現層次遍歷二叉樹?
2叉樹沒有層次遍歷
只有先序遍歷，中序遍歷，和後續遍歷三種
用c語言編一個演算法 按層次遍歷二叉樹的結點?
#includestdio.h
#includemalloc.h
// 定義隊列的最大長度
#define QUEUE_LENGTH 100
//
// 二叉樹與雙向鏈表數據結構定義，
//
typedef struct struNode
{
int data;
struct struNode *lchild; //二叉樹中的左子樹或雙向鏈表中的前向指針
struct struNode*rchild; //二叉樹中的右子樹或雙向鏈表中的後向指針
}BitNode , *BitNodePtr , DuLNode , *DuLNodePtr;
//
// 生成二叉樹
//
BitNodePtr Create_bitree()
{
int m;
BitNodePtr T;
T = NULL;
scanf(“%d”, m);
if(m)
{
T = (BitNodePtr)malloc(sizeof(BitNode));
T-data = m;
T-lchild = Create_bitree();
T-rchild = Create_bitree();
}
return T;
}
//
// 層次遍歷二叉樹
//
void ReadBitTree(BitNodePtr pRoot)
{
BitNodePtr pQueue[QUEUE_LENGTH];
int head = 0 , tail = 1;
pQueue[0] = pRoot;
//結束的條件是head向後移動一個位置後，與tail重合
while (head != tail)
{
printf(“%d ” , pQueue[head]-data);
//左孩子入隊列
if (pQueue[head]-lchild)
{
pQueue[tail] = pQueue[head]-lchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//隊列長度太小，退出
printf(“Queue overflow!”);
return;
}
}
//右孩子入隊列
if (pQueue[head]-rchild)
{
pQueue[tail] = pQueue[head]-rchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//隊列長度太小，退出
printf(“Queue overflow!”);
return;
}
}
//隊首出隊列
head = (head + 1) % QUEUE_LENGTH;
}
printf(“\n”);
return;
}
void main()
{
BitNodePtr Root;
Root = Create_bitree();
ReadBitTree(Root);
return;
}
由中序遍歷和層次遍歷還原二叉樹。C語言實現
經測，該代碼已經修改正確，只需在void BuildTree(char *level,char *inorder,pBiTree T)這裡的最後一個變數T改為引用即可。還有一個地方判斷調用右子樹的地方的判斷條件。
#include stdio.h
#include stdlib.h
#include string.h
typedef struct _BiTree
{
char data;
struct _BiTree *lchild;
struct _BiTree *rchild;
}BiNode, *pBiTree;
void BuildTree(char *level,char *inorder,pBiTree T)
{
int i;
int len=strlen(level); //取得層次遍歷長度
int pos=0;
if(len==0)
return ;
char *p=strchr(inorder,level[0]);
if(p==NULL) //如果為空則拋棄第一個，跳到下一個；
{
char *L=(char*)malloc(sizeof(char)*len); //開闢數組
strncpy(L,level+1,len-1); //捨棄第一個
L[len-1]=0;
BuildTree(L,inorder,T); //調用建樹函數
return ;
}
pos=p-inorder; //得到中序遍歷左子樹字元串長度
T-data=level[0]; //為根節點賦值
T-lchild=NULL;
T-rchild=NULL;
if(pos!=0) //左子樹的遞歸調用
{
T-lchild=(pBiTree)malloc(sizeof(BiNode));
char *left_level=(char*)malloc(sizeof(char)*len);
char *left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1); //捨去層次遍歷第一個
strncpy(left_inor,inorder,pos); //截取左子樹字元串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T-lchild);
}
if(pos strlen(inorder)-1) //右子樹的遞歸調用
{
T-rchild=(pBiTree)malloc(sizeof(BiNode));
char *right_level=(char*)malloc(sizeof(char)*(len));
char *right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T-rchild);
}
}
void priOrder(pBiTree T)
{
if (T != NULL){
printf (“%c”, T-data);
priOrder(T-lchild);
priOrder(T-rchild);
}
}
void postOrder(pBiTree T)
{
if (T != NULL){
postOrder(T-lchild);
postOrder(T-rchild);
printf (“%c”, T-data);
}
}
void freeNode(pBiTree T)
{
if (T != NULL){
freeNode(T-lchild);
freeNode(T-rchild);
free(T);
}
}
int main()
{
pBiTree root;
char level[28], inorder[28];
int n;
scanf (“%d”, n);
//fflush(stdin);
getchar();
while (n –){
scanf (“%s%s”, level, inorder);
root = (pBiTree)malloc(sizeof(BiNode));
BuildTree(level, inorder, root);
priOrder(root);
printf (“\n”);
postOrder(root);
printf (“\n”);
//freeNode(root);
}
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語言 層次遍歷二叉樹
//隊列的操作代碼你自己寫吧？
void
HierarchyBiTree(BiTree
Root){
LinkQueue
*Q;
//
保存當前節點的左右孩子的隊列
InitQueue(Q);
//
初始化隊列
if
(Root
==
NULL)
return
;
//樹為空則返回
BiNode
*p
=
Root;
//
臨時保存樹根Root到指針p中
Visit(p-data);
//
訪問根節點
if
(p-lchild)
EnQueue(Q,
p-lchild);
//
若存在左孩子，左孩子進隊列
if
(p-rchild)
EnQueue(Q,
p-rchild);
//
若存在右孩子，右孩子進隊列
while
(!QueueEmpty(Q))
//
若隊列不空，則層序遍歷
{
DeQueue(Q,
p);
//
出隊列
Visit(p-data);//
訪問當前節點
if
(p-lchild)
EnQueue(Q,
p-lchild);
//
若存在左孩子，左孩子進隊列
if
(p-rchild)
EnQueue(Q,
p-rchild);
//
若存在右孩子，右孩子進隊列
}
DestroyQueue(Q);
//
釋放隊列空間
return
;
}
原創文章，作者：QFPF，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/135089.html
微信掃一掃 
支付寶掃一掃 