二叉树的遍历算法设计

Ⅰ 二叉树的层次遍历

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
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);
}