二叉樹的遍歷演算法設計

Ⅰ 二叉樹的層次遍歷

設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
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，又不是我們學C。

Ⅲ 二叉樹採用二叉鏈存儲結構，設計一個演算法，按層次順序遍歷二叉樹

應該沒錯~
p = T;//p指向樹根結點
if(p)//樹非空
{
InitQueue(Q);//初始化隊列
EnQueue(Q,p);//p指向結點入列
while(!Empty(Q))//隊列非空
{
DeQueue(Q,p);//出列且p指向出列結點
Visit(p);//訪問結點
//若p指向結點左孩子非空，則左孩子入列
if(p->lchild)
EnQueue(Q,p->lchild);
//若p指向結點右孩子非空，則右孩子入列
if(p->rchild)
EnQueue(Q,p->rchild);
}
}

Ⅳ 演算法設計 遞歸實現遍歷二叉樹，輸出每個節點的度

既然是樹，除葉節點的度是1以外，其他節點的度都是2。
#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;}

Ⅳ 課程設計 二叉樹遍歷演算法集成

#include <iostream>

using namespace std;
int tree[20];//存放二叉樹節點標號
int i=0;//二叉樹節點個數
class node//節點域
{
public:
int num;
node * left;
node * right;
string data;
};
void menu(void)
{
cout<<endl<<" 二叉樹的應用"<<endl;
cout<<"1.創建二叉樹"<<endl;
cout<<"2.成序遍歷二叉樹"<<endl;
cout<<"3.先序遍歷二叉樹"<<endl;
cout<<"4.中序遍歷二叉樹"<<endl;
cout<<"5.後序遍歷二叉樹"<<endl;
cout<<"6.清屏"<<endl;
cout<<"7.結束程序"<<endl;
cout <<"請選擇：" << endl;
}
node* search(node *p,int a)//搜索標號為a的節點
{
node *q=p;
if(q!=NULL)
{
if(q->num==a)
return q;
if(search(q->left,a)!=NULL)
return search(q->left,a);
if(search(q->right,a)!=NULL)
return search(q->right,a);
}
return NULL;
}
node * creatTree(node *p)//建立二叉樹
{

int flag=1;
char c;
int temp;
if(p==NULL)
{
p=new node;
cout<<"請輸入首節點元素："<<endl;//創建首節點
cin>>p->data;
p->num=1;
p->left=NULL;
p->right=NULL;
i++;
tree[0]=1;
}
while(flag)
{

cout<<"1.繼續"<<endl;
cout<<"2.返回"<<endl;
cin>>c;
switch (c)
{
case '1':
cout<<"已有節點標號:"<<endl;
for(int j=0;j<i;j++)
cout<<tree[j]<<" ";
cout<<endl<<"輸入要插入節點標號："<<endl;
cin>>temp;

int a=temp/2;
node *q=search(p,a);//尋找要求父節點
if(q==NULL)
{
cout<<"未找到父節點"<<endl;
break;
}
int j;
for(j=0;j<i;j++)//若輸入已存在節點標號，僅更新樹
if(temp==tree[j])
break;
tree[j]=temp;
if(j==i)
i++;

node *newNode=new node;//新建並添加節點
newNode->left=NULL;
newNode->right=NULL;
newNode->num=temp;
cout<<"輸入信息："<<endl;
cin>>newNode->data;
if(temp==a*2)
q->left=newNode;
else q->right=newNode;

break;
case '2':
flag=0;
break;
default :
cout<<"輸入錯誤。"<<endl;
}
}
return p;
}
void levelOrder(node *p)//成序遍歷
{
int m,n,temp;
for(m=0;m<i;m++)
for(n=m;n<i;n++)
{
if(tree[m]>tree[n])
{
temp=tree[m];
tree[m]=tree[n];
tree[n]=temp;
}
}
for(m=0;m<i;m++)
cout<<search(p,tree[m])->data<<" ";
}
void preOrder(node * p)
{
if(p!=NULL)
{
cout<<p->data<<" ";
preOrder(p->left);
preOrder(p->right);
}
}
void inOrder(node * p)
{
if(p!=NULL)
{
inOrder(p->left);
cout<<p->data<<" ";
inOrder(p->right);
}
}
void postOrder(node * p)
{
if(p!=NULL)
{
postOrder(p->left);
postOrder(p->right);
cout<<p->data<<" ";
}
}

int main()
{
char choose;
node *head=NULL;
while(1)
{
menu();
cin>>choose;
switch (choose)
{
case '1':
head=creatTree(head);
break;
case '2':
if(head==NULL)
cout<<"請先創建二叉樹"<<endl<<endl<<endl;
levelOrder(head);
break;
case '3':
if(head==NULL)
cout<<"請先創建二叉樹"<<endl<<endl<<endl;
preOrder(head);
break;
case '4':
if(head==NULL)
cout<<"請先創建二叉樹"<<endl<<endl<<endl;
inOrder(head);
break;
case '5':
if(head==NULL)
cout<<"請先創建二叉樹"<<endl<<endl<<endl;
postOrder(head);
break;
case '6':
system("cls");
break;
case '7':
return 0;
break;
default :
cout<<"錯誤輸入，請重新選擇。"<<endl<<endl<<endl;
}
}
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);
}
}

Ⅶ 二叉樹的建立及其遍歷演算法的應用問題描述

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef char *BTree;

typedef enum{OVERFLOW=-2,ERROR,FALSE,OK,TRUE} Status;

Status InitBTree(BTree *bt,char *Node)
{
int Length;
int i;
for(Length=0;Node[Length];Length++); /*確定二叉樹的節點數*/
*bt=(BTree)malloc((Length+1)*sizeof(char));/*分配存儲空間，0#單元保存長度*/
if(!(*bt)) exit(OVERFLOW);
(*bt)[0]=Length;
for(i=0;i<Length;i++)
(*bt)[i+1]=Node[i];
return OK;
}

Status Visit(char c)
{
printf("%c",c);
return OK;
}

Status PreorderTraverse(BTree bt,int i)
{ /*遞歸先序遍歷*/
if(i<=bt[0] && bt[i]!='#')
{
Visit(bt[i]);
if(2*i<=bt[0] && bt[2*i]!='#') PreorderTraverse(bt,2*i);
if(2*i+1<=bt[0] && bt[2*i+1]!='#') PreorderTraverse(bt,2*i+1);
}
return OK;
}
void Leaf(BTree bt,int *count)
{ /*計算二叉樹的葉子數*/
if (bt) {
Leaf(bt->lchild,count);
/* 計算左子樹的葉子結點個數 */
if (bt->lchild==NULL && bt->rchild==NULL) (*count)++;
Leaf(bt->rchild,count);
/* 計算右子樹的葉子結點個數 */
}
}

void main()
{
char *node="ABCDEFG##H#IJ#K"; /*二叉樹初始串*/
BTree *bt;
int count=0;
InitBTree(&bt,node); /*用初始串構造一個順序存儲的二叉樹*/
printf("先序遍歷:\n\t");
PreorderTraverse(bt,1);
printf("\n");
Leaf(bt,&count);
printf("\nThe number of leaves is %d\n",count);
getch();
}

我的編輯環境是win-TC ，但願能對你有幫助。

Ⅷ 二叉樹層次遍歷演算法

#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);
}