【Oracle】存储过程遍历树举例emp表的树状结构

心已赠人 2022-04-10 06:17 204阅读 0赞

# 树的遍历 #

编辑

[同义词][Link 1] 遍历树一般指树的遍历

树的遍历是树的一种重要的[运算][Link 2]。所谓[遍历][Link 3]是指对树中所有[结点][Link 4]的信息的访问，即依次对树中每个结点访问一次且仅访问一次。二叉树的3种最重要的遍历方式分别称为[前序遍历][Link 5]、[中序遍历][Link 6]和[后序遍历][Link 7]。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。

中文名

树的遍历

概    括

计算机的一种重要的运算

类    别

计算机语言

分    类

前序，中序、后序

## 目录 ##

1.  1 [定义][Link 8]
2.  2 [方法][Link 9]

## 定义 ##

编辑

树的这3种[遍历][Link 3]方式可[递归][Link 10]地定义如下：

如果T是一棵空树，那么对T进行[前序遍历][Link 5]、[中序遍历][Link 6]和[后序遍历][Link 7]都是空操作，得到的列表为空表。

如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。

否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有：

对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。

对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T3,..,Tk进行中序遍历。

对T进行[后序遍历][Link 7]是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。

[![树图结构][20181228103558601]][20181228103558601 1]树图结构

[前序遍历][Link 5]和中序[遍历][Link 3]可形式地依次描述如下 ：

三种遍历可以形式地描述如下，其中用到了树的[ADT][]操作：

Procedure Preorder\_Traversal(v:NodeType); \{前序遍历算法\}

begin

Visite(v); \{访问节点v\}

i:=Leftmost\_Child(v);

while i<>∧ do

begin

Preorder\_Traversal(i);\{从左到右依次访问v的每一个儿子节点i\}

i:=Right\_Sibling(i);

end;

Procedure Inorder\_Traversal(v:NodeType); \{ [中序遍历][Link 6]算法\}

begin

if Leftmost\_Child(v)=∧ \{判断v是否是叶节点\}

then Visite(v)

else

begin

Inorder\_Traversal(Leftmost\_Child(v)); \{中序遍历v的左边第一个儿子节点\}

Visite(v); \{访问节点v\}

i:=Right\_Sibling(Leftmost\_Child(v)); \{i=v的左边第二个儿子\}

while i<>∧ do

begin

Inorder\_Traversal(i);

\{从左边第二个开始到最右边一个为止依次访问v的每一个儿子节点i\}

i:=Right\_Sibling(i);

end;

Procedure Postorder\_Traversal(v:NodeType); \{ [后序遍历][Link 7]算法\}

begin

i:=Leftmost\_Child(v);

while i<>∧ do

begin

Preorder\_Traversal(i);\{从左到右依次访问v的每一个儿子节点i\}

i:=Right\_Sibling(i);

end;

Visite(v); \{访问节点v\}

end;

## 方法 ##

编辑

为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图7中的树进行[前序遍历][Link 5]、[中序遍历][Link 6]和[后序遍历][Link 7]将分别得到前序列表：A B E F I J

C D G H；中序列表：E B I F J A C G D H；后序列表：E I J F B C G H D A。

下面介绍一种方法可以产生上述3种[遍历][Link 3]方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。

在上述3种不同次序的列表方式中，各树叶之间的相对次序是相同的，它们都按树叶之间从左到右的次序排列。3种列表方式的差别仅在于内部结点之间以及内部结点与树叶之间的次序有所不同。

一棵树进行前序列表或后序列表有助于查询结点间的祖先子孙关系。假设结点v在后序列表中的序号(整数)为postorder(v)，我们称这个整数为结点v的后序编号。例如在图7中，结点E，I和J的后序编号分别为1，2和3。

结点的后序编号具有这样的特点：设结点v的真子孙个数为desc(v)，那么在以v为根的子树中的所有结点的后序编号恰好落在postorder(v)- desc(v)与postorder(v)之间。因此为了检验结点x是否为结点y的子孙，我们只要判断它们的后序编号是否满足：

postorder(y)-desc(y)≤postorder(x)≤postorder(y)

前序编号也具有类似的性质。

学术论文

内容来自[ ][Link 11]

![20181228103558647][]

*   [舒栋才，程根伟.    基于多叉树的遍历算法在数字水系拓扑关系计算中的应用． ][.]《 长江流域资源与环境 》 ， 2006
 *   
 *   [彭启伟，张浩.    基于多叉树遍历的中压配电线载波自适应中继算法． ][. 1]《 电力系统通信 》 ， 2009
 *   
 *   [张亚萍，陈得宝，侯俊钦.    二叉树遍历教学方法研究． ][. 2]《 牡丹江师范学院学报(自然科学版) 》 ， 2010
 *   
 *   [孟林，尹德辉.    二叉树遍历递归算法非递归化的讨论． ][. 3]《 福建电脑 》 ， 2004
 *   
 *   [徐凤生，李立群，马夕荣.    二叉树遍历的通用非递归算法． ][. 4]《 福建电脑 》 ， 2006

[查看全部 ![toggle_185d48f.svg][]][toggle_185d48f.svg 1]

[https://baike.baidu.com/item/%E9%81%8D%E5%8E%86/9796023?fr=aladdin][https_baike.baidu.com_item_E9_81_8D_E5_8E_86_9796023_fr_aladdin]

## **使用存储过程求emp表的树状结构** ##

求出每个员工的上级（经理）并输出

create or replace procedure p_emp(v_empno emp.empno%type,v_level binary_integer) is
    
      cursor c is
    
        select * from emp where mgr = v_empno;
    
      v_str varchar2(256) := '';
    
    begin
    
      for i in 1..v_level loop
    
        v_str := v_str || '   ';
    
      end loop;
    
      for emp in c loop
    
        dbms_output.put_line(v_str || emp.ename);
    
        p_emp(emp.empno,v_level+1);--递归调用存储过程
    
      end loop;
    
    end;
    
     
    
    --求出没有经理的员工
    
    declare
    
      v_emp emp%rowtype;
    
    begin
    
      select * into v_emp from emp where mgr is null;
    
      dbms_output.put_line(v_emp.ename);
    
      p_emp(v_emp.empno, 1);
    
    end;
    
     
    
    --或者我们已经知道7839是没有上级的
    
     
    
    begin
    
      p_emp(7839, 1);
    
    end;
    
     
    
    --输出
    
    KING
    
       JONES
    
          SCOTT
    
             ADAMS
    
          FORD
    
             SMITH
    
       BLAKE
    
          ALLEN
    
          WARD
    
          MARTIN
    
          TURNER
    
          JAMES
    
       CLARK
    
          MILLER

[https://www.cnblogs.com/hjwublog/p/5968097.html?utm\_source=itdadao&utm\_medium=referral][https_www.cnblogs.com_hjwublog_p_5968097.html_utm_source_itdadao_utm_medium_referral]

## 利用oracle存储过程生成树编码 ##

### 需求 ###

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 字段 </td> 
 <td style="vertical-align:top;"> 描述 </td> 
 <td style="vertical-align:top;"> 备注 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> ID </td> 
 <td style="vertical-align:top;"> 主键，32位UUID </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> TYPE_CODE </td> 
 <td style="vertical-align:top;"> 编码 </td> 
 <td style="vertical-align:top;"> 如：1-01-003 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> PARENT_ID </td> 
 <td style="vertical-align:top;"> 父节点ID，32位UUID </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> SORT_NUM </td> 
 <td style="vertical-align:top;"> 排序编号 </td> 
 <td style="vertical-align:top;"> 正整数 </td> 
 </tr> 
 </tbody> 
</table>

假设顶级节点的TYPE\_CODE为字符1，写存储过程把表中所有的节点TYPE\_CODE生成好；

二级节点前面补一个龄，三级补两个零，依次类推；

### 实现关键点 ###

n 不知道[系统][Link 12]有多少层级，需要递归调用

通过递归调用自身；

n 如何动态在TYPE\_CODE前面填充‘0’；通过计算‘-’的个数来确定层级，从而确定前缀的个数

tree\_level:= (length(p\_code)-length(replace(p\_code,'-',''))) + 1;

n 前面填充前缀‘0’字符

lpad(to\_char(cnt),tree\_level,'0')

### 存储过程代码 ###

[?][Link 13]

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 </td> 
 <td> <code>CREATEOR </code><code>REPLACE</code> <code>PROCEDURE</code> <code>INI_TREE_CODE</code> &nbsp; <code>(</code> &nbsp; <code>&nbsp;&nbsp;</code><code>V_PARENT_ID </code><code>IN</code> <code>VARCHAR2 </code> &nbsp; <code>)</code><code>AS</code> &nbsp; <code>&nbsp;&nbsp;</code><code>p_id&nbsp; varchar2(32);</code> &nbsp; <code>&nbsp;&nbsp;</code><code>p_code varchar2(256);</code> &nbsp; <code>&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;</code><code>sub_num&nbsp;&nbsp; number(4,0);</code> &nbsp; <code>&nbsp;&nbsp;</code><code>tree_level number(4,0); </code> &nbsp; <code>&nbsp;&nbsp;</code><code>cnt&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; number(4,0) </code><code>default</code> <code>0;</code> &nbsp; <code>&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;</code><code>cursor</code> <code>treeCur(oid varchar2) </code><code>is</code> &nbsp; <code>&nbsp;&nbsp;</code><code>select</code> <code>id,TYPE_CODE </code><code>from</code> <code>eval_index_type</code> &nbsp; <code>&nbsp;&nbsp;</code><code>where</code> <code>parent_id = oid</code> &nbsp; <code>&nbsp;&nbsp;</code><code>order</code> <code>by</code> <code>sort_num;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; &nbsp; <code>BEGIN</code> &nbsp; <code>&nbsp;&nbsp;</code><code>sub_num := 0;</code> &nbsp; <code>&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;</code><code>select</code> <code>id,type_code </code><code>into</code> <code>p_id,p_code</code> &nbsp; <code>&nbsp;&nbsp;</code><code>from</code> <code>eval_index_type</code> &nbsp; <code>&nbsp;&nbsp;</code><code>where</code> <code>id = V_PARENT_ID</code> &nbsp; <code>&nbsp;&nbsp;</code><code>order</code> <code>by</code> <code>sort_num;</code> &nbsp; <code>&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;</code><code>for</code> <code>curRow </code><code>in</code> <code>treeCur(p_id) loop</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cnt := cnt +1;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>tree_level :=(length(p_code)-length(</code><code>replace</code><code>(p_code,</code><code>'-'</code><code>,</code><code>''</code><code>))) + 1;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>update</code> <code>eval_index_type </code><code>set</code> <code>type_code =p_code || </code><code>'-'</code> <code>|| lpad(to_char(cnt) ,tree_level,</code><code>'0'</code><code>)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>where</code> <code>id = curRow.id;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>select</code> <code>COUNT</code><code>(*) </code><code>into</code> <code>sub_num fromeval_index_type </code><code>where</code> <code>parent_id = p_id;</code> &nbsp; <code>&nbsp;</code>&nbsp; &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if sub_num &gt; 0 </code><code>then</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>INI_TREE_CODE (curRow.id);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end</code> <code>if; </code> &nbsp; <code>&nbsp;&nbsp;</code><code>end</code> <code>loop;</code> &nbsp; <code>ENDINI_TREE_CODE;</code> </td> 
 </tr> 
 </tbody> 
</table>

[https://www.2cto.com/database/201412/358382.html][https_www.2cto.com_database_201412_358382.html]

[Link 1]: https://baike.baidu.com/subview/71844/10028254.htm
[Link 2]: https://baike.baidu.com/item/%E8%BF%90%E7%AE%97/5866856
[Link 3]: https://baike.baidu.com/item/%E9%81%8D%E5%8E%86/9796023
[Link 4]: https://baike.baidu.com/item/%E7%BB%93%E7%82%B9/9794643
[Link 5]: https://baike.baidu.com/item/%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86/757319
[Link 6]: https://baike.baidu.com/item/%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86/757281
[Link 7]: https://baike.baidu.com/item/%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86/1214806
[Link 8]: https://baike.baidu.com/item/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86?fromtitle=%E9%81%8D%E5%8E%86%E6%A0%91&fromid=15906791#1
[Link 9]: https://baike.baidu.com/item/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86?fromtitle=%E9%81%8D%E5%8E%86%E6%A0%91&fromid=15906791#2
[Link 10]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[20181228103558601]: https://img-blog.csdnimg.cn/20181228103558601
[20181228103558601 1]: /images/20220402/7170c6209762411fb72c7d1dd4316be5.png
[ADT]: https://baike.baidu.com/item/ADT/8945833
[Link 11]: https://xueshu.baidu.com/?site=baike
[20181228103558647]: /images/20220402/736e7396524947ef82588cc09ac41d4d.png
[.]: https://xueshu.baidu.com/usercenter/paper/show?paperid=4d1ac123ed91c5d037e3b386b2a36b3a&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&site=baike
[. 1]: https://xueshu.baidu.com/usercenter/paper/show?paperid=98d2552bb7d0386e364294e9e09ff9f0&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&site=baike
[. 2]: https://xueshu.baidu.com/usercenter/paper/show?paperid=236edf8a82c895522e3fc925c9f23d0b&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&site=baike
[. 3]: https://xueshu.baidu.com/usercenter/paper/show?paperid=c96120041743e4a4a7758d4bb091f535&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&site=baike
[. 4]: https://xueshu.baidu.com/usercenter/paper/show?paperid=7ee6e9a6d5c48f1d4364b673443db8e0&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&site=baike
[toggle_185d48f.svg]: /images/20220402/54f9904a617346afa3f61255c88dfebf.png
[toggle_185d48f.svg 1]: https://xueshu.baidu.com/s?wd=intitle%3A%28%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86%29&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_from=pingtai7&site=baike
[https_baike.baidu.com_item_E9_81_8D_E5_8E_86_9796023_fr_aladdin]: https://baike.baidu.com/item/%E9%81%8D%E5%8E%86/9796023?fr=aladdin
[https_www.cnblogs.com_hjwublog_p_5968097.html_utm_source_itdadao_utm_medium_referral]: https://www.cnblogs.com/hjwublog/p/5968097.html?utm_source=itdadao&utm_medium=referral
[Link 12]: https://www.2cto.com/os/
[Link 13]: https://www.2cto.com/database/201412/358382.html#
[https_www.2cto.com_database_201412_358382.html]: https://www.2cto.com/database/201412/358382.html