论坛首页 → 入门技术论坛 →

二叉树

浏览 2335 次
锁定老帖子 主题：二叉树
该帖已经被评为新手帖
作者 正文
  • bill.end
  • 等级: 一星会员
  • 性别:
  • 文章: 182
  • 积分: 180
  • 来自: 大连
   发表时间：2007-09-07   最后修改：2009-03-19
java 代码
  1. 这是我写的二叉树和四种遍历方式，请指教。   
  2. p.s. 编号是按照满进行编号(location)。   
  3.   
  4.   
  5.   
  6. public class BinaryTree {   
  7.     private static final int ROOT_LOCATION = 1;   
  8.   
  9.     private BinaryNode root;   
  10.   
  11.     public BinaryTree() {   
  12.     }   
  13.   
  14.     public BinaryNode getRoot() {   
  15.         return root;   
  16.     }   
  17.   
  18.     public void setRoot(BinaryNode root) {   
  19.         this.root = root;   
  20.         this.root.setLocation(ROOT_LOCATION);   
  21.         updateLocation(ROOT_LOCATION, root);   
  22.     }   
  23.   
  24.     public BinaryTree(BinaryNode root) {   
  25.         this();   
  26.         setRoot(root);   
  27.     }   
  28.   
  29.     public BinaryTree(BinaryNode root, int location) {   
  30.         this();   
  31.         this.root = root;   
  32.         this.root.setLocation(location);   
  33.         updateLocation(location, root);   
  34.     }   
  35.   
  36.     public boolean add(BinaryTree aTree, int location) {   
  37.         if (this == aTree) {   
  38.             return false;   
  39.         }   
  40.         BinaryNode aRoot = aTree.getRoot();   
  41.         return add(aRoot, location);   
  42.     }   
  43.   
  44.     public boolean add(BinaryNode node, int location) {   
  45.         if (location == ROOT_LOCATION) {   
  46.             root = getRoot();   
  47.             if (root == null) {   
  48.                 setRoot(node);   
  49.                 return true;   
  50.             }   
  51.             return false;   
  52.         }   
  53.         BinaryNode parent = getParent(location);   
  54.         if (parent == null) {   
  55.             return false;   
  56.         }   
  57.         if (location % 2 == 0) {   
  58.             BinaryNode curNode = parent.getL_Child();   
  59.             if (curNode != null) {   
  60.                 return false;   
  61.             }   
  62.             parent.setL_Child(node);   
  63.         } else {   
  64.             BinaryNode curNode = parent.getR_Child();   
  65.             if (curNode != null) {   
  66.                 return false;   
  67.             }   
  68.             parent.setR_Child(node);   
  69.         }   
  70.         updateLocation(location, node);   
  71.         return true;   
  72.     }   
  73.   
  74.     public BinaryNode getParent(int location) {   
  75.         int parentLoc = location / 2;   
  76.         BinaryNode parent = getNode(parentLoc);   
  77.         return parent;   
  78.     }   
  79.   
  80.     private BinaryNode getNode(int location) {   
  81.         GetNodeHandler handler = new GetNodeHandler(location);   
  82.         TraverseUtil.traverseByPre(this, handler);   
  83.         return handler.getNode();   
  84.     }   
  85.   
  86.     public void delete(int location) {   
  87.         BinaryNode parent = getParent(location);   
  88.         if (parent == null) {   
  89.             return;   
  90.         }   
  91.         if (location % 2 == 0) {   
  92.             parent.setL_Child(null);   
  93.         } else {   
  94.             parent.setR_Child(null);   
  95.         }   
  96.     }   
  97.   
  98.     public boolean update(Object value, int location) {   
  99.         if (value instanceof BinaryNode) {   
  100.             return false;   
  101.         }   
  102.         BinaryNode node = getNode(location);   
  103.         if (node == null) {   
  104.             return false;   
  105.         }   
  106.         node.setData(value);   
  107.         return true;   
  108.     }   
  109.   
  110.     private void updateLocation(int rootLocation, BinaryNode aRoot) {   
  111.         UpdateLocationHandler handler = new UpdateLocationHandler(rootLocation,   
  112.                 aRoot);   
  113.         TraverseUtil.traverseByPre(aRoot, handler);   
  114.     }   
  115.   
  116.     public int getTreeDepth() {   
  117.         MaxLocationHandler handler = new MaxLocationHandler(getRoot());   
  118.         TraverseUtil.traverseByPre(this, handler);   
  119.         int depth = getDepth(handler.getLocation());   
  120.         return depth;   
  121.     }   
  122.   
  123.     public int size() {   
  124.         SizeHandler handler = new SizeHandler(getRoot());   
  125.         TraverseUtil.traverseByPre(this, handler);   
  126.         return handler.getSize();   
  127.     }   
  128.   
  129.     private int getDepth(int max) {   
  130.         ++max;   
  131.         int depth = 1;   
  132.         while (max > 1) {   
  133.             max /= 2;   
  134.             ++depth;   
  135.         }   
  136.         return depth;   
  137.     }   
  138.   
  139.     public Object getData(int loc) {   
  140.         BinaryNode node = getNode(loc);   
  141.         if (node == null) {   
  142.             return null;   
  143.         }   
  144.         return node.getData();   
  145.     }   
  146.   
  147.     private class GetNodeHandler extends AbstractNodeHandler {   
  148.   
  149.         public GetNodeHandler(final int location) {   
  150.             super(location);   
  151.         }   
  152.   
  153.         public boolean handle(BinaryNode node) {   
  154.             if (node == null) {   
  155.                 return false;   
  156.             }   
  157.             if (node.getLocation() == getLocation()) {   
  158.                 setNode(node);   
  159.                 return true;   
  160.             }   
  161.             return false;   
  162.         }   
  163.     }   
  164.   
  165.     private class UpdateLocationHandler extends AbstractNodeHandler {   
  166.   
  167.         public UpdateLocationHandler(int location, BinaryNode root) {   
  168.             super(location);   
  169.             root.setLocation(location);   
  170.         }   
  171.   
  172.         public boolean handle(BinaryNode node) {   
  173.             if (node == null) {   
  174.                 return false;   
  175.             }   
  176.   
  177.             if (node.isExistL_Child()) {   
  178.                 BinaryNode l = node.getL_Child();   
  179.                 l.setLocation(node.getLocation() * 2);   
  180.             }   
  181.   
  182.             if (node.isExistR_Child()) {   
  183.                 BinaryNode r = node.getR_Child();   
  184.                 r.setLocation(node.getLocation() * 2 + 1);   
  185.             }   
  186.             return false;   
  187.         }   
  188.     }   
  189.   
  190.     private class MaxLocationHandler extends AbstractNodeHandler {   
  191.   
  192.         public MaxLocationHandler(BinaryNode root) {   
  193.             super(root.getLocation());   
  194.         }   
  195.   
  196.         public boolean handle(BinaryNode node) {   
  197.             if (node == null) {   
  198.                 return false;   
  199.             }   
  200.             int curLoc = node.getLocation();   
  201.             if (curLoc > getLocation()) {   
  202.                 setLocation(curLoc);   
  203.             }   
  204.             return false;   
  205.         }   
  206.     }   
  207.   
  208.     private class SizeHandler extends AbstractNodeHandler {   
  209.         private int size;   
  210.   
  211.         public int getSize() {   
  212.             return size;   
  213.         }   
  214.   
  215.         public SizeHandler(BinaryNode root) {   
  216.             super(root.getLocation());   
  217.         }   
  218.   
  219.         public boolean handle(BinaryNode node) {   
  220.             if (node == null) {   
  221.                 return false;   
  222.             }   
  223.             size++;   
  224.             return false;   
  225.         }   
  226.     }   
  227. }   
  228.   
  229. public class BinaryNode {   
  230.     public final static int SINGLENODE = 0;   
  231.   
  232.     private Object data;   
  233.   
  234.     private int location;   
  235.   
  236.     private BinaryNode l_Child;   
  237.   
  238.     private BinaryNode r_Child;   
  239.   
  240.     public BinaryNode() {   
  241.         super();   
  242.         this.location = SINGLENODE;   
  243.     }   
  244.   
  245.     public BinaryNode(Object data) {   
  246.         this();   
  247.         this.data = data;   
  248.     }   
  249.   
  250.     public Object getData() {   
  251.         return data;   
  252.     }   
  253.   
  254.     public void setData(Object data) {   
  255.         this.data = data;   
  256.     }   
  257.   
  258.     public BinaryNode getL_Child() {   
  259.         return l_Child;   
  260.     }   
  261.   
  262.     public void setL_Child(BinaryNode child) {   
  263.         l_Child = child;   
  264.     }   
  265.   
  266.     public BinaryNode getR_Child() {   
  267.         return r_Child;   
  268.     }   
  269.   
  270.     public void setR_Child(BinaryNode child) {   
  271.         r_Child = child;   
  272.     }   
  273.   
  274.     public boolean isExistL_Child() {   
  275.         if (getL_Child() == null) {   
  276.             return false;   
  277.         }   
  278.         return true;   
  279.     }   
  280.   
  281.     public boolean isExistR_Child() {   
  282.         if (getR_Child() == null) {   
  283.             return false;   
  284.         }   
  285.         return true;   
  286.     }   
  287.   
  288.     public int getLocation() {   
  289.         return location;   
  290.     }   
  291.   
  292.     public void setLocation(int location) {   
  293.         this.location = location;   
  294.     }   
  295. }   
  296.   
  297. public interface IHandler {   
  298.     /**  
  299.      * return true indicate stopping traversing, otherwise continuing.  
  300.      */  
  301.     boolean handle(BinaryNode node);   
  302. }   
  303.   
  304. public abstract class AbstractNodeHandler implements IHandler {   
  305.     private BinaryNode node;   
  306.   
  307.     private int location;   
  308.   
  309.     public AbstractNodeHandler(final int location) {   
  310.         super();   
  311.         this.location = location;   
  312.     }   
  313.   
  314.     public abstract boolean handle(BinaryNode node);   
  315.   
  316.     public BinaryNode getNode() {   
  317.         return node;   
  318.     }   
  319.   
  320.     public void setNode(BinaryNode node) {   
  321.         this.node = node;   
  322.     }   
  323.   
  324.     public int getLocation() {   
  325.         return location;   
  326.     }   
  327.   
  328.     public void setLocation(int location) {   
  329.         this.location = location;   
  330.     }   
  331.   
  332. }   
  333.   
  334. import java.util.LinkedList;   
  335.   
  336. public class TraverseUtil {   
  337.   
  338.     private TraverseUtil() {   
  339.     }   
  340.   
  341.     public static void traverseByPre(BinaryTree tree, IHandler handler) {   
  342.         BinaryNode root = tree.getRoot();   
  343.         if (root == null) {   
  344.             return;   
  345.         }   
  346.         traverseByPre(root, handler);   
  347.     }   
  348.   
  349.     public static void traverseByPre(BinaryNode node, IHandler handler) {   
  350.         boolean isStop = handler.handle(node);   
  351.         if (isStop) {   
  352.             return;   
  353.         }   
  354.         if (node.isExistL_Child()) {   
  355.             BinaryNode child = node.getL_Child();   
  356.             traverseByPre(child, handler);   
  357.         }   
  358.         if (node.isExistR_Child()) {   
  359.             BinaryNode child = node.getR_Child();   
  360.             traverseByPre(child, handler);   
  361.         }   
  362.     }   
  363.   
  364.     public static void traverseByInOrder(BinaryTree tree, IHandler handler) {   
  365.         BinaryNode root = tree.getRoot();   
  366.         if (root == null) {   
  367.             return;   
  368.         }   
  369.         traverseByInOrder(root, handler);   
  370.     }   
  371.   
  372.     public static void traverseByInOrder(BinaryNode node, IHandler handler) {   
  373.         if (node.isExistL_Child()) {   
  374.             BinaryNode child = node.getL_Child();   
  375.             traverseByInOrder(child, handler);   
  376.         }   
  377.   
  378.         boolean isStop = handler.handle(node);   
  379.         if (isStop) {   
  380.             return;   
  381.         }   
  382.   
  383.         if (node.isExistR_Child()) {   
  384.             BinaryNode child = node.getR_Child();   
  385.             traverseByInOrder(child, handler);   
  386.         }   
  387.     }   
  388.   
  389.     public static void traverseByPost(BinaryTree tree, IHandler handler) {   
  390.         BinaryNode root = tree.getRoot();   
  391.         if (root == null) {   
  392.             return;   
  393.         }   
  394.         traverseByPost(root, handler);   
  395.     }   
  396.   
  397.     public static void traverseByPost(BinaryNode node, IHandler handler) {   
  398.         if (node.isExistL_Child()) {   
  399.             BinaryNode child = node.getL_Child();   
  400.             traverseByPost(child, handler);   
  401.         }   
  402.   
  403.         if (node.isExistR_Child()) {   
  404.             BinaryNode child = node.getR_Child();   
  405.             traverseByPost(child, handler);   
  406.         }   
  407.   
  408.         boolean isStop = handler.handle(node);   
  409.         if (isStop) {   
  410.             return;   
  411.         }   
  412.     }   
  413.   
  414.     public static void traverseByLevel(BinaryTree tree, IHandler handler) {   
  415.         BinaryNode node = tree.getRoot();   
  416.         LinkedList<BinaryNode> level = new LinkedList<BinaryNode>();   
  417.         level.addLast(node);   
  418.         traverseByLevel(handler, level);   
  419.     }   
  420.   
  421.     private static void traverseByLevel(IHandler handler,   
  422.             LinkedList<BinaryNode> level) {   
  423.         if (level.isEmpty()) {   
  424.             return;   
  425.         }   
  426.         BinaryNode node = level.removeFirst();   
  427.         boolean isStop = handler.handle(node);   
  428.         if (isStop) {   
  429.             return;   
  430.         }   
  431.         if (node.isExistL_Child()) {   
  432.             level.addLast(node.getL_Child());   
  433.         }   
  434.         if (node.isExistR_Child()) {   
  435.             level.addLast(node.getR_Child());   
  436.         }   
  437.         traverseByLevel(handler, level);   
  438.     }   
  439. }   
返回顶楼
         
论坛首页 → 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics