樹的層次遍歷演算法
A. 試完成二叉樹按層次（同一層自左至右）遍歷的演算法。
#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
}
參考資料：找來的，你看看吧！
B. 以二叉連表做存儲結構，試編寫按層次順序遍歷二叉樹的演算法
//二叉樹，按層次訪問
//引用如下地址的思想，設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
//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);
}
}
C. java實現二叉樹層次遍歷
import java.util.ArrayList;
public class TreeNode {
private TreeNode leftNode;
private TreeNode rightNode;
private String nodeName;
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public String getNodeName() {
return nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public static int level=0;
public static void findNodeByLevel(ArrayList<TreeNode> nodes){
if(nodes==null||nodes.size()==0){
return ;
}
level++;
ArrayList<TreeNode> temp = new ArrayList();
for(TreeNode node:nodes){
System.out.println("第"+level+"層:"+node.getNodeName());
if(node.getLeftNode()!=null){
temp.add(node.getLeftNode());
}
if(node.getRightNode()!=null){
temp.add(node.getRightNode());
}
}
nodes.removeAll(nodes);
findNodeByLevel(temp);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode();
root.setNodeName("root");
TreeNode node1 = new TreeNode();
node1.setNodeName("node1");
TreeNode node3 = new TreeNode();
node3.setNodeName("node3");
TreeNode node7 = new TreeNode();
node7.setNodeName("node7");
TreeNode node8 = new TreeNode();
node8.setNodeName("node8");
TreeNode node4 = new TreeNode();
node4.setNodeName("node4");
TreeNode node2 = new TreeNode();
node2.setNodeName("node2");
TreeNode node5 = new TreeNode();
node5.setNodeName("node5");
TreeNode node6 = new TreeNode();
node6.setNodeName("node6");
root.setLeftNode(node1);
node1.setLeftNode(node3);
node3.setLeftNode(node7);
node3.setRightNode(node8);
node1.setRightNode(node4);
root.setRightNode(node2);
node2.setLeftNode(node5);
node2.setRightNode(node6);
ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
nodes.add(root);
findNodeByLevel(nodes);
}
}
D. 什麼是樹的層次遍歷 要求通俗易懂
二叉樹的層次遍歷是指從二叉樹的第一層（根節點）開始，從上至下逐層遍歷，在同一層中，則按照從左到右的順序對節點逐個訪問。在逐層遍歷過程中，按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進行訪問。
其思想為：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。在進行層次遍歷的時候，設置一個隊列結構，遍歷從二叉樹的根節點開始，首先將根節點指針入隊列，然後從隊頭取出一個元素，每取一個元素，執行下面兩個操作：
1、訪問該元素所指向的節點。
2、若該元素所指節點的左右孩子節點非空，則將該元素所指節點的左孩子指針和右孩子指針順序入隊。此過程不斷進行，當隊列為空時，二叉樹的層次遍歷結束。
(4)樹的層次遍歷演算法擴展閱讀
由於遍歷中所使用的數據結構是一個隊列而不是棧，因此寫一個按層遍歷的遞歸程序很困難。如下程序用來對二叉樹進行逐層遍歷，它採用了隊列數據結構。隊列中的元素指向二叉樹節點。當然，也可以採用公式化隊列。
程序中，僅當樹非空時，才進入w h i l e循環。首先訪問根節點，然後把其子節點加到隊列中。當隊列添加操作失敗時，由Add引發NoMem異常，由於沒有捕獲該異常，因此當異常發生時函數將退出。在把t的子節點加入隊列後，要從隊列中刪除t元素。
E. 如何用c語言實現層次遍歷二叉樹
下面是c語言的前序遍歷二叉樹的演算法，在這里假設的節點元素值假設的為字元型，
說明：演算法中用到了結構體，也用到了遞歸的方法，你看看怎麼樣，祝你好運！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定義鏈表結構
{
elemtype
data;
//定義節點值
struct
note
*lchild;
//定義左子節點值
struct
note
*rchild;
//定義右節點值
}btree;
preorder(btree
*root)
//前序遍歷
{
if(roof!=null)
//如果不是空節點
{
printf("%c\n",root->data);
//輸出當前節點
preorder(root->lchild);
//遞歸前序遍歷左子節點
preorder(root->rchild);
//遞歸前序遍歷右子節點
}
return;
//結束
}
F. 二叉樹的層次遍歷以及用層次遍歷演算法顯示所有葉子節點
#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;}
G. 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。
按層次遍歷演算法如下：
#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);
}
}
H. 二叉樹的層次遍歷
設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
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 ;
這個已經很詳細了！你一定可以看懂的！加油啊！