• 数据结构与算法之-树的概念(二叉树)
  • 浪子 发表于 2014/11/20 10:11:00 | 分类标签: 数据结构 算法 二叉树
  • 一、树

    树形结构是一类重要的非线性结构。树形结构是结点之间有分支,并具有层次关系的结构。它非常类似于自然界中的树。树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。本章重点讨论二叉树的存储表示及其各种运算,并研究一般树和森林与二叉树的转换关系,最后介绍树的应用实例。

    二、二叉树

    二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树右子树的二叉树组成。关于更多概念,请大家自己上网查询,我们这里将用代码实现常见的算法。更多的概念,请访问:http://student.zjzk.cn/course_ware/data_structure/web/SHU/shu6.2.3.1.htm 。

    1、二叉树的建立

    首先,我们采用广义表建立二叉树(关于广义表的概念,请查看百科的介绍:http://baike.baidu.com/view/203611.htm)

    我们建立一个字符串类型的广义表作为输入:

    String  expression = "A(B(D(,G)),C(E,F))";与该广义表对应的二叉树为:


    写代码前,我们通过观察二叉树和广义表,先得出一些结论:

    • 每当遇到字母,将要创建节点
    • 每当遇到“(”,表面要创建左孩子节点
    • 每当遇到“,”,表明要创建又孩子节点
    • 每当遇到“)”,表明要返回上一层节点
    • 广义表中“(”的数量正好是二叉树的层数

    根据这些结论,我们基本就可以开始写代码了。首先建议一个节点类(这也属于一种自定义的数据结构)。

    1. package com.xtfggef.algo.tree;  
    2.   
    3. public class Node {  
    4.   
    5.     private char data;  
    6.     private Node lchild;  
    7.     private Node rchild;  
    8.   
    9.     public Node(){  
    10.           
    11.     }  
    12.     public char getData() {  
    13.         return data;  
    14.     }  
    15.   
    16.     public void setData(char data) {  
    17.         this.data = data;  
    18.     }  
    19.   
    20.     public Node getRchild() {  
    21.         return rchild;  
    22.     }  
    23.   
    24.     public void setRchild(Node rchild) {  
    25.         this.rchild = rchild;  
    26.     }  
    27.   
    28.     public Node getLchild() {  
    29.         return lchild;  
    30.     }  
    31.   
    32.     public void setLchild(Node lchild) {  
    33.         this.lchild = lchild;  
    34.     }  
    35.   
    36.     public Node(char ch, Node rchild, Node lchild) {  
    37.         this.data = ch;  
    38.         this.rchild = rchild;  
    39.         this.lchild = lchild;  
    40.     }  
    41.   
    42.     public String toString() {  
    43.         return "" + getData();  
    44.     }  
    45. }  
    根据广义表创建二叉树的代码如下:

    1. public Node createTree(String exp) {  
    2.         Node[] nodes = new Node[3];  
    3.         Node b, p = null;  
    4.         int top = -1, k = 0, j = 0;  
    5.         char[] exps = exp.toCharArray();  
    6.         char data = exps[j];  
    7.         b = null;  
    8.         while (j < exps.length - 1) {  
    9.             switch (data) {  
    10.             case '(':  
    11.                 top++;  
    12.                 nodes[top] = p;  
    13.                 k = 1;  
    14.                 break;  
    15.             case ')':  
    16.                 top--;  
    17.                 break;  
    18.             case ',':  
    19.                 k = 2;  
    20.                 break;  
    21.             default:  
    22.                 p = new Node(data, nullnull);  
    23.                 if (b == null) {  
    24.                     b = p;  
    25.                 } else {  
    26.                     switch (k) {  
    27.                     case 1:  
    28.                         nodes[top].setLchild(p);  
    29.                         break;  
    30.                     case 2:  
    31.                         nodes[top].setRchild(p);  
    32.                         break;  
    33.                     }  
    34.                 }  
    35.             }  
    36.             j++;  
    37.             data = exps[j];  
    38.         }  
    39.         return b;  
    40.     }  
    思路不难,结合上述的理论,自己断点走一遍程序就懂了!

    2、二叉树的递归遍历

    二叉树的遍历有三种:先序、中序、后序,每种又分递归和非递归。递归程序理解起来有一定的难度,但是实现起来比较简单。对于上述二叉树,其:

        a 先序遍历

                A B D G C E F

        b 中序遍历

               D G B A E C F 

        c 后序遍历

               G D B E F C A

    先、中、后序递归遍历如下:

    1. /** 
    2.      * pre order recursive 
    3.      *  
    4.      * @param node 
    5.      */  
    6.     public void PreOrder(Node node) {  
    7.         if (node == null) {  
    8.             return;  
    9.         } else {  
    10.             System.out.print(node.getData() + " ");  
    11.             PreOrder(node.getLchild());  
    12.             PreOrder(node.getRchild());  
    13.   
    14.         }  
    15.     }  
    16.   
    17.     /** 
    18.      * in order recursive 
    19.      *  
    20.      * @param node 
    21.      */  
    22.     public void InOrder(Node node) {  
    23.         if (node == null) {  
    24.             return;  
    25.         } else {  
    26.             InOrder(node.getLchild());  
    27.             System.out.print(node.getData() + " ");  
    28.             InOrder(node.getRchild());  
    29.         }  
    30.     }  
    31.   
    32.     /** 
    33.      * post order recursive 
    34.      *  
    35.      * @param node 
    36.      */  
    37.     public void PostOrder(Node node) {  
    38.         if (node == null) {  
    39.             return;  
    40.         } else {  
    41.             PostOrder(node.getLchild());  
    42.             PostOrder(node.getRchild());  
    43.             System.out.print(node.getData() + " ");  
    44.         }  
    45.     }  
    二叉树的递归遍历实现起来很简单,关键是非递归遍历有些难度,请看下面的代码:

    3、二叉树的非递归遍历

    先序非递归遍历:

    1. public void PreOrderNoRecursive(Node node) {  
    2.         Node nodes[] = new Node[CAPACITY];  
    3.         Node p = null;  
    4.         int top = -1;  
    5.         if (node != null) {  
    6.             top++;  
    7.             nodes[top] = node;  
    8.             while (top > -1) {  
    9.                 p = nodes[top];  
    10.                 top--;  
    11.                 System.out.print(p.getData() + " ");  
    12.                 if (p.getRchild() != null) {  
    13.                     top++;  
    14.                     nodes[top] = p.getRchild();  
    15.                 }  
    16.                 if (p.getLchild() != null) {  
    17.                     top++;  
    18.                     nodes[top] = p.getLchild();  
    19.                 }  
    20.             }  
    21.         }  
    22.     }  
    原理:利用一个栈,先序遍历即为根先遍历,先将根入栈,然后出栈,凡是出栈的元素都打印值,入栈之前top++,出栈之后top--,利用栈后进先出的原理,右节点先于左节点进栈,根出栈后,开始处理左子树,然后是右子树,读者朋友们可以自己走一遍程序看看,也不算难理解!

    中序非递归遍历:

    1. public void InOrderNoRecursive(Node node) {  
    2.         Node nodes[] = new Node[CAPACITY];  
    3.         Node p = null;  
    4.         int top = -1;  
    5.         if (node != null)  
    6.             p = node;  
    7.         while (p != null || top > -1) {  
    8.             while (p != null) {  
    9.                 top++;  
    10.                 nodes[top] = p;  
    11.                 p = p.getLchild();  
    12.             }  
    13.             if (top > -1) {  
    14.                 p = nodes[top];  
    15.                 top--;  
    16.                 System.out.print(p.getData() + " ");  
    17.                 p = p.getRchild();  
    18.             }  
    19.         }  
    20.     }  
    原理省略。

    后续非递归遍历:

    1. public void PostOrderNoRecursive(Node node) {  
    2.         Node[] nodes = new Node[CAPACITY];  
    3.         Node p = null;  
    4.         int flag = 0, top = -1;  
    5.         if (node != null) {  
    6.             do {  
    7.                 while (node != null) {  
    8.                     top++;  
    9.                     nodes[top] = node;  
    10.                     node = node.getLchild();  
    11.                 }  
    12.                 p = null;  
    13.                 flag = 1;  
    14.                 while (top != -1 && flag != 0) {  
    15.                     node = nodes[top];  
    16.                     if (node.getRchild() == p) {  
    17.                         System.out.print(node.getData() + " ");  
    18.                         top--;  
    19.                         p = node;  
    20.                     } else {  
    21.                         node = node.getRchild();  
    22.                         flag = 0;  
    23.                     }  
    24.                 }  
    25.             } while (top != -1);  
    26.         }  
    27.     }  

    三、树与二叉树的转换

    本人之前总结的:



    这部分概念的其他知识,请读者自己上网查看。

    原文地址:http://blog.csdn.net/zhangerqing/article/details/8822476

  • 请您注意

    ·自觉遵守:爱国、守法、自律、真实、文明的原则

    ·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规

    ·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品

    ·承担一切因您的行为而直接或间接导致的民事或刑事法律责任

    ·您在编程中国社区新闻评论发表的作品,本网站有权在网站内保留、转载、引用或者删除

    ·参与本评论即表明您已经阅读并接受上述条款

  • 感谢本文作者
  • 作者头像
  • 昵称:浪子
  • 加入时间:2013/6/13 0:00:00
  • TA的签名
  • 这家伙很懒,虾米都没写
  • +进入TA的空间
  • 以下内容也很赞哦
分享按钮