请选择 进入手机版 | 继续访问电脑版
楼主: Lisrelchen
2918 9

[其他] [C语言源码]树的非递归中序和层次遍历实现 [推广有奖]

  • 0关注
  • 62粉丝

VIP

院士

67%

还不是VIP/贵宾

-

TA的文库  其他...

Bayesian NewOccidental

Spatial Data Analysis

东西方数据挖掘

威望
0
论坛币
49955 个
通用积分
79.3687
学术水平
253 点
热心指数
300 点
信用等级
208 点
经验
41518 点
帖子
3256
精华
14
在线时间
766 小时
注册时间
2006-5-4
最后登录
2022-11-6

Lisrelchen 发表于 2015-4-4 10:54:36 |显示全部楼层 |坛友微信交流群
相似文件 换一批

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. // Author: 过往记忆
  4. // Email: wyphao.2007@163.com
  5. // Blog: http://www.iteblog.com


  6. // TreeNode
  7. //////////////////////////////////////////////////////////////////////////
  8. typedef struct TreeNode
  9. {
  10.     char m_cVal;
  11.     TreeNode* m_pLeft;
  12.     TreeNode* m_pRight;

  13.     TreeNode(char cVal);
  14.     ~TreeNode();
  15. };

  16. TreeNode::TreeNode(char cVal)
  17. {
  18.     m_cVal = cVal;
  19.     m_pLeft = 0;
  20.     m_pRight = 0;
  21. }

  22. TreeNode::~TreeNode()
  23. {

  24. }

  25. //Stack
  26. //////////////////////////////////////////////////////////////////////////
  27. class Stack
  28. {
  29. public:
  30.     Stack(int iAmount = 10);
  31.     ~Stack();

  32. //return 1 means succeeded, 0 means failed.
  33.     int Pop(TreeNode* &pVal);
  34.     int Push(TreeNode* pVal);
  35.     int Top(TreeNode* &pVal);

  36. //1 means not null, 0 means null.
  37.     int NotNull();
  38. private:
  39.     TreeNode **m_ppData;
  40.     int m_iCount;
  41.     int m_iAmount;
  42. };

  43. Stack::Stack(int iAmount)
  44. {
  45.     m_ppData = new TreeNode*[iAmount];
  46.     m_iCount = 0;
  47.     m_iAmount = iAmount;
  48. }

  49. Stack::~Stack()
  50. {
  51.     delete m_ppData;
  52. }

  53. int Stack::Pop(TreeNode* &pVal)
  54. {
  55.     if(m_iCount>0)
  56.     {
  57.         --m_iCount;
  58.         pVal = m_ppData[m_iCount];
  59.         return 1;
  60.     }
  61.     return 0;
  62. }

  63. int Stack::Push(TreeNode* pVal)
  64. {
  65.     if(m_iCount<m_iAmount)
  66.     {
  67.         m_ppData[m_iCount] = pVal;
  68.         ++m_iCount;
  69.         return 1;
  70.     }
  71.     return 0;
  72. }

  73. int Stack::Top(TreeNode* &pVal)
  74. {
  75.     if(m_iCount>0 && m_iCount<=m_iAmount)
  76.     {
  77.         pVal = m_ppData[m_iCount-1];
  78.         return 1;
  79.     }
  80.     return 0;
  81. }

  82. int Stack::NotNull()
  83. {
  84.     if(m_iCount!=0)
  85.         return 1;
  86.     return 0;
  87. }

  88. //Queue
  89. //////////////////////////////////////////////////////////////////////////
  90. class Queue
  91. {
  92. public:
  93.     Queue(int nMounts);
  94.     ~Queue();
  95.    
  96.     //operator
  97.     int EnQueue(TreeNode *node);
  98.     int DeQueue(TreeNode *&node);
  99.     int IsFull();
  100.     int IsEmpty();
  101.    
  102. private:
  103.     TreeNode **Q;
  104.     int front;
  105.     int rear;
  106.     int totalNode;
  107. };

  108. Queue::Queue(int nMounts = 10){
  109.         Q = new TreeNode*[nMounts];
  110.         totalNode = nMounts;
  111.         rear = 0;
  112.         front = 0;
  113. }

  114. Queue::~Queue(){
  115.         delete Q;
  116. }

  117. int Queue::EnQueue(TreeNode *node){
  118.         if(!IsFull()){
  119.                 Q[rear] = node;
  120.                 rear = (rear + 1) % totalNode;
  121.         }else{
  122.                 //printf("Queue is full!\n");
  123.                 return 0;
  124.         }
  125.         
  126.         return 1;
  127. }

  128. int Queue::DeQueue(TreeNode *&node){
  129.         if(!IsEmpty()){
  130.                 node = Q[front];
  131.                 front = (front + 1) % totalNode;
  132.         }else{
  133.                 //printf("Queue is empty!\n");
  134.                 return 0;
  135.         }
  136.         return 1;
  137. }

  138. int Queue::IsFull(){
  139.         if((rear + 1) % totalNode == front){
  140.                 return 1;
  141.         }
  142.         return 0;
  143. }

  144. int Queue::IsEmpty(){
  145.         if(rear == front){
  146.                 return 1;
  147.         }
  148.         return 0;
  149. }


  150. int main(int argc, char* argv[])
  151. {
  152.     TreeNode nA('A');
  153.     TreeNode nB('B');
  154.     TreeNode nC('C');
  155.     TreeNode nD('D');
  156.     TreeNode nE('E');
  157.     TreeNode nF('F');
  158.     TreeNode nG('G');
  159.     TreeNode nH('H');
  160.     TreeNode nI('I');
  161.     TreeNode nJ('J');
  162.     TreeNode nK('K');
  163.     TreeNode nL('L');

  164.     nA.m_pLeft = &nB;
  165.     nA.m_pRight = &nC;
  166.     nB.m_pRight = &nD;
  167.     nD.m_pRight = &nG;
  168.     nC.m_pLeft = &nE;
  169.     nC.m_pRight = &nF;
  170.     nF.m_pRight = &nH;
  171.     nH.m_pLeft = &nI;
  172.     nH.m_pRight = &nJ;
  173.     nI.m_pLeft = &nK;
  174.     nI.m_pRight = &nL;

  175.     Stack st;
  176.         
  177.         //非递归中序遍历
  178.     TreeNode *pVal = &nA;
  179.     int iPopped = 0;
  180.     while(pVal!=0)
  181.     {
  182.         if(pVal->m_pLeft!=0 && iPopped==0)
  183.         {
  184.             st.Push(pVal);
  185.             pVal = pVal->m_pLeft;
  186.             iPopped = 0;
  187.         }
  188.         else if(pVal->m_pRight!=0)
  189.         {
  190.             printf("%c ", pVal->m_cVal);
  191.             pVal = pVal->m_pRight;
  192.             iPopped = 0;
  193.         }
  194.         else
  195.         {
  196.             printf("%c ", pVal->m_cVal);
  197.             if(0==st.Pop(pVal))
  198.                 break;
  199.             iPopped = 1;
  200.         }
  201.     }
  202.    
  203.     printf("\n");
  204.    
  205.     //层次遍历
  206.     pVal = &nA;
  207.     Queue queue;
  208.     while(pVal != NULL){
  209.             if(pVal->m_pLeft != NULL && pVal->m_pRight != NULL){
  210.                     queue.EnQueue(pVal->m_pLeft);
  211.                         queue.EnQueue(pVal->m_pRight);
  212.             }else if(pVal->m_pLeft != NULL){
  213.                     queue.EnQueue(pVal->m_pLeft);
  214.             }else if(pVal->m_pRight != NULL){
  215.                     queue.EnQueue(pVal->m_pRight);
  216.             }
  217.                    printf("%c ", pVal->m_cVal);
  218.                    if(0 == queue.DeQueue(pVal)){
  219.                            break;
  220.                    }
  221.     }
  222.         printf("\n");
  223.     return 0;
  224. }
复制代码

相信大家对树的各种递归的遍历很了解,利用递归使得代码变得简单而且比较好理解,但是利用递归是需要代价的,特别是当递归层次比较深的时候,可能会导致递归栈溢出。而且递归一般运行速度比较慢,那么这种情况下,我们就可以采用非递归来实现,非递归相对递归来说,代码相对比较难理解,而且代码量也一般比较多,可是它的执行效率却是很不错的。
在树的中序非递归遍历中需要用到栈,在层次遍历中需要用到队列,非递归中序遍历的思想如下:

  • 先设一个栈st和一个指向树根的指针pVal ,用pVal 指指向结点的m_pLeft(左孩子)并顺其而下直到pVal ==NULL跳出循环,在这一过程中把每个节点入栈,则此时的pVal 指向的是树的最左结点。
  • 栈顶元素出栈以访问最左结点。(此步很重要,是为了实现按栈内元素的顺序后入先出访问结点访问最左结点的根结点。栈内元素逐一退栈即为中序遍历的元素顺序。)
  • 访问最左结点的根结点。
  • 由于将右子树理解为一个子树,对其的遍历也是采用中序遍历的方法,故将右子树的根结点理解为开始遍历树时的根结点,故可用语句pVal = pVal->m_pRight,则又开始了对一个树的遍历,pVal 指针又会走遍右子树的每一个结点。

非递归中序遍历的思想如下:

  • 按层次遍历需要一个队列,开始将二叉树的头结点入队
  • 然后每次从队列中删除一个节点并输出节点信息,接下来把它的非空
  • 左右孩子入队,下一个输出的位它的右面堂兄弟或兄弟节点信息,在把它的
  • 左右孩子入队,这两个孩子在上面两个孩子的后面(紧跟其后)
  • 这样当队列为空时算法结束


二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:C语言 include succeed Private amount include C语言 Email

回帖推荐

jerker 发表于3楼  查看完整内容

[*]--贴段MS SQL SERVER代码,CTE递归查询,与Lisrelchen探讨。 [*]--执行环境:SQL Server 2008 [*]IF OBJECT_ID('MENU') IS NOT NULL DROP TABLE MENU; [*] [*]CREATE TABLE MENU [*] ( [*] name nvarchar(50) NOT NULL PRIMARY KEY, [*] senior nvarchar(50) NULL [*]); [*] [*] INSERT INTO MENU values [*] ('文件',NULL), [*] ('新建','文件'), [*] ('项目','新建'), [*] ...
已有 4 人评分经验 论坛币 学术水平 热心指数 信用等级 收起 理由
xujingtang + 40 + 1 精彩帖子
离歌レ笑 + 30 + 1 + 1 精彩帖子
fantuanxiaot + 60 + 30 + 1 + 1 + 1 精彩帖子
jerker + 40 + 40 精彩帖子

总评分: 经验 + 140  论坛币 + 100  学术水平 + 2  热心指数 + 3  信用等级 + 1   查看全部评分

本帖被以下文库推荐

igs816 在职认证  发表于 2015-4-4 15:06:27 |显示全部楼层 |坛友微信交流群
C的算法,用python实现会简洁的多,如果用F#之类的函数语言更简洁。
已有 1 人评分论坛币 收起 理由
fantuanxiaot + 5 精彩帖子

总评分: 论坛币 + 5   查看全部评分

使用道具

jerker 发表于 2015-4-4 21:01:27 |显示全部楼层 |坛友微信交流群
  • --贴段MS SQL SERVER代码,CTE递归查询,与Lisrelchen探讨。


  • --执行环境:SQL Server 2008



  • IF OBJECT_ID('MENU') IS NOT NULL DROP TABLE MENU;

  • CREATE TABLE MENU
  • (
  •     name nvarchar(50) NOT NULL PRIMARY KEY,
  •     senior nvarchar(50) NULL
  • );
  • INSERT INTO MENU values
  •     ('文件',NULL),
  •     ('新建','文件'),
  •     ('项目','新建'),
  •     ('使用当前连接查询','新建');

  • ;WITH lmenu(name,senior,level) as
  • (
  •     SELECT NAME,SENIOR,0 level FROM MENU WHERE SENIOR IS NULL
  •     UNION ALL
  •     SELECT A.NAME,A.SENIOR,b.level+1 FROM MENU A,lmenu b
  •     where a.senior = b.name
  • )
  • SELECT *  from lmenu;



QQ截图20150404210002.png


已有 1 人评分论坛币 学术水平 热心指数 信用等级 收起 理由
fantuanxiaot + 20 + 1 + 1 + 1 精彩帖子

总评分: 论坛币 + 20  学术水平 + 1  热心指数 + 1  信用等级 + 1   查看全部评分

使用道具

Edwardliu 在职认证  发表于 2015-4-5 07:34:53 |显示全部楼层 |坛友微信交流群
已有 1 人评分论坛币 收起 理由
jerker + 5 精彩帖子

总评分: 论坛币 + 5   查看全部评分

使用道具

ydb8848 发表于 2015-4-5 08:26:45 |显示全部楼层 |坛友微信交流群

使用道具

honghudu 发表于 2015-4-5 08:56:01 |显示全部楼层 |坛友微信交流群

使用道具

hyq2003 发表于 2015-4-5 10:09:42 |显示全部楼层 |坛友微信交流群

使用道具

rrjj101022 发表于 2015-4-5 10:28:02 |显示全部楼层 |坛友微信交流群
谢谢分享。这种实例代码帖很好
已有 1 人评分论坛币 收起 理由
jerker + 5 精彩帖子

总评分: 论坛币 + 5   查看全部评分

使用道具

am4444 发表于 2015-4-5 12:00:39 |显示全部楼层 |坛友微信交流群
不错 学习了啊 !!!!!!!!!!!!!!!!!!!!!!!!!!!!
已有 1 人评分论坛币 收起 理由
fantuanxiaot + 10 精彩帖子

总评分: 论坛币 + 10   查看全部评分

使用道具

cc457921 发表于 2015-4-7 08:44:32 |显示全部楼层 |坛友微信交流群
来学习!来研究!!

使用道具

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加好友,备注jr
拉您进交流群

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2024-3-28 23:32