二叉樹的層次遍歷演算法
① 實現二叉樹的層次遍歷用c語言！不要c++
很完整的層次遍歷，就不貼代碼了。
http://wenku..com/view/820bfffb04a1b0717fd5dde8.html?st=1
② 二叉樹的層次遍歷是遞歸的演算法嗎
層次遍歷從方法上不具有遞歸的形式，所以一般不用遞歸實現。當然了，非要寫成遞歸肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 補充一下，在main裡面調用的時候就得用LevelOrder(T,1)了。
③ 二叉樹層次遍歷演算法
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}
void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}
④ 二叉樹的層次遍歷以及用層次遍歷演算法顯示所有葉子節點
#include <iostream>
using namespace std;
struct segtree{int a,b;} tree[10001];
void buildtree(int l,int r,int root = 0) //建樹 { tree[root].a=l; tree[root].b=r; if (l==r) return; int mid=(l+r)>>1; root<<=1; buildtree(l,mid,root+1); buildtree(l,mid,root+2);}
void dfs(int level,int root = 0){ for (int i=1;i<level;i++) cout<<' '; cout<<"Lv"<<level<<" : ["<<tree[root].a<<","<<tree[root].b<<"]\n"; if (tree[root].a!=tree[root].b) { root<<=1; dfs(level+1,root+1); dfs(level+1,root+2); }}
struct {int root,level;} st[100001];
void bfs(){ int top=1,first=0; st[first].root=0; st[first].level=1; while (first<top) { for (int i=st[first].level;i>1;i--) cout<<' '; cout<<"Lv"<<st[first].level<<" : ["<<tree[st[first].root].a<<","<<tree[st[first].root].b<<"]\n"; if (tree[st[first].root].a!=tree[st[first].root].b) { st[top].root=st[first].root*2+1; st[top++].level=st[first].level+1; st[top].root=st[first].root*2+2; st[top++].level=st[first].level+1; } first++; }}
int main(){ int t,i; cout<<"以[1,9]線段樹為例，生成一個二叉樹。\n\n"; buildtree(1,9); cout<<"以深度遍歷該樹（深搜）：\n"; dfs(1); cout<<"以深度遍歷該樹（寬搜）：\n"; bfs(); system("pause"); return 0;}
⑤ 以二叉連表做存儲結構，試編寫按層次順序遍歷二叉樹的演算法
//二叉樹，按層次訪問
//引用如下地址的思想，設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;
void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}
}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//構造成滿二叉樹，利於查看結果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;
createBTree(&(*tree)->left);
createBTree(&(*tree)->right);
}
}
void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}
void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}
visitBTree(q);
}
}
⑥ 編寫演算法實現對二叉樹進行按層次遍歷
void Levelorder(BiTree T)
{
int front=0,rear=1;
BiTree q[50];
q[0]=T;
while(front<rear)
{
if(q[front])
{
cout<<q[front]->data<<" ";
q[rear++]=q[front]->lchild;
q[rear++]=q[front]->rchild;
front++;
}
else
front++;
}
cout<<endl;
}
⑦ 二叉樹層次遍歷怎麼進行
設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
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 ;
這個已經很詳細了！你一定可以看懂的！加油啊！
⑧ 求二叉樹的層次遍歷代碼，求高手！！！
#include "stdio.h"typedef int Datatype#define MAXNODE 100
//二叉鏈表的存儲typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild;//左右孩子指針}BiTreeNode,*BiTree;
//三叉鏈表的存儲typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild,*parent;}BiTreeNode,*BiTree;
//演算法3.1：二叉樹的先序遍歷遞歸演算法void PreOrder(BiTree bt){ if(bt!=NULL){ visit(bt->data);//訪問根結點 PreOrder(bt->lchild); PreOrder(bt->rchild); }}
//演算法3.2：二叉樹的中序遍歷遞歸演算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); visit(bt->data); InOrder(bt->rchild); }}
//演算法3.3：二叉樹的後序遍歷遞歸演算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); InOrder(bt->rchild); visit(bt->data); }}
//演算法3.4：二叉樹的層次遍歷演算法void LevelOrder(BiTree bt){ BiTreeNode Queue[MAXNODE]; //定義隊列 int front,rear; if(bt==NULL) return //空二叉樹，遍歷結束 front=-1; rear=0; Queue[rear]=bt; //根結點入隊 while(rear!=front){ //隊列不空，繼續遍歷；否則，遍歷結束 front++; //出隊 visit(Queue[front]->data); //訪問剛出隊的元素 if(Queue[front]->lchild!=NULL){ //如果有左孩子，左孩子入隊 rear++; Queue[rear]=Queue[front]->lchild; } if(Queue[front]->rchild!=NULL){ //如果有右孩子，右孩子入隊 rear++; Queue[rear]=Queue[front]->rchild; } }}
//演算法3.5：中序遍歷的非遞歸演算法void NRInOrder(BiTree bt){ BiTree S[MAXNODE],p=bt;//定義棧 int top=-1; if(bt==NULL) return;//空二叉樹，遍歷結束 while(!(p==NULL&&top==0)){ while(p!=NULL){ if(top<MAXNODE-1) S[top++]=p;//當前指針p入棧 else{printf("棧溢出\n");return;} p=p->lchild;//指針指向p的左孩子結點 } if(top==-1) return //棧空，結束 else{ p=S[--top];//彈出棧頂元素 visit(p->data);//訪問結點的數據域 p=p->rchild;//指向p的右孩子結點 } }}
//演算法3.6：根據先序與中序遍歷結果建立二叉樹void PreInOrd(char preord[],char inord[],int i,int j,int k,int h,BiTree *t)//先序序列從i到j,中序序列從k到h，建立一個二叉樹放到t中{ int m; (*t)=new BTNode; (*t)->data=preord[i];//二叉樹的根 m=k; while (i[m]!=preord[i])m++;//在中序序列中定位樹根 /********遞歸調用建立左子樹******/ if(m==k)(*t)->left=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*t)->left); /********遞歸調用建立左子樹******/ if(m==k)(*t)->right=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*))->right);}BTree * createBT(char preord[],char inord[],int n,BTree root)//n為二叉樹接點的個數，建立的二叉樹放在root中{ if(n<=0) root=NULL; else PreInOrd(preord,inord,1,n,1,n,&root) return root;}
//演算法3.7：統計二叉樹的葉子結點演算法int BitreeLeaf(BTree bt) if(bt==NULL) return 0; if(bt->left==NULL & bt->right==NULL) return 1; return (BitreeLeaf(bt->left)+BirLeaf(bt->right));}
//演算法3.8：求二叉樹深度演算法int BitreeDepth (BiTree bt){ if(bt==NULL) return 0; if(bt->lchild==NULL & bt->rchild==NULL) return1; depthL=BitreeDepth(bt->lchild); depthR=BitreeDepth(bt->rchild); return 1+max(depthL,depthR);}
//演算法3.12：二叉樹的查找演算法BiTree SearchBST(BiTree bt,KeyType key){ if(bt==NULL || key==bt->data.key) return bt; if(key<bt->data.key) return SearchBST(bt->lchild,key); else return SearchBST(bt->rchild,key);}
//演算法3.13：在二叉樹中插入結點int InseartBST(BiTreeNode **bt,Datatype e){ BiTreeNode *qq=new BiTreeNode(),*pp=new BiTreeNode(); BiTreeNode **qq=&qq,*s,**p=&pp; *q=OxO; *p=OxO; if(SearchBST(*bt,e.key,p,q)==0)//待查結點是否在二叉排序樹中 { s=new BiTreeNode(); s->data=e;s->lchild=s->rchild=OxO;//待查結點 if(!(*q)) *bt=s;//二叉樹的根 else if(e.key<(*q)->data.key) (*q)->lchild=s;//作為左兒子插入 else(*q)->rchild=s;//作為右兒子插入 return 1; } else return 0;}
//演算法3.14：在二叉排序樹中刪除結點int DeleteNode(BitreeNode **t,int key){ BiTreeNode *pp=new BiTreeNode(),*ff=new BiTreeNode; BiTreeNode **p=&pp,*s,*q,**f=&ff; *p=OxO;*f=OxO; int flag=0; if(SearchBST(*t,key,f,p)!=0){ flag=1;//查找成功，置刪除標記，待刪除結點為p if(!((*p)->rchild)){//結點無右兒子，結點只有一個分支或為葉子結點 if((*f)->lchild==*p) (*f)->lchild=(*P)->lchild; else (*f)->rchild=(*p)->lchild; } else{//結點有右兒子 if(!((*p)->lchild)){//結點無左兒子，一個分支 if((*f)->lchild==*p) (*f)->lchild=(*P)->rchild; else (*f)->rchild=(*p)->rchild; } else {//結點有左二子，兩個分支 q=*p; s=(*p)->lchild; while(s->rchild){q=s;s=s->rchild;}//在結點p的左分支上沿右指針域往下找，直到右指針域為空時為止 (*p)->data=s->data; if(q!=*p){(q)->rchild=s->lchild;} else(q)->lcild=s->lchild; } } } return flag;}
⑨ 試給出二叉樹的自上而下,自右而左的層次遍歷演算法
根節點入隊
判定隊列是否為空，將隊頂元素e出隊
e的右節點不為空則入隊
e的左節點不為空則入隊
重復2,3，4直到隊列為空