现在的位置: 首页 > 综合 > 正文

Binary Tree

2014年10月03日 ⁄ 综合 ⁄ 共 7202字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

  1. /**
  2.  * filename: BinaryTree.java
  3.  * package:
  4.  * author: Nick Ma
  5.  * email: nick.ma85@yahoo.com
  6.  * date: Nov 1, 2008
  7.  * description: this class implements a binary tree data structure.
  8.  */
  10. public
     
    class
     BinaryTree {
  12.         
    // Data Field
  13.         
  14.         
    /** the root of the binary tree */
  15.         
    protected
     TreeNode root;
  17.         
    /**
  18.          * description: default constructor
  19.          */
  20.         
    public
     BinaryTree() {
  21.                 
    // TODO Auto-generated constructor stub
  22.                 
    this
    .root = 
    null
    ;
  23.         }
  24.         
  25.         
    /**
  26.          * description: protected constructor just to build a new binary tree 
  27.          * with only root node
  28.          */
  29.         
    protected
     BinaryTree(TreeNode node) {
  30.                 
    this
    .root = node;
  31.         }
  33.         
    /**
  34.          * description: the constructor to build a new binary tree
  35.          * @param data - the info stored in the root node
  36.          * @param leftTree - the left subtree of the root
  37.          * @param rightTree - the right subtree of the root
  38.          */
  39.         
    public
     BinaryTree(Object data, BinaryTree leftTree, BinaryTree rightTree) {
  40.                 
    // store the data to the root node
  41.                 root.setData(data);
  42.                 
  43.                 
    // set the left subtree of the root
  44.                 
    if
    (leftTree != 
    null
    ) {
  45.                         root.setLeft(leftTree.root);
  46.                 } 
    else
     {
  47.                         root.setLeft(
    null
    );
  48.                 }
  49.                 
  50.                 
    // set the right subtree of the root
  51.                 
    if
    (rightTree != 
    null
    ) {
  52.                         root.setRight(rightTree.root);
  53.                 } 
    else
     {
  54.                         root.setRight(
    null
    );
  55.                 }
  56.         }
  57.         
  58.         
    /**
  59.          * description: return the left subtree of the root
  60.          * @return - the left subtree
  61.          */
  62.         
    public
     BinaryTree getLeftSubTree() {
  63.                 
    if
    (root != 
    null
     && root.getLeft() != 
    null
    ) {
  64.                         
    return
     
    new
     BinaryTree(root.getLeft());
  65.                 } 
    else
     {
  66.                         
    return
     
    null
    ;
  67.                 }
  68.         }
  69.         
  70.         
    /**
  71.          * description: return the right subtree of the root
  72.          * @return - the right subtree
  73.          */
  74.         
    public
     BinaryTree getRightSubTree() {
  75.                 
    if
    (root != 
    null
     && root.getRight() != 
    null
    ) {
  76.                         
    return
     
    new
     BinaryTree(root.getRight());
  77.                 } 
    else
     {
  78.                         
    return
     
    null
    ;
  79.                 }
  80.         }
  81.         
  82.         
    /**
  83.          * description: determine whether the root has no children or not
  84.          * @return - true if the root has no children
  85.          */
  86.         
    public
     
    boolean
     isLeaf() {
  87.                 
    return
     (root != 
    null
     && root.getLeft() == 
    null
     && root.getRight() == 
    null
    );
  88.         }
  89.         
  90.         
    /**
  91.          * description: perform a pre-order traversal
  92.          * @param node - the local root
  93.          */
  94.         
    public
     
    void
     preOrderTraverse(TreeNode node) {       
  95.                 
    if
    (node == 
    null
    ) {
  96.                         
    // do something when node is null
  97.                 } 
    else
     {
  98.                         
    // do something to root node
  99.                         
    // then traverse to its children
  100.                         preOrderTraverse(node.getLeft());
  101.                         preOrderTraverse(node.getRight());
  102.                 }
  103.         }
  104.         
  105.         
    /**
  106.          * description: perform a in-order traversal
  107.          * @param node - the local root
  108.          */
  109.         
    public
     
    void
     inOrderTraverse(TreeNode node) {
  110.                 
    if
    (node == 
    null
    ) {
  111.                         
    // do something when node is null
  112.                 } 
    else
     {
  113.                         inOrderTraverse(node.getLeft());
  114.                         
    // do something to root node
  115.                         
    // then traverse to its children
  116.                         inOrderTraverse(node.getRight());
  117.                 }
  118.         }
  119.         
  120.         
    /**
  121.          * description: perform a post-order traversal
  122.          * @param node - the local root
  123.          */
  124.         
    public
     
    void
     postOrderTraverse(TreeNode node) {
  125.                 
    if
    (node == 
    null
    ) {
  126.                         
    // do something when node is null
  127.                 } 
    else
     {
  128.                         postOrderTraverse(node.getLeft());
  129.                         postOrderTraverse(node.getRight());
  130.                         
    // do something to root node
  131.                         
    // then traverse to its children
  132.                 }
  133.         }
  134.         
  135.         
    /**
  136.          * description: get the depth of this expression tree
  137.          * @param node - the local root node
  138.          * @return - the depth of the local root
  139.          */
  140.         
    protected
     
    int
     getDepth(TreeNode node) {
  141.                 
    if
    (node == 
    null
    ) {
  142.                         
    return
     
    0
    ;
  143.                 } 
    else
     {
  144.                         
    return
     
    1
     + Math.max(getDepth(node.getLeft()), getDepth(node.getRight()));
  145.                 }
  146.         }
  147. }

  1. /**
  2.  * filename: TreeNode.java
  3.  * package: 
  4.  * author: Nick Ma
  5.  * email: nick.ma85@yahoo.com
  6.  * date: Nov 1, 2008
  7.  * description: this class encapsulates a tree node.
  8.  */
  10. public
     
    class
     TreeNode {
  12.         
    // Data Field
  13.         
  14.         
    /** info stored in this root node */
  15.         
    private
     Object data;
  16.         
  17.         
    /** reference to the left child */
  18.         
    private
     TreeNode left;
  19.         
  20.         
    /** reference to the right child */
  21.         
    private
     TreeNode right;
  23.         
    /**
  24.          * description: default constructor
  25.          */
  26.         
    public
     TreeNode() {
  27.                 
    // TODO Auto-generated constructor stub
  28.                 data = 
    null
    ;
  29.                 left = 
    null
    ;
  30.                 right = 
    null
    ;
  31.         }
  33.         
    /**
  34.          * description: constructor to initialize its data with no left and right children
  35.          * @param data - the data to store in this node
  36.          */
  37.         
    public
     TreeNode(Object data) {
  38.                 
    this
    .data = data;
  39.                 
    this
    .left = 
    null
    ;
  40.                 
    this
    .right = 
    null
    ;
  41.         }
  42.         
  43.         
    /**
  44.          * description: constructor with fields
  45.          * @param data - the data to store in this node
  46.          * @param left - the left child
  47.          * @param right - the right child
  48.          */
  49.         
    public
     TreeNode(Object data, TreeNode left, TreeNode right) {
  50.                 
    this
    .data = data;
  51.                 
    this
    .left = left;
  52.                 
    this
    .right = right;
  53.         }
  55.         
    /* (non-Javadoc)
  56.          * @see java.lang.Object#toString()
  57.          */
  58.         
    @Override
  59.         
    public
     String toString() {
  60.                 
    // TODO Auto-generated method stub
  61.                 
    return
     
    this
    .data.toString();
  62.         }
  64.         
    /**
  65.          * @return the data
  66.          */
  67.         
    public
     Object getData() {
  68.                 
    return
     data;
  69.         }
  71.         
    /**
  72.          * @param data the data to set
  73.          */
  74.         
    public
     
    void
     setData(Object data) {
  75.                 
    this
    .data = data;
  76.         }
  78.         
    /**
  79.          * @return the left
  80.          */
  81.         
    public
     TreeNode getLeft() {
  82.                 
    return
     left;
  83.         }
  85.         
    /**
  86.          * @param left the left to set
  87.          */
  88.         
    public
     
    void
     setLeft(TreeNode left) {
  89.                 
    this
    .left = left;
  90.         }
  92.         
    /**
  93.          * @return the right
  94.          */
  95.         
    public
     TreeNode getRight() {
  96.                 
    return
     right;
  97.         }
  99.         
    /**
  100.          * @param right the right to set
  101.          */
  102.         
    public
     
    void
     setRight(TreeNode right) {
  103.                 
    this
    .right = right;
  104.         }
  105. }

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞