您的位置: 首页  >  文章  >  数据结构 --- Java之二叉树的实现

数据结构 --- Java之二叉树的实现

分类: 文章 • 2024-07-16 21:59:04

二叉树（Binary Tree）：二叉树是一棵树，其中每个结点都不能有多于两个的子结点；


特点：

     （1） 每个结点最多有两棵子树，没有子树或者只有一棵子树也是可以的；

      （2）左子树和右子树是有顺序的，次序不能任意颠倒；

      （3）即使树中只有一棵子树，也要区分它是左子树还是右子树；


特殊的二叉树：

      （1）斜树：顾名思义，斜树一定是要斜的；所有的结点都只有左子树的二叉树叫左斜树，所有的结点都只有右子树的二叉树叫右斜树；其实，线性表就可以理解为树的一种特殊的表现形式；

       （2）满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树;如图：

数据结构 --- Java之二叉树的实现

         （3）完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，那么这棵二叉树称为完全二叉树；或者这样理解：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是右边缺少连续若干个结点，则称此树为完全二叉树；

数据结构 --- Java之二叉树的实现

所以我们可以这样判断完全二叉树：那就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是；


二叉树的实现：同样，二叉树也可以通过顺序存储和链式存储来实现；

          二叉树的顺序存储就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如父结点与子结点的逻辑关系，子结点 与子结点之间的关系；但顺序存储的实用性不强；

          所以一般采用链式存储；


二叉树的遍历：是指从根结点出发，按照某种次序，依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次；

 二叉树的遍历方式有好多种，如果我们限制了从左到右的习惯方式，那么主要就有以下几种：

         （1）前序遍历：先访问子结点，然后前序遍历左子树，再前序遍历右子树；如下图，遍历顺序是：ABDGHCEIF

数据结构 --- Java之二叉树的实现

         （2）中序遍历：从根结点开始（但并不是先访问根结点），中序遍历根结点的左子树，然后方式根结点，最后中序遍历右树，如图，遍历的顺序是：GDHBAEICF

数据结构 --- Java之二叉树的实现

           （3）后序遍历：从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点；如图，遍历的顺序是：GHDBIEFCA

数据结构 --- Java之二叉树的实现

          （4）层序遍历：从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点进行逐个访问；如图，遍历顺序为：ABCDEFGHI

数据结构 --- Java之二叉树的实现


代码如下：

二叉树结点

[java] view plain copy
  1. package binaryTree;  
  2.   
  3. // 二叉树节点   
  4. public class BTNode  
  5. {  
  6.     private char key;                  // 数据  
  7.     private BTNode left, right;    // 左右子结点  
  8.   
  9.     public BTNode(char key)  
  10.     {  
  11.         this(key, null, null);  
  12.     }  
  13.   
  14.     public BTNode(char key, BTNode left, BTNode right)  
  15.     {  
  16.         this.key = key;  
  17.         this.left = left;  
  18.         this.right = right;  
  19.     }  
  20.   
  21.     public char getKey()  
  22.     {  
  23.         return key;  
  24.     }  
  25.   
  26.     public void setKey(char key)  
  27.     {  
  28.         this.key = key;  
  29.     }  
  30.   
  31.     public BTNode getLeft()  
  32.     {  
  33.         return left;  
  34.     }  
  35.   
  36.     public void setLeft(BTNode left)  
  37.     {  
  38.         this.left = left;  
  39.     }  
  40.   
  41.     public BTNode getRight()  
  42.     {  
  43.         return right;  
  44.     }  
  45.   
  46.     public void setRight(BTNode right)  
  47.     {  
  48.         this.right = right;  
  49.     }  
  50.   
  51. }  

二叉树遍历：

[java] view plain copy
  1. package binaryTree;  
  2.   
  3. import java.util.Stack;  
  4.   
  5. // 遍历二叉树   
  6. public class BinTree  
  7. {  
  8.     protected BTNode root;  
  9.   
  10.     public BinTree(BTNode root)  
  11.     {  
  12.         this.root = root;  
  13.     }  
  14.   
  15.     public BTNode getRoot()  
  16.     {  
  17.         return root;  
  18.     }  
  19.   
  20.     // 初始化，构造二叉树  
  21.     public static BTNode init()  
  22.     {  
  23.         BTNode a = new BTNode('A');  
  24.         BTNode b = new BTNode('B', null, a);  
  25.         BTNode c = new BTNode('C');  
  26.         BTNode d = new BTNode('D', b, c);  
  27.         BTNode e = new BTNode('E');  
  28.         BTNode f = new BTNode('F', e, null);  
  29.         BTNode g = new BTNode('G', null, f);  
  30.         BTNode h = new BTNode('H', d, g);  
  31.         return h;         // 根结点  
  32.     }  
  33.   
  34.     // 访问节点  
  35.     public static void visit(BTNode p)  
  36.     {  
  37.         System.out.print(p.getKey() + " ");  
  38.     }  
  39.   
  40.     // 递归实现前序遍历  
  41.     protected static void preorder(BTNode p)  
  42.     {  
  43.         if (p != null)  
  44.         {  
  45.             visit(p);  
  46.             preorder(p.getLeft());  
  47.             preorder(p.getRight());  
  48.         }  
  49.     }  
  50.   
  51.     // 递归实现中序遍历  
  52.     protected static void inorder(BTNode p)  
  53.     {  
  54.         if (p != null)  
  55.         {  
  56.             inorder(p.getLeft());  
  57.             visit(p);  
  58.             inorder(p.getRight());  
  59.         }  
  60.     }  
  61.   
  62.     // 递归实现后序遍历  
  63.     protected static void postorder(BTNode p)  
  64.     {  
  65.         if (p != null)  
  66.         {  
  67.             postorder(p.getLeft());  
  68.             postorder(p.getRight());  
  69.             visit(p);  
  70.         }  
  71.     }  
  72.   
  73.     // 非递归实现前序遍历  
  74.     protected static void iterativePreorder(BTNode p)  
  75.     {  
  76.         Stack<BTNode> stack = new Stack<BTNode>();  
  77.         if (p != null)  
  78.         {  
  79.             stack.push(p);  
  80.             while (!stack.empty())  
  81.             {  
  82.                 p = stack.pop();  
  83.                 visit(p);  
  84.                 if (p.getRight() != null)  
  85.                     stack.push(p.getRight());  
  86.                 if (p.getLeft() != null)  
  87.                     stack.push(p.getLeft());  
  88.             }  
  89.         }  
  90.     }  
  91.   
  92.     // 非递归实现后序遍历  
  93.     protected static void iterativePostorder(BTNode p)  
  94.     {  
  95.         BTNode q = p;  
  96.         Stack<BTNode> stack = new Stack<BTNode>();  
  97.         while (p != null)  
  98.         {  
  99.             // 左子树入栈  
  100.             for (; p.getLeft() != null; p = p.getLeft())  
  101.                 stack.push(p);  
  102.             // 当前结点无右子结点或右子结点已经输出  
  103.             while (p != null && (p.getRight() == null || p.getRight() == q))  
  104.             {  
  105.                 visit(p);  
  106.                 q = p;        // 记录上一个已输出结点  
  107.                 if (stack.empty())  
  108.                     return;  
  109.                 p = stack.pop();  
  110.             }  
  111.             // 处理右子结点  
  112.             stack.push(p);  
  113.             p = p.getRight();  
  114.         }  
  115.     }  
  116.   
  117.     // 非递归实现中序遍历  
  118.     protected static void iterativeInorder(BTNode p)  
  119.     {  
  120.         Stack<BTNode> stack = new Stack<BTNode>();  
  121.         while (p != null)  
  122.         {  
  123.             while (p != null)  
  124.             {  
  125.                 if (p.getRight() != null)  
  126.                     stack.push(p.getRight());   // 当前结点右子结点入栈  
  127.                 stack.push(p);                  // 当前结点入栈  
  128.                 p = p.getLeft();  
  129.             }  
  130.             p = stack.pop();  
  131.             while (!stack.empty() && p.getRight() == null)  
  132.             {  
  133.                 visit(p);  
  134.                 p = stack.pop();  
  135.             }  
  136.             visit(p);  
  137.             if (!stack.empty())  
  138.                 p = stack.pop();  
  139.             else  
  140.                 p = null;  
  141.         }  
  142.     }  
  143.   
  144.     public static void main(String[] args)  
  145.     {  
  146.         BinTree tree = new BinTree(init());  
  147.   
  148.         System.out.print(" 递归实现前序遍历:");  
  149.         preorder(tree.getRoot());  
  150.         System.out.println("\n");  
  151.   
  152.         System.out.print(" 递归实现中序遍历:");  
  153.         inorder(tree.getRoot());  
  154.         System.out.println("\n");  
  155.   
  156.         System.out.print(" 递归实现后序遍历:");  
  157.         postorder(tree.getRoot());  
  158.         System.out.println("\n");  
  159.   
  160.         System.out.print(" 非递归实现前序遍历:");  
  161.         iterativePreorder(tree.getRoot());  
  162.         System.out.println("\n");  
  163.   
  164.         System.out.print(" 非递归实现中序遍历:");  
  165.         iterativeInorder(tree.getRoot());  
  166.         System.out.println("\n");  
  167.   
  168.         System.out.print(" 非递归实现后序遍历:");  
  169.         iterativePostorder(tree.getRoot());  
  170.         System.out.println("\n");  
  171.   
  172.     }  
  173. }  

相关推荐