从上往下遍历二元树(层次遍历二元树)

2024-03-16 17:08
文章标签 遍历 层次 二元

本文主要是介绍从上往下遍历二元树(层次遍历二元树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。

例如输入

      8
    /  \
   6    10
  /\     /\
5  7   9  11

输出8   6   10   5   7   9   11。

分析:这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树,只不过不是我们熟悉的前序、中序或者后序遍历。

我们从树的根结点开始分析。自然先应该打印根结点8,同时为了下次能够打印8的两个子结点,我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6 和10了。按照从左往右的要求,我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中,此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器,此时又比5和7先取出,就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。

既然已经确定数据容器是一个队列,现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个,因为STL已经为我们实现了一个很好的deque(两端都可以进出的队列),我们只需要拿过来用就可以了。

我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解,将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。

import java.util.LinkedList;public class Test_12 {public static void main(String[] args) {BTree bt = new BTree();int[] arr = {8,6,10,5,7,9,11};for(int i = 0;i<arr.length;i++){bt.insert(arr[i]);}PrintFromTopToButton(bt.getRoot());}public static void PrintFromTopToButton(TreeNode2 root){if(root == null){System.out.println("树为空");return;}LinkedList<TreeNode2> queue = new LinkedList<TreeNode2>();queue.add(root);while(queue.size()!=0){TreeNode2 pnode = queue.removeFirst();System.out.println(pnode.getKey());if(pnode.getLeftchild()!=null){queue.add(pnode.getLeftchild());}if(pnode.getRightchild() !=null){queue.add(pnode.getRightchild());}}}}
//以下为二元树的构建//树节点类
class TreeNode2{private int key;private TreeNode2 leftchild;private TreeNode2 rightchild;public int getKey() {return key;}public void setKey(int key) {this.key = key;}public TreeNode2 getLeftchild() {return leftchild;}public void setLeftchild(TreeNode2 leftchild) {this.leftchild = leftchild;}public TreeNode2 getRightchild() {return rightchild;}public void setRightchild(TreeNode2 rightchild) {this.rightchild = rightchild;}public TreeNode2(int key,TreeNode2 leftchild,TreeNode2 rightchild){this.key = key;this.leftchild = leftchild;this.rightchild = rightchild;}}
//二元树类
class BTree{private TreeNode2 root;public TreeNode2 getRoot() {return root;}public void setRoot(TreeNode2 root) {this.root = root;}public void insert(int key){TreeNode2 newnode = new TreeNode2(key,null,null);if(root == null){root = newnode;return;}LinkedList<TreeNode2> queue = new LinkedList<TreeNode2>();queue.add(root);while(queue.size() != 0){TreeNode2 pnode = queue.removeFirst();if(pnode.getLeftchild() == null){pnode.setLeftchild(newnode);return;}if(pnode.getRightchild() == null){pnode.setRightchild(newnode);return;}queue.add(pnode.getLeftchild());queue.add(pnode.getRightchild());}}public void MidOrder(TreeNode2 root){if(root == null){System.out.println("树为空");return;}if(root.getLeftchild()!=null){MidOrder(root.getLeftchild());}System.out.println(root.getKey());if(root.getRightchild()!=null){MidOrder(root.getRightchild());}}
}


 

这篇关于从上往下遍历二元树(层次遍历二元树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816138

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注

MATLAB层次聚类分析法

转自:http://blog.163.com/lxg_1123@126/blog/static/74841406201022774051963/ 层次聚类是基于距离的聚类方法,MATLAB中通过pdist、linkage、dendrogram、cluster等函数来完成。层次聚类的过程可以分这么几步: (1) 确定对象(实际上就是数据集中的每个数据点)之间的相似性,实际上就是定义一个表征

hashmap的存值,各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null,把

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

二叉树的层次遍历(10道)

(写给未来遗忘的自己) 102.二叉数的层序遍历(从上到下) 题目: 代码: class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> node; if (root == nullptr) {

关于双指针遍历

今晚跟一个朋友突然问我,你懂双指针遍历吗?并叫我敲出代码。当时自己愣住了,但是还是写出来了,第一个版本是: #include <iostream> using namespace std; int main(int argc, char** argv, char** arge) { cout<<"输出参数个数:"<<argc<<endl; cout<<"输出字符串数组:"<<endl; f

【ML--13】聚类--层次聚类

一、基本概念 层次聚类不需要指定聚类的数目,首先它是将数据中的每个实例看作一个类,然后将最相似的两个类合并,该过程迭代计算只到剩下一个类为止,类由两个子类构成,每个子类又由更小的两个子类构成。 层次聚类方法对给定的数据集进行层次的分解,直到某种条件满足或者达到最大迭代次数。具体又可分为: 凝聚的层次聚类(AGNES算法):一种自底向上的策略,首先将每个对象作为一个簇,然后合并这些原子簇为越来