按层次遍历二叉树算法
//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//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<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);
}
遍历方法从void cengci(bitree *t) 开始的 用队列方法遍历的
❸ 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
辅助的就是队列了，如果是堆栈就成了深度优先算法了；其实这里辅助结构决定了算法的性质，你可以换成最大堆，最小堆等，就可以达到很多不同的效果
❹ 数据结构二叉树的基本操作~~~~
用递归的方法实现以下算法：
1．以二叉链表表示二叉树，建立一棵二叉树；
2．输出二叉树的前序遍历结果；
3．输出二叉树的猛猛备中序遍历结果；
4．输出二叉树的后序遍历结果；
5．统计二叉树的叶结点个数；
6．统计二叉树的结点个数；
7．计算二叉树的深度。
8．交换二叉树每个结点的左孩子和右孩子；
#include <malloc.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define OK 1
#define NULL 0
#define FALSE 0
typedef struct BiTNode{ //定义链式二叉树结构体
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;
char ch;
int flag=0;
int createBiTree(BiTree &T){
//按先序输入二叉树中知裂结点的值（一个字符），空格表示空树
ch=getchar();
if(ch==' ')T=NULL; //表示空树
else if(ch==10)flag=1; //结点信息输入错误则返回0
else {
T=(BiTNode*)malloc(sizeof(BiTree));
if(!T)exit(1);//空间分配不成功则退出
T->data=ch; //生成根结点
createBiTree(T->lchild); //生成左子树
createBiTree(T->rchild); //生成右子树
}//else
return OK;
}//createBiTree
int PreOrderTraverse(BiTree T){ //先序遍历二叉树的递归算法
if(T){
printf("%c",T->data); //访问根结点
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}//if
return OK;
}
int InOrderTraverse(BiTree T){ //中序
if(T){
InOrderTraverse(T->lchild);
printf("%c",T->data); //访问根结点
InOrderTraverse(T->rchild);
}//if
return OK;
}
int PostOrderTraverse(BiTree T){ // 后序
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data); //访问根结点
}
return OK;
}
int NodeCount(BiTree T){ //
if(T==NULL) return 0;// 如果是空树，则结点个数为0
else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
//否则结点个数为1+左子树的结点个数+右子树的结点个数
}
int LeafNodeCount(BiTree T ){
if(!T)return 0; //如果是空树，则叶子个数为枝毁0;
else if(LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild)==0)return 1;//如果是叶子结点，则叶子结点个数为1
else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
//否则叶结点个数为左子树的叶结点个数+右子树的叶结点个数
}
int Depth(BiTree T){//计算二叉树的深度
int m,n;
if(T==NULL )return 0;//如果是空树，则深度为0
else {
m=Depth(T->lchild);//计算左子树的深度记为m
n=Depth(T->rchild);//计算右左子树的深度记为n
if(m>n) return(m+1);//二叉树的深度为m 与n的较大者加1
else return (n+1);
}
}
void Exchange1(BiTree T)
{
BiTree temp;
if(T)
{
Exchange1(T->lchild);
Exchange1(T->rchild);
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}
}
void main(){
int no,out=1;
char choose;
//*****************************主界面**********************************
while(out){
system("cls");
printf("\n这是实验2的程序，请按照说明使用：\n");
printf("1．以二叉链表表示二叉树，建立一棵二叉树，请输入1");
printf("\n2．输出二叉树的前序遍历结果，请输入2");
printf("\n3．输出二叉树的中序遍历结果，请输入3");
printf("\n4．输出二叉树的后序遍历结果请输入4");
printf("\n5．统计二叉树的结点个数，请输入5");
printf("\n6．统计二叉树的叶结点个数，请输入6");
printf("\n7．计算二叉树的深度，请输入7");
printf("\n8. 交换二叉树的左右孩子，请输入8");
printf("\n9．退出，请输入其他\n");
//********************处理输入的选项************************************
choose=getch();
switch(choose){
case '1':
system("cls");
printf("\n请输入二叉链表各结点信息建立二叉树，空树用空格表示：\n");
if(createBiTree(T)==0||flag==1){ //结点输入错误！
printf("输入错误，请重新输入结点信息!\n");
getch();break;}
else
printf("输入完毕！");//成功建立二叉链表
getch();break;
case '2':
printf("\n先序遍历的结果是：");
PreOrderTraverse(T);
getch();break;
case '3':
printf("\n中序遍历的结果是：");
InOrderTraverse(T);
getch();break;
case '4':
printf("\n后序遍历的结果是：");
PostOrderTraverse(T);
getch();break;
case '5':
no=NodeCount(T);
printf("\n总结点个数为:%d\n",no);
getch();break;
case '6':
printf("\n叶子结点的个数为:%d\n",LeafNodeCount(T));
getch();break;
case '7':
printf("\n二叉树深度为：%d\n",Depth(T));
getch();break;
case '8':
printf("\n交换后的结果为：");
Exchange1(T);
PostOrderTraverse(T);
getch();break;
default :
printf("\n你输入的是:其他\n");
getch();
out=0;
} //end switch
}//end of while
system("cls");
printf("\n\n\t\t欢迎使用，再见！");
}
碉堡了！
❺ 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);
}
}
❻ 设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
按层次遍历算法如下：
#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);
}
}
❼ 试完成二叉树按层次（同一层自左至右）遍历的算法。
#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
}
参考资料：找来的，你看看吧！
❽ 二叉树的层次遍历
设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
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 <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;}