精华内容
下载资源
问答
  • 层次遍历二叉树算法

    万次阅读 2017-05-11 15:43:30
    在网上看了一些按层次遍历二叉树算法,这里修改了一下通过队列来按层次遍历二叉树算法 ------------------------------------------------------- 网上说的通过队列来实现的解释是: 设置一个队列,然后只要...

    问题:按层次遍历二叉树

    在网上看了一些按层次遍历二叉树的算法,这里修改了一下通过队列来按层次遍历二叉树的算法

    -------------------------------------------------------

    网上说的通过队列来实现的解释是:

    设置一个队列,然后只要队列不为空,将对首元素的左右孩子加入队列(如果左右孩子不为空),然后将队列的首元素出对即可


    流程如下:


    注:图片来源网络


    为了避免大材小用,用单向队列简简单单,清清淡淡。

    #include
    #include
    using namespace std;
    void PrintAtLevel(Tree T) {
    	queue myqueue;
    	myqueue.push(T);
    	while (!myqueue.empty()) {
    		Tree tmp = myqueue.front();
    		if (tmp->lchild != NULL)
    			myqueue.push(tmp->lchild);
    		if (tmp->rchild != NULL)
    			myqueue.push(tmp->rchild);
    		cout << tmp->value << " ";
    		myqueue.pop();
    	}
    }

    展开全文
  • 一、层次遍历  从s

    一、层次遍历

           从上至下,从左至右:每访问一个节点后,将该节点的左子树的节点指针进队,然后再将该节点的右子树的节点指针进队;出队时,正好先出来的是左子树的根节点的指针。

    二、代码实现

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef char EType;
    
    struct BinaryTreeNode//定义节点
    {  
        EType data;  
        struct BinaryTreeNode *LChild;  
        struct BinaryTreeNode *RChild;  
    };  
    typedef BinaryTreeNode BinaryTree; 
    
    typedef struct QType  
    {  
        BinaryTreeNode *ptr;
    }QType; 
    
    typedef struct Queue
    {
    	QType *element;//循环线性队列,0号空间不使用(为了区分队满与队空),注意这不是链式队列
    	int front;
    	int rear;
    	int MaxSize;
    }Queue;
    
    void CreatBiTree(BinaryTreeNode **BT);
    bool IsEmpty(Queue &Q);
    bool IsFull(Queue &Q);
    bool GetFront(Queue &Q,QType &result);
    bool EnQueue(Queue &Q,QType &x);
    bool DeQueue(Queue &Q,QType &result);
    void LevelOrder_LtoR_UtoD(BinaryTreeNode *BT);
    void LevelOrder_RtoL_UtoD(BinaryTreeNode *BT);
    
    int main()
    {
    	BinaryTreeNode *BT = NULL;
    	CreatBiTree(&BT);
    	printf("从上至下,从左至右遍历二叉树输出为:");
    	LevelOrder_LtoR_UtoD(BT);
    	printf("\n");
    	printf("从上至下,从右至左遍历二叉树输出为:");
    	LevelOrder_RtoL_UtoD(BT);
    	printf("\n");
    	return 0;
    }
    
    void CreatQueue(Queue &Q,int MaxQueueSize)
    {
    	Q.MaxSize = MaxQueueSize;
    	Q.element = new QType[Q.MaxSize+1];
    	Q.front = 0;
    	Q.rear = 0;
    }
    
    bool IsEmpty(Queue &Q)
    {
    	if(Q.front == Q.rear)
    		return true;
    	return false;
    }
    
    bool IsFull(Queue &Q)
    {
    	if(Q.front == (Q.rear+1)%(Q.MaxSize+1))
    		return true;
    	return false;
    }
    
    bool GetFront(Queue &Q,QType &result)
    {
    	if(IsEmpty(Q))
    		return false;
    	result = Q.element[(Q.front+1)%(Q.MaxSize+1)];
    	return true;
    }
    
    bool EnQueue(Queue &Q,QType &x)//进队操作:rear向后移
    {
    	if(IsFull(Q))
    		return false;
    	Q.rear = (Q.rear+1)%(Q.MaxSize+1);
    	Q.element[Q.rear] = x;
    	return true;
    }
    
    bool DeQueue(Queue &Q,QType &result)//出队操作:front向后移
    {
    	if(IsEmpty(Q))
    		return false;
    	Q.front = (Q.front+1)%(Q.MaxSize+1);
    	result = Q.element[Q.front];
    	return true;
    }
    
    void CreatBiTree(BinaryTreeNode **BT)//以前序遍历方法输入节点的data,构造一棵二叉树
    {  
        EType tem;  
          
        scanf("%c",&tem);  
        if(' ' == tem)  
        {  
            *BT = NULL;  
        }  
        else  
        {  
            *BT = new BinaryTreeNode;  
            (*BT)->data = tem;  
            CreatBiTree(&(*BT)->LChild);//递归
            CreatBiTree(&(*BT)->RChild);  
        }  
    }  
    
    void LevelOrder_LtoR_UtoD(BinaryTreeNode *BT)
    {
    	Queue Q;
    	QType temp;
    	BinaryTreeNode *p;
    	int MaxQueueSize = 50;
    	CreatQueue(Q,MaxQueueSize);
    	p = BT;
    	temp.ptr = p;
    	EnQueue(Q,temp);//先将根节点进队
    	while(p)//二叉树为空就直接结束
    	{
    		if(!DeQueue(Q,temp))节点出队,当队空时,出队操作返回false,程序return
    			return;//这是这个循环的出口,如果一个二叉树不为空,最终都是在这里跳出循环
    		p = temp.ptr;
    		printf("%c\t",p->data);
    
    		if(p->LChild)//若该节点的左孩子存在,则将其进队
    		{
    			temp.ptr = p->LChild;
    			EnQueue(Q,temp);
    		}
            if(p->RChild)//若该节点的右孩子存在,则将其进队
    		{
    			temp.ptr = p->RChild;
    			EnQueue(Q,temp);
    		}
    	}
    }
    
    void LevelOrder_RtoL_UtoD(BinaryTreeNode *BT)
    {
        Queue Q;
    	QType temp;
    	BinaryTreeNode *p;
    	int MaxQueueSize = 50;
    	CreatQueue(Q,MaxQueueSize);
    	p = BT;
    	temp.ptr = p;
    	EnQueue(Q,temp);
    	while(p)
    	{
    		if(!DeQueue(Q,temp))
    			return;
    		p = temp.ptr;
    		printf("%c\t",p->data);
    
    		if(p->RChild)
    		{
    			temp.ptr = p->RChild;
    			EnQueue(Q,temp);
    		}
    		if(p->LChild)
    		{
    			temp.ptr = p->LChild;
    			EnQueue(Q,temp);
    		}
    	}
    }
    三、效果展示

    建立这样一棵二叉树


    所以按照前序遍历输入应该是:“AB_D_ _CE_ _ _”(其中“_”代表空格)

    那么运行结果为:


    展开全文
  • int Height(BTNode *T)//求二叉树高度 {  int L,R;  if(NULL == T)  return 0;  else  {  L=Height(T->lchild);  R=Height(T->rchild);  return L>R ? L+1 :R+1;  


    int Height(BTNode *T)//求二叉树高度
    {
        int L,R;
        if(NULL == T)  
           return 0;
        else
        {  
            L=Height(T->lchild);
            R=Height(T->rchild);
            return  L>R ? L+1 :R+1;
        }
           
        

    }







    const int MAXSIZE=100;
    BTNode * Q[MAXSIZE];
    int front=0;
    int rear=0;


    void VisitByLayer(BTNode *T)//层次遍历二叉树
    {
         BTNode *s=NULL;
         if(NULL != T)
         {
                 Q[rear] = T;
                 rear=(rear+1)%MAXSIZE;
                 
                 while(front != rear)
                 {
                         s=Q[front];    
                         front=(front+1)%MAXSIZE;
                         printf("%c\t",s->data);
                         if(NULL != s->lchild)
                         {
                                 Q[rear]=s->lchild;
                                 rear=(rear+1)%MAXSIZE;
                         }
                         if(NULL != s->rchild)
                         {  
                                 Q[rear]=s->rchild;
                                 rear=(rear+1)%MAXSIZE;
                         }
                 }
         }
    }
    展开全文
  • 层次遍历二叉树算法 简单易懂 按层次遍历二叉树算法 简单易懂
  • 编写按层次遍历二叉树算法

    千次阅读 2013-06-16 10:43:22
    原题:编写按层次遍历二叉树算法.(分析:显然这种问题适合用队列实现) #include #include #define ElemType char #define NodeNum 5 using namespace std; //二叉树的双链表存储结构 typedef struct BiTNode { ...

    原题:编写按层次遍历二叉树的算法.(分析:显然这种问题适合用队列实现)

    #include<iostream>
    #include<time.h>
    #define ElemType char
    #define NodeNum 5
    using namespace std;
    
    //二叉树的双链表存储结构
    typedef struct BiTNode
    {
    	ElemType data;//数据域
    	struct BiTNode *lchild, *rchild;//左右孩子指针
    }BiTNode, *BiTree;
    
    //队列的数据结构
    typedef struct QNode
    {
    	BiTree base;//初始化的分配存储空间
    	int front;//头指针针,若队列不空,则指向队头元素
    	int rear;//尾指针,若队列不空,则指向队尾元素的下一个元素
    }SqQueue;
    
    int InitQueue(SqQueue &Q)//初始化一个空队列
    {
    	Q.base = (BiTNode *)malloc((NodeNum+3) * sizeof(BiTNode));//队列基址指针
    	if(NULL == Q.base)//若分配内存失败
    	{
    		cout<<"存储分配失败!"<<endl<<endl;
    		return -1;
    	}
    	Q.front = Q.rear = 0;//初始化队头和队尾指针
    	return 1;
    }
    
    int EnQueue(SqQueue &Q, BiTree node)//在队尾插入新的元素作为新的队尾
    {
    	if(Q.front == (Q.rear+1)%(NodeNum+3))
    	{
    		cout<<"队列已满!"<<endl<<endl;
    		return -1;
    	}
    	Q.base[Q.rear] = *node;
    	Q.rear = (Q.rear + 1)%(NodeNum+3);//队尾指针前进一位
    	return 1;
    }
    
    int DeQueue(SqQueue &Q, BiTNode &p)//删除队头元素
    {
    	if(Q.rear == Q.front)
    	{
    		cout<<"队列已空!"<<endl<<endl;
    		return -1;
    	}
    	p = Q.base[Q.front];
    	cout<<"	队头元素 "<<p.data<<" 出队列!"<<endl<<endl;
    	Q.front = (Q.front + 1)%(NodeNum+3);//队头指针前进一位
    	return 1;
    }
    
    int LeverOrderTraverse(BiTree root, int(* visit)(ElemType e))//层次遍历二叉树
    {
    	if(root != NULL)
    	{
    		BiTNode p;
    		SqQueue Q;
    		InitQueue(Q);
    		EnQueue(Q, root);
    		while(Q.front != Q.rear)
    		{
    			DeQueue(Q, p);
    
    			if(p.lchild)//如果左孩子非空, 则左孩子入队
    			{
    				EnQueue(Q, p.lchild);
    			}
    			if(p.rchild)//如果右孩子非空, 则右孩子入队
    			{
    				EnQueue(Q, p.rchild);
    			}
    		}
    		//Destroy(Q);//释放队列所占用的存储空间 (注:该函数还没在此程序中实现)
    	}
    	return 1;
    }
    
    void CreateTree(BiTree &root)
    {//建立二叉树
    	int i=1, flag;
    	BiTree node, pre, p;
    	srand((unsigned)time(NULL));
    	while(i++ <= NodeNum)
    	{
    		node = new BiTNode;
    		node->lchild = NULL;
    		node->rchild = NULL;
    		if(NULL == root)
    		{
    			root = node;
    		}
    		else
    		{
    			p = pre = root;
    			/*现在从树根出发, 走到指定树叶结点, 然后在树叶结点上插入新结点, 输入 0 表示
    			向左走, 输入其它字符表示向右走*/
    			cout<<"(向左向右?)请输入:"<<endl;
    			while(NULL != p)
    			{
    				cin>>flag;
    				pre = p;
    				if(0 == flag)
    				{//向左走
    					p = p->lchild;
    				}
    				else
    				{//向右走
    					p = p->rchild;
    				}
    			}
    			/*将新结点插入为当前叶结点的左孩子(输入 0 )或右孩子(输入其它字符):*/
    			cout<<"选择插入方向:";
    			cin>>flag;
    			if(0 == flag)
    			{
    				pre->lchild = node;
    			}
    			else
    			{
    				pre->rchild = node;
    			}
    		}
    		//输入当前结点数据域值
    		cout<<"输入当前结点数据域值:";
    		cin>>node->data;
    		cout<<endl;
    	}
    }
    
    void main()
    {
    
    	BiTree root = NULL;
    
    	cout<<"建立二叉树:"<<endl<<endl;
    	CreateTree(root);
    
    	cout<<endl<<endl;
    	cout<<"按层次遍历二叉树结果如下:"<<endl<<endl;
    	LeverOrderTraverse(root, NULL);
    
    	cout<<endl<<endl;
    }


     

    展开全文
  • 层次遍历二叉树 1、若树非空,访问根结点。 2、若第1,…i(i≥1)层结点已被访问,且第i+1层结点尚未访问,则从左到右依次访问第i+1层。 层次遍历二叉树,是从根结点开始遍历,按层次次序“自上而下,从左至右”访问...
  • 二叉树的创建及基本操作 PHP储存二叉树,二叉树的创建与二叉树的基本操作 遍历二叉树算法 /** *二叉树的创建及基本操作 * *1.构造方法,初始化建立二叉树 ...*2....*3....*4....*5....*6....*7....*8....*9.层次遍历二叉树 *
  • 层次遍历二叉树

    2011-11-10 22:36:29
    算法设计实际分析了二叉树结构与如何实现层次遍历一颗二叉树,其中包括算法思想与程序代码。分析详尽,推导合理,容易理解。
  • 遍历二叉树分三种:先序遍历二叉树(根左右)、中序遍历二叉树(左根右)、后序遍历二叉树(左右根)。 一、三种遍历方式的操作定义 1、先序遍历二叉树的操作定义: 若二叉树为空,则空操作;否则 1)访问根结点...
  • 层次遍历二叉树分析:层次遍历二叉树也称广度优先遍历,是一层一层的遍历二叉树,可以借助队列,先进先出。 注:与前序遍历的非递归有点像,一个是栈,一个是队列void LevelOreder(Node *pRoot) { cout 层次遍历 ...
  • //中序遍历非递归 @Override public void inOrderByStack() { System.out.println("中序遍历非递归操作"); //创建栈 Deque&lt;Node&gt; stack=new LinkedList&lt;Node&gt;(); ...
  • //非递归按层次遍历二叉树 算法思想:按层次遍历需要一个队列,开始将二叉树的头结点入队,  然后每次从队列中删除一个节点并输出节点信息,接下来把它的非空  左右孩子入队,下一个输出的位它的右面堂兄弟或...
  • // 程序员面试100题(算法)之层次遍历二叉树(用队列实现) #include "stdafx.h" #include #include using namespace std; struct BiTreeNode { BiTreeNode *leftNode; BiTreeNode *rightNode; int value; }; ...
  • 数据结构 树 层次遍历二叉树 C语言版

    千次阅读 多人点赞 2017-08-27 17:18:55
    //层次遍历二叉树并输出结点的算法 #include #include typedef struct NNode { char data; struct NNode *LChild; struct NNode *RChild; } BiTNode,*BiTree; //定义二叉树结点和结点指针 typedef BiTree ...
  • 题目给定一个二叉树,返回其节点值的层次遍历(即从左到右,一层一层遍历) 通过广度优先遍历来实现层次遍历。创建一个Queue来缓存每一层的树节点,在遍历Queue的过程中,每取出一个元素,将该元素的左右子节点按...
  • 题目 从上到下按层打印二叉树,同一层结点从左至右...分层次遍历肯定要使用队列来完成了,没啥好分析的 代码实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function...
  • 编写按层次顺序(同一层自左至右)遍历二叉树算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 (4)测试用例自己设计。
  • 层次遍历二叉树

    千次阅读 2015-07-16 22:29:56
    编写按层次顺序(同一层自左至右)遍历二叉树算法。 #include "stdafx.h" #include #include using namespace std; struct BiNOde { int ele; BiNOde* lnode; BiNOde* rnode; }; vector>aa; BiNOde*p; ...
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    二叉树层序遍历 1、算法思想 用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点...此过程不断进行,当队列为空时,二叉树层次遍历结束...
  • 在此之前,我们已经掌握了使用递归算法实现二叉树先序遍历、中序遍历和后序遍历的流程,这里我们加大一下难度,探讨该如何实现二叉树层次遍历算法. 相信有朋友至此会直接回答"用递归算法解决". 我曾经也有过这种...
  • 遍历二叉树算法

    2015-08-17 19:41:06
    遍历二叉树算法遍历二叉树的方法有以下几种: 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树先序遍历 先序遍历的递归步骤如下:1)访问根节点;2)先序遍历左子树;3)先序遍历右子树。简单的讲就是只要出现...
  • 在之前的博客中,我们已经掌握了使用辅助队列来实现二叉树层次遍历算法. 既然是"遍历",那么二叉树中的每个结点在一次操作中都会被访问到:基于此,我们对遍历时的操作稍加修改,便可统计二叉树中度为1的结点的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,279
精华内容 10,111
关键字:

层次遍历二叉树算法