二叉樹的層序遍歷演算法

發布時間: 2022-10-30 10:57:36

① 建立二叉樹，層序、先序遍歷

#include <iostream>
#include "sq_Queue.h"
#define M 1000
using namespace std;
template<class T>
struct Btnode
{T d;
Btnode *lchild;
Btnode *rchild;
};
template<class T>
class Binary_Tree
{private:
Btnode<T> *BT;
public:
Binary_Tree(){BT=NULL;return;}
void creat_Binary_Tree(T);
void pretrav_Binary_Tree();
void level( );
}；
template<class T>
void Binary_Tree<T>::creat_Binary_Tree(T end)
{
Btnode<T> *p;
T x;
cin>>x;
if(x==end)
return; p=new Btnode<T>;
p->d=x;
p->lchild=NULL;
p->rchild=NULL;
BT=p;
creat(p,1,end);
creat(p,2,end);
return;
}
template<class T>
static creat(Btnode<T> *p,int k,T end)
{
Btnode<T> *q;
T x;
cin>>x;
if(x!=end)
{
q=new Btnode<T>; q->d=x;
q->lchild=NULL;
q->rchild=NULL;
if(k==1) p->lchild=q; if(k==2) p->rchild=q; creat(q,1,end); creat(q,2,end); }
return 0;
}
//————————————前序遍歷二叉鏈表——————————————
template<class T>
void Binary_Tree<T>::pretrav_Binary_Tree( )
{
Btnode<T> *p;
p=BT;
pretrav(p); cout<<endl;
return;
}

template<class T>
static pretrav(Btnode<T> *p)
{
if(p!=NULL)
{
cout<<p->d<<" "; pretrav(p->lchild); pretrav(p->rchild); }
return 0;
}
//————————————按層次遍歷二叉鏈表——————————————
template<class T>
void Binary_Tree<T>::level( )
{
Btnode<T> *k;
sq_Queue<Btnode<T>*>q(M);
if(BT!=NULL)
q.ins_sq_Queue(BT);
while(q.flag_sq_Queue( ))
{
k=q.del_sq_Queue( );
cout<<k->d<<endl;
if(k->lchild!=NULL) q.ins_sq_Queue(k->lchild);
if(k->rchild!=NULL) q.ins_sq_Queue(k->rchild);
}
return;
}
int main( )
{
Binary_Tree<int>b; cout<<"輸入各結點值(-1為結束符值):"<<endl;
b.creat_Binary_Tree(-1); cout<<"前序序列:"<<endl;
b.pretrav_Binary_Tree( );
cout<<"按層次輸出二叉鏈表中所有結點值:"<<endl;
b.level( );
再建立一個用戶自定義文件sq_Queue,把下面的考進去
#include <iostream>
using namespace std;
//定義循環隊列類
template<class T> //模板聲明，數據元素虛擬類型為T
class sq_Queue
{private: //數據成員
int mm; //存儲空間容量
int front; //排頭指針
int rear; //隊尾指針
int s; //標志
T *q; //循環隊列存儲空間首地址
public: //成員函數
sq_Queue(int); //構造函數，建立空循環隊列
void prt_sq_Queue(); //輸出排頭與隊尾指針以及隊中元素
int flag_sq_Queue(); //檢測循環隊列的狀態
void ins_sq_Queue(T); //入隊
T del_sq_Queue(); //退隊
};
//建立容量為mm的空循環隊列
template<class T>
sq_Queue<T>::sq_Queue(int m)
{mm=m; //存儲空間容量
q=new T[mm]; //動態申請存儲空間
front=mm;
rear=mm;
s=0;
return;
}
//輸出排頭與隊尾指針以及隊中元素
template<class T>
void sq_Queue<T>::prt_sq_Queue()
{int i;
cout<<"front="<<front<<endl;
cout<<"rear="<<rear<<endl;
if(s==0){cout<<"隊列空！"<<endl;
return;
}
i=front;
do{i=i+1;
if(i==mm+1)i=1;
cout<<q[i-1]<<endl;
}while(i!=rear);
return;
}
//檢測循環隊列的狀態
template<class T>
int sq_Queue<T>::flag_sq_Queue()
{if((s==1)&&(rear==front))return(-1); //存儲空間已滿，返回-1
if(s==0)return(0); //循環隊列為空，返回0
return(1); //正常返回1
}
//入隊
template<class T>
void sq_Queue<T>::ins_sq_Queue(T x)
{if((s==1)&&(rear==front)) //存儲空間已滿，上溢錯誤
{cout<<"Queue_overflow!"<<endl;
return;
}
rear=rear+1; //隊尾指針進一
if(rear==mm+1)rear=1;
q[rear-1]=x; //新元素入隊
s=1; //入隊後隊列非空
return;
}
//退隊
template<class T>
T sq_Queue<T>::del_sq_Queue()
{T y;
if(s==0) //隊列為空，下溢錯誤
{cout<<"Queue_underflow!"<<endl;
return(0);
}
front=front+1; //排頭指針進一
if(front==mm+1)front=1;
y=q[front-1]; //將退隊元素賦值給變數
if(front==rear)s=0;
return(y); //返回退隊元素
}

② 二叉樹層次遍歷怎麼進行

設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
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 ;
這個已經很詳細了！你一定可以看懂的！加油啊！

③ 求c#前中後序遍歷二叉樹的演算法及思想

下面簡單介紹一下幾種演算法和思路：
先序遍歷：
1. 訪問根結點
2. 按先序遍歷左子樹;
3. 按先序遍歷右子樹;
4. 例如：遍歷已知二叉樹結果為：A->B->D->G->H->C->E->F
中序遍歷：
1. 按中序遍歷左子樹;
2. 訪問根結點;
3. 按中序遍歷右子樹;
4. 例如遍歷已知二叉樹的結果：B->G->D->H->A->E->C->F
後序遍歷：
1. 按後序遍歷左子樹;
2. 按後序遍歷右子樹;
3. 訪問根結點;
4. 例如遍歷已知二叉樹的結果：G->H->D->B->E->F->C->A
層次遍歷：
1.從上到下,從左到右遍歷二叉樹的各個結點(實現時需要借輔助容器);
2.例如遍歷已知二叉樹的結果：A->B->C->D->E->F->G->H

附加代碼：
二叉遍歷演算法解決方案
using System;
using System.Collections.Generic;
using System.Text;
namespace structure
{
class Program
{
二叉樹結點數據結構的定義#region 二叉樹結點數據結構的定義
//二叉樹結點數據結構包括數據域,左右結點以及父結點成員;
class nodes<T>
{
T data;
nodes<T> Lnode, Rnode, Pnode;
public T Data
{
set { data = value; }
get { return data; }

}
public nodes<T> LNode
{
set { Lnode = value; }
get { return Lnode; }
}
public nodes<T> RNode
{
set { Rnode = value; }
get { return Rnode; }

}

public nodes<T> PNode
{
set { Pnode = value; }
get { return Pnode; }

}
public nodes()
{ }
public nodes(T data)
{
this.data = data;
}

}
#endregion

#region 先序編歷二叉樹
static void PreOrder<T>(nodes<T> rootNode)
{
if (rootNode != null)
{
Console.WriteLine(rootNode.Data);
PreOrder<T>(rootNode.LNode);
PreOrder<T>(rootNode.RNode);

}
}

#endregion

④ 層序遍歷二叉樹

#include<stdio.h>
#include<stdlib.h>
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜單==============");
printf("\n 1.建立二叉樹方法 1");
printf("\n 2.建立二叉樹方法 2");
printf("\n 3.先序遞歸遍歷二叉樹");
printf("\n 4.中序遞歸遍歷二叉樹");
printf("\n 5.後序遞歸遍歷二叉樹");
printf("\n 6.層次遍歷二叉樹");
printf("\n 7.計算二叉樹的高度");
printf("\n 8.計算二叉樹中葉結點個數");
printf("\n 9.交換二叉樹的左右子樹");
printf("\n 10.列印二叉樹");
printf("\n 0.結束程序運行");
printf("\n===============================");
printf("\n 請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",&k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n請輸入二叉樹各節點的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍歷二叉樹：");
preorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 4:if(t)
{printf("中序遍歷二叉樹：");
inorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 5:if(t)
{printf("後序遍歷二叉樹：");
postorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 6:if(t)
{printf("層次遍歷二叉樹：");
levorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 7:if(t)
{printf("二叉樹的高度為：%d",treedepth(t));
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 8:if(t)
{printf("二叉樹的葉子結點數為：%d\n",leafcount(t));
printf("二叉樹的葉結點數為：");paintleaf(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 9:if(t)
{printf("二叉樹的左右子樹：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 10:if(t)
{printf("逆時針旋轉90度輸出的二叉樹：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再見! 按回車鍵，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n請輸入二叉樹各結點的編號和對應的值(如：1，a):");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n 請繼續輸入二叉樹各結點的編號和對應的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",&e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){

inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level+1;j++)printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);exchange(bt->rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}

⑤ 試完成二叉樹按層次（同一層自左至右）遍歷的演算法。

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"

typedef char ElemType;//定義二叉樹結點值的類型為字元型
const int MaxLength=10;//結點個數不超過10個

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹
// if(T) return;
char ch;
ch=getchar(); //不能用cin來輸入，在cin中不能識別空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍歷
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍歷
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//後序遍歷
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//層序遍歷

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根結點入隊
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不為空，入隊
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不為空，入隊
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}
//非遞歸的先序遍歷演算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非遞歸的中序遍歷演算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{

stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非遞歸的後序遍歷演算法
/*bt是要遍歷樹的根指針，後序遍歷要求在遍歷完左右子樹後，再訪問根。
需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法，結點入棧時，配一個標志tag一同入棧
(1：遍歷左子樹前的現場保護，2：遍歷右子樹前的現場保護)。
首先將bt和tag(為1)入棧，遍歷左子樹；
返回後，修改棧頂tag為2，遍歷右子樹；最後訪問根結點。*/

typedef struct
{
BiTree ptr;
int tag;
}stacknode;

void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍歷左子樹
{
s[top].ptr = p;
s[top].tag = 1; //標記為左子樹
top++;
p=p->lchild;
}

while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<<p->data; //tag為R，表示右子樹訪問完畢，故訪問根結點
}

if (top>0)
{
s[top-1].tag =2; //遍歷右子樹
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec

int BTDepth(BiTree T){//求二叉樹的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){//求二叉樹的葉子數
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){//求二叉樹的結點總數
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

void main(){
BiTree T;
T=NULL;
int select;
//cout<<"請按先序次序輸入各結點的值，以空格表示空樹(輸入時可連續輸入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n請選擇要執行的操作:\n";
cout<<"1.創建二叉樹\n";
cout<<"2.二叉樹的遞歸遍歷演算法（前、中、後）\n";
cout<<"3.二叉樹的層次遍歷演算法\n";
cout<<"4.求二叉樹的深度\n";
cout<<"5.求二叉樹的葉子結點\n";
cout<<"6.求二叉樹的結點總數\n";
cout<<"7.二叉樹的非遞歸遍歷演算法（前、中、後）\n"; //此項可選做
cout<<"0.退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"請按先序次序輸入各結點的值，以空格表示空樹(輸入時可連續輸入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
PreOrderTraverse(T);
cout<<"\n中序遍歷:\n";
InOrderTraverse(T);
cout<<"\n後序遍歷:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n層序遍歷:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉樹的深度為:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n葉子節點數:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"總節點數:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
NRPreOrder(T);
cout<<"\n中序遍歷:\n";
NRInOrder(T);
cout<<"\n後序遍歷:\n";
NRPostOrder(T);
}
break;
default:
cout<<"請確認選擇項:\n";
}//end switch
}//end while

}
參考資料：找來的，你看看吧！

⑥ 二叉樹中的層序遍歷

層次遍歷就是按二叉樹的每一層的順序來遍歷，也就是先訪問根結果，然後訪問第一層，接著訪問第二層...
38題應選:B。大致是先從層次上看出二叉樹的根結點為然後從中序中可以看出DBA為左邊的結點，CE為右邊的結點。然後結合兩個可以發現D、E分別是第二層的左右子結點。而B，A則分別為第三層第四層的右結點，C是第三層上的左結點。

⑦ 以二叉連表做存儲結構，試編寫按層次順序遍歷二叉樹的演算法

//二叉樹，按層次訪問
//引用如下地址的思想，設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
//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);
}
}

⑧ 設完成二叉樹按層次（同一層自左至右）遍歷的演算法。

⑨ 已知二叉樹採用二叉鏈表存儲，編寫演算法實現層次遍歷二叉樹

這是我以前寫的程序，包含了前序中序後序層次便利：若只需層序便利只要把其餘的刪掉就行！
#include"stdafx.h"
#include<stdlib.h>
#include<math.h>
typedef structbitnode{
char data;
struct bitnode *lchild,*rchild;

}bitnode,*bitree;
typedef structqnode{
bitree data;
struct qnode *next;
}qnode;
typedef struct{
qnode * front;
qnode * rear;
}linkqueue;
intinitqueue(linkqueue &q)
{
q.front=q.rear=(qnode*)malloc(sizeof(qnode));
if(!q.front) exit(OVERFLOW);
q.front->next=NULL;
return 1;
}
intenqueue(linkqueue &q,bitree e)
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;

}
intoutqueue(linkqueue & q,bitree &e)
{ qnode *p;
if(q.front==q.rear) return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
return 1;
}
intcreatebitree(bitree &t)
{
char ch;
scanf("%c",&ch);
if(ch=='.')
t=NULL;
else{
if(!(t=(bitnode*)malloc(sizeof(bitnode))))
exit(OVERFLOW);
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
return 1;
}
int visit(char e)
{
printf("%c",e);
return 1;
}
intpreordertraverse(bitree t,int (*visit)(char e))
{

if(t){
if(visit(t->data))
if(preordertraverse(t->lchild,visit))
if(preordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intinordertraverse(bitree t,int (*visit)(char e))
{

if(t){
if(inordertraverse(t->lchild,visit))
if(visit(t->data))
if(inordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intpostordertraverse(bitree t,int (*visit)(char e))
{

if(t){
if(postordertraverse(t->lchild,visit))
if(postordertraverse(t->rchild,visit))
if(visit(t->data))
return 1;
return 0;
}else return 1;
}
voidlevelordertraverse(bitree t)
{
linkqueue q;
bitree e;
initqueue(q);
enqueue(q,t);

while(outqueue(q,e)){
if(e)
{
visit(e->data);
enqueue(q,e->lchild);
enqueue(q,e->rchild);
}
}

}
int main(int argc,char* argv[])
{
bitree t;
printf("輸入字元：");
createbitree(t);
printf("輸出先序遍歷：");
preordertraverse(t, visit);
printf("\n");
printf("輸出中序遍歷：");
inordertraverse(t,visit);
printf("\n");
printf("輸出後序遍歷：");
postordertraverse(t,visit);
printf("\n");
printf("輸出層序遍歷：");
levelordertraverse(t);
printf("\n");
return 0;
}

⑩ 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。

按層次遍歷演算法如下：
#include <iostream>
using namespace std;

typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;

typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;

void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}

if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}

閱讀全文

熱點內容

安卓軟體為什麼經常自啟動發布：2025-05-14 04:38:17 瀏覽：158

譚浩強c語言第三版課後答案發布：2025-05-14 04:37:31 瀏覽：59

san存儲和nas存儲發布：2025-05-14 04:34:44 瀏覽：152

幽靈戰士3什麼配置發布：2025-05-14 04:33:53 瀏覽：114

安卓的虛擬機哪個好用發布：2025-05-14 04:32:34 瀏覽：871

宿遷存儲式化工設備發布：2025-05-14 04:32:33 瀏覽：54

s7200編程s7200 發布：2025-05-14 04:28:32 瀏覽：413

安卓定製版蘋果手機是什麼意思發布：2025-05-14 04:26:27 瀏覽：379

如何搭建php環境虛擬伺服器免費發布：2025-05-14 04:25:37 瀏覽：103

相冊加密怎麼看發布：2025-05-14 04:24:53 瀏覽：573

二叉樹的層序遍歷演算法

與二叉樹的層序遍歷演算法相關的資訊