树状结构专用结构

UML类图

image.png

生成树状结构

  • Node接口：有输出方法
  • LeafNode实现类：包含内容，可以输出内容
  • BranchNode实现类：包含名字和子节点列表（子节点可以是LeafNode也可以是BranchNode），并且可以添加子节点与输出名字 ```java package com.mashibing.dp.composite;

import java.util.ArrayList; import java.util.List;

abstract class Node { abstract public void p(); }

class LeafNode extends Node { String content; public LeafNode(String content) {this.content = content;}

  1. @Override
  2. public void p() {
  3.     System.out.println(content);
  4. }

}

class BranchNode extends Node { List nodes = new ArrayList<>();

  1. String name;
  2. public BranchNode(String name) {this.name = name;}
  4. @Override
  5. public void p() {
  6.     System.out.println(name);
  7. }
  9. public void add(Node n) {
  10.     nodes.add(n);
  11. }

}

public class Main { public static void main(String[] args) {

  1.     BranchNode root = new BranchNode("root");
  2.     BranchNode chapter1 = new BranchNode("chapter1");
  3.     BranchNode chapter2 = new BranchNode("chapter2");
  4.     Node r1 = new LeafNode("r1");
  5.     Node c11 = new LeafNode("c11");
  6.     Node c12 = new LeafNode("c12");
  7.     BranchNode b21 = new BranchNode("section21");
  8.     Node c211 = new LeafNode("c211");
  9.     Node c212 = new LeafNode("c212");
  11.     root.add(chapter1);
  12.     root.add(chapter2);
  13.     root.add(r1);
  14.     chapter1.add(c11);
  15.     chapter1.add(c12);
  16.     chapter2.add(b21);
  17.     b21.add(c211);
  18.     b21.add(c212);
  20.     tree(root, 0);
  22. }
  24. // 递归显示
  25. static void tree(Node b, int depth) {
  26.     // 按树状结构的目录层次进行输出
  27.     for(int i=0; i<depth; i++) System.out.print("--");
  28.     b.p();
  30.     if(b instanceof BranchNode) {
  31.         // 强转
  32.         for (Node n : ((BranchNode)b).nodes) {
  33.             tree(n, depth + 1);
  34.         }
  35.     }
  36. }

} ```

🤏随想

  1. 递归本身就是一个压栈过程，任何递归都可以自己写成栈式结构，自己压栈弹栈
  2. 有的情况用到递归方便，而栈式结构就不一定方便
  3. 二叉树的栈式遍历是面试时经常考的