数据结构与算法——二叉树遍历
编程技术  /  houtizong 发布于 3年前   63
首先定义一个二叉树结构如下
class BNode{private String name;private BNode left,right;public String getName() {return name;}public void setName(String name) {this.name = name;}public BNode getLeft() {return left;}public void setLeft(BNode left) {this.left = left;}public BNode getRight() {return right;}public void setRight(BNode right) {this.right = right;}public BNode(String name){this(name,null,null);}public BNode(String name,BNode left,BNode right){this.name = name;this.left = left;this.right = right;}}
插入一堆节点
BNode root;root = new BNode("贾母");root.setLeft(new BNode("贾政"));root.setRight(new BNode("贾赦"));root.getLeft().setLeft(new BNode("贾元春"));root.getLeft().setRight(new BNode("贾宝玉"));root.getRight().setLeft(new BNode("贾琏"));root.getRight().setRight(new BNode("王熙凤"));
下面是简单的前序遍历,中序遍历,后序遍历
protected static void preOrder(BNode n){if(n!=null){System.out.println(n.getName());preOrder(n.getLeft());preOrder(n.getRight());}}protected static void inOrder(BNode n){if(n!=null){inOrder(n.getLeft());System.out.println(n.getName());inOrder(n.getRight());}}protected static void postOrder(BNode n){if(n!=null){postOrder(n.getLeft());postOrder(n.getRight());System.out.println(n.getName());}}
下面是广度优先遍历
protected static void wideOrder(BNode n){LinkedList l = new LinkedList();if(n!= null){l.push(n);}while(!l.isEmpty()){BNode t = (BNode)l.removeLast();System.out.println(t.getName());if(t.getLeft()!=null){l.push(t.getLeft());}if(t.getRight()!=null){l.push(t.getRight());}}}
1,首先将根节点放到队列中;
2,不断循环取队列尾,如果能取到节点,进行步骤3,否则退出循环;
3,依次将该节点的左右子节点插入队列头
下面是非递归先序遍历二叉树的一种实现,用到Stack这种数据结构,注意压栈时先右子节点后左子节点
protected static void preOrder(BNode n){Stack s = new Stack();if(n!=null){s.push(n);}while(!s.isEmpty()){n = (BNode)s.pop();System.out.println(n.getName());if(n.getRight() != null){s.push(n.getRight());}if(n.getLeft()!=null){s.push(n.getLeft());}}}
请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
技术博客集 - 网站简介:
前后端技术:
后端基于Hyperf2.1框架开发,前端使用Bootstrap可视化布局系统生成
网站主要作用:
1.编程技术分享及讨论交流,内置聊天系统;
2.测试交流框架问题,比如:Hyperf、Laravel、TP、beego;
3.本站数据是基于大数据采集等爬虫技术为基础助力分享知识,如有侵权请发邮件到站长邮箱,站长会尽快处理;
4.站长邮箱:[email protected];
文章归档
文章标签
友情链接