数据结构与算法——二叉树遍历
程序员文章站
2022-07-12 17:30:32
...
首先定义一个二叉树结构如下
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()); } } }
上一篇: 心情小记 生活工作