您的位置: 首页  >  文章  >  二叉树基础概念

二叉树基础概念

分类: 文章 • 2025-02-24 13:07:34

【数据结构和算法】【二叉树】二叉树遍历的代码实现

二叉树的顺序存储结构：
使用数组表示，将二叉树填充为完全二叉树并依次自上而下、自左至右进行编号[1-n]，而后将编号为[1-n]的结点元素一一对应地存储在数组下标为[0-(n-1)]的数组元素中。

二叉树的链式存储结构：
1、二叉链表：结点中有两个链域（指针），分别指向左儿子、右儿子；
2、三叉链表：结点中有三个链域（指针），分别指向左儿子、右儿子、双亲；
3、线索链表：二叉链表的升级版本，将结点中的空链域利用起来，如：左空链域指向遍历的前一个结点，而右空链域指向遍历的后一个结点。

特殊的二叉树概念：
线索二叉树：使用线索链表表示的二叉树。也就是基于二叉链表表示的二叉树，将其结点中的空链域利用起来，使其左空链域指向遍历的前一个结点，右空链域指向遍历的后一个结点。

二叉树的遍历方式：先序遍历、中序遍历、后续遍历、层次遍历。
根据L、D、R（分别表示遍历左子树、访问根节点、遍历右子树）的组合，共有6种排列顺序。约定“先L后R”，则只有3中排列顺序，分别称之为：先序遍历DLR、中序遍历LDR、后序遍历LRD。
拿到一颗二叉树，快速写出各类遍历方式的结点访问顺序的方法参考《数据结构》P130“图6.10 三种遍历过程示意图”。
结点穿越原则：1、方向向下时，总是指向儿子结点的左侧；2、方向向上时，作为左儿子则指向双亲的左侧，作为右儿子则指向双亲的右侧；3、左儿子指向双亲后，再指向右儿子。

二叉树基础概念

三种遍历的非递归实现（空指针不入栈）总体步骤：
步骤1：建立堆栈并初始化；
步骤2：根指针入栈；（中序遍历时，根指针无需入栈）
步骤3：遍历过程；（重点！！）
步骤4：销毁堆栈。
注：
1、入栈时要判定指针是否为空，空的话就不入栈，以确保栈中的指针都是有对应节点的；
2、出栈时可以立即访问该节点（出栈==遍历/访问），因为入栈保证了都是非空节点。

遍历方式
 辅助变量
循环原则
 每次循环做的事情（空指针不入栈）
代码框架
先序遍历
p为出栈指针
栈不空时进行循环
出栈访问 -> 右子树入栈 ->  左子树入栈
 while (栈不空)
pop visit; push right; push left;
中序遍历
p为出栈指针和遍历指针，并初始为T
p不空或栈不空时进行循环
p不空则将p入栈，并将p指向其左子树；
p空则出栈访问，并将p指向栈顶结点的右子树；
while (栈不空 || p不空)
if (p) { push(p); p = p->left; }
else { pop visit; p = p->right; }
后续遍历
p为出栈指针；pre为已完成出栈/遍历的结点指针，并初始为NULL
栈不空时进行循环
查看栈顶指针(GetTop)：如果左右子树都完成了遍历或者pre为其左儿子或者pre为其右儿子则出栈访问并刷新pre；否则右子树入栈 ->  左子树入栈
while (栈不空)
GetTop(p);
if () { pop visit; pre = p; }
else { push right; push left; }


先序遍历二叉树（非递归 - 根指针不入栈）
[cpp] view plain copy
  1. void PreOrderTraverseNoRec(BiTree T)  
  2. {  
  3.     SqStack S; // 堆栈管理结构  
  4.     BiTree p; // 二叉树根节点指针  
  5.   
  6.     // 空树直接返回  
  7.     if (!T) return;  
  8.   
  9.     // STEP1: 建立堆栈并初始化  
  10.     (void)InitStack(&S);  
  11.   
  12.     // STEP2: 根指针入栈  
  13.     (void)Push(&S, &T);  
  14.   
  15.     // STEP3: 遍历  
  16.     while (!StackEmpty(&S))  
  17.     {  
  18.         (void)Pop(&S, &p);  
  19.         Visit(p->data);  
  20.         if (p->rchild) (void)Push(&S, &p->rchild);  
  21.         if (p->lchild) (void)Push(&S, &p->lchild);  
  22.     }  
  23.   
  24.     // STEP4: 销毁堆栈  
  25.     (void)DestroyStack(&S);  
  26.   
  27.     return;  
  28. }  

中序遍历二叉树（非递归 - 空指针不入栈）
[cpp] view plain copy
  1. void InOrderTraverseNoRec2(BiTree T)  
  2. {  
  3.     SqStack S;  
  4.     BiTree p; // 二叉树根节点指针  
  5.   
  6.     // 空树直接返回  
  7.     if (!T) return;  
  8.   
  9.     // STEP1: 建立堆栈并初始化  
  10.     (void)InitStack(&S);  
  11.   
  12.     // STEP2: 根指针在下面循环中入栈入栈  
  13.     //(void)Push(&S, &T);  
  14.   
  15.     // STEP3: 遍历  
  16.     p = T;  
  17.     while (p || !StackEmpty(&S))  
  18.     {  
  19.         if (p)  
  20.         {  
  21.             (void)Push(&S, &p);  
  22.             p = p->lchild;  
  23.         }  
  24.         else  
  25.         {  
  26.             (void)Pop(&S, &p);  
  27.             Visit(p->data);  
  28.             p = p->rchild;  
  29.         }  
  30.     }  
  31.   
  32.     // STEP4: 销毁堆栈  
  33.     (void)DestroyStack(&S);  
  34.   
  35.     return;  
  36. }  

后序遍历二叉树（非递归 - 空指针不入栈）
[cpp] view plain copy
  1. void PostOrderTraverseNoRec(BiTree T)  
  2. {  
  3.     SqStack S; // 堆栈管理结构  
  4.     BiTree p; // 二叉树根节点指针  
  5.     BiTree pre = NULL; // 已访问完成的二叉树根节点指针  
  6.   
  7.     // 空树直接返回  
  8.     if (!T) return;  
  9.   
  10.     // STEP1: 建立堆栈并初始化  
  11.     (void)InitStack(&S);  
  12.   
  13.     // STEP2: 根指针入栈  
  14.     (void)Push(&S, &T);  
  15.   
  16.     // STEP3: 遍历  
  17.     while (!StackEmpty(&S))  
  18.     {  
  19.         (void)GetTop(&S, &p);  
  20.         if ((!p->lchild && !p->rchild)  
  21.             || (pre && ((p->lchild == pre) || (p->rchild == pre))))  
  22.         {  
  23.             (void)Pop(&S, &p);  
  24.             Visit(p->data);  
  25.             pre = p;  
  26.         }  
  27.         else  
  28.         {  
  29.             if (p->rchild) (void)Push(&S, &p->rchild);  
  30.             if (p->lchild) (void)Push(&S, &p->lchild);  
  31.         }  
  32.     }  
  33.   
  34.     // STEP4: 销毁堆栈  
  35.     (void)DestroyStack(&S);  
  36.   
  37.     return;  
  38. }  


二叉树遍历的全部代码实现：

[cpp] view plain copy
  1. <span style="font-family:SimSun;">// Filename: bitree.c  
  2.   
  3. #include <stdio.h>  
  4. #include <stdlib.h>  
  5. #include "sq_stack.h"  
  6.   
  7. #ifndef _OK_  
  8. #define OK  0  
  9. #endif  
  10.   
  11. #ifndef _ERROR_  
  12. #define ERROR  1  
  13. #endif  
  14.   
  15. #ifndef _TRUE_  
  16. #define TRUE  1  
  17. #endif  
  18.   
  19. #ifndef _FALSE_  
  20. #define FALSE  0  
  21. #endif  
  22.   
  23. #ifndef _BiTNode_  
  24. #define _BiTNode_  
  25. typedef char TElemType;  
  26.   
  27. typedef struct BiTNode  
  28. {  
  29.     TElemType data;  
  30.     struct BiTNode *lchild;  
  31.     struct BiTNode *rchild;  
  32. } BiTNode, *BiTree;  
  33. #endif // _BiTNode_  
  34.   
  35. // 创建二叉树，按照先序遍历的方式进行输入  
  36. //               A  
  37. //      B                 ^  
  38. //  ^       C  
  39. //        ^    ^  
  40. //上面的二叉树对应的先序输入序列为： AB^C^^^  
  41. void CreateBiTree(BiTree *pT)  
  42. {  
  43.     char c;  
  44.     scanf("%c", &c);  
  45.   
  46.     if (' ' == c)  
  47.     {  
  48.         *pT = NULL;  
  49.     }  
  50.     else  
  51.     {  
  52.         *pT = (BiTNode *)malloc(sizeof(BiTNode));  
  53.         (*pT)->data = c;  
  54.         CreateBiTree(&(*pT)->lchild);  
  55.         CreateBiTree(&(*pT)->rchild);  
  56.     }  
  57.   
  58.     return;  
  59. }  
  60.   
  61. // 访问根结点  
  62. void Visit(char data)  
  63. {  
  64.     printf("%c", data);  
  65.     return;  
  66. }  
  67.   
  68. // 先序遍历二叉树（递归）  
  69. void PreOrderTraverse(BiTree T)  
  70. {  
  71.     if (!T) return;  
  72.     Visit(T->data);  
  73.     PreOrderTraverse(T->lchild);  
  74.     PreOrderTraverse(T->rchild);  
  75.     return;  
  76. }  
  77.   
  78. // 先序遍历二叉树（非递归 - 根指针不入栈）  
  79. void PreOrderTraverseNoRec(BiTree T)  
  80. {  
  81.     SqStack S;  // 堆栈管理结构  
  82.     BiTree p;   // 二叉树根节点指针  
  83.   
  84.     // 空树直接返回  
  85.     if (!T) return;  
  86.   
  87.     // STEP1: 建立堆栈并初始化  
  88.     (void)InitStack(&S);  
  89.   
  90.     // STEP2: 根指针入栈  
  91.     (void)Push(&S, &T);  
  92.   
  93.     // STEP3: 遍历  
  94.     while (!StackEmpty(&S))  
  95.     {  
  96.         (void)Pop(&S, &p);  
  97.         Visit(p->data);  
  98.         if (p->rchild) (void)Push(&S, &p->rchild);  
  99.         if (p->lchild) (void)Push(&S, &p->lchild);  
  100.     }  
  101.   
  102.     // STEP4: 销毁堆栈  
  103.     (void)DestroyStack(&S);  
  104.   
  105.     return;  
  106. }  
  107.   
  108. // 中序遍历二叉树（递归）  
  109. void InOrderTraverse(BiTree T)  
  110. {  
  111.     if (!T) return;  
  112.     InOrderTraverse(T->lchild);  
  113.     Visit(T->data);  
  114.     InOrderTraverse(T->rchild);  
  115.     return;  
  116. }  
  117.   
  118. // 中序遍历二叉树（非递归 - 空指针入栈）  
  119. void InOrderTraverseNoRec1(BiTree T)  
  120. {  
  121.     SqStack S;  
  122.     BiTree p; // 二叉树根节点指针  
  123.   
  124.     // 空树直接返回  
  125.     if (!T) return;  
  126.   
  127.     // STEP1: 建立堆栈并初始化  
  128.     (void)InitStack(&S);  
  129.   
  130.     // STEP2: 根指针入栈  
  131.     (void)Push(&S, &T);  
  132.   
  133.     // STEP3: 遍历  
  134.     while (!StackEmpty(&S))  
  135.     {  
  136.         while ((OK == GetTop(&S, &p)) && p)  
  137.         {  
  138.             (void)Push(&S, &p->lchild);  
  139.         }  
  140.   
  141.         (void)Pop(&S, &p);  
  142.   
  143.         if (!StackEmpty(&S))  
  144.         {  
  145.             (void)Pop(&S, &p); Visit(p->data);  
  146.             (void)Push(&S, &p->rchild);  
  147.         }  
  148.     }  
  149.   
  150.     // STEP4: 销毁堆栈  
  151.     (void)DestroyStack(&S);  
  152.   
  153.     return;  
  154. }  
  155.   
  156. // 中序遍历二叉树（非递归 - 空指针不入栈）  
  157. void InOrderTraverseNoRec2(BiTree T)  
  158. {  
  159.     SqStack S;  
  160.     BiTree p;    // 二叉树根节点指针  
  161.   
  162.     // 空树直接返回  
  163.     if (!T) return;  
  164.   
  165.     // STEP1: 建立堆栈并初始化  
  166.     (void)InitStack(&S);  
  167.   
  168.     // STEP2: 根指针在下面循环中入栈入栈  
  169.     //(void)Push(&S, &T);  
  170.   
  171.     // STEP3: 遍历  
  172.     p = T;  
  173.     while (p || !StackEmpty(&S))  
  174.     {  
  175.         if (p)  
  176.         {  
  177.             (void)Push(&S, &p);  
  178.             p = p->lchild;  
  179.         }  
  180.         else  
  181.         {  
  182.             (void)Pop(&S, &p);  
  183.             Visit(p->data);  
  184.             p = p->rchild;  
  185.         }  
  186.     }  
  187.   
  188.     // STEP4: 销毁堆栈  
  189.     (void)DestroyStack(&S);  
  190.   
  191.     return;  
  192. }  
  193.   
  194. // 后序遍历二叉树（递归）  
  195. void PostOrderTraverse(BiTree T)  
  196. {  
  197.     if (!T) return;  
  198.     PostOrderTraverse(T->lchild);  
  199.     PostOrderTraverse(T->rchild);  
  200.     Visit(T->data);  
  201.     return;  
  202. }  
  203.   
  204. // 后序遍历二叉树（非递归 - 根指针不入栈）  
  205. void PostOrderTraverseNoRec(BiTree T)  
  206. {  
  207.     SqStack S;  // 堆栈管理结构  
  208.     BiTree p;   // 二叉树根节点指针  
  209.     BiTree pre = NULL; // 已访问完成的二叉树根节点指针  
  210.   
  211.     // 空树直接返回  
  212.     if (!T) return;  
  213.   
  214.     // STEP1: 建立堆栈并初始化  
  215.     (void)InitStack(&S);  
  216.   
  217.     // STEP2: 根指针入栈  
  218.     (void)Push(&S, &T);  
  219.   
  220.     // STEP3: 遍历  
  221.     while (!StackEmpty(&S))  
  222.     {  
  223.         (void)GetTop(&S, &p);  
  224.         if ((!p->lchild && !p->rchild)  
  225.             || (pre && ((p->lchild == pre) || (p->rchild == pre))))  
  226.         {  
  227.             (void)Pop(&S, &p);  
  228.             Visit(p->data);  
  229.             pre = p;  
  230.         }  
  231.         else  
  232.         {  
  233.             if (p->rchild) (void)Push(&S, &p->rchild);  
  234.             if (p->lchild) (void)Push(&S, &p->lchild);  
  235.         }  
  236.     }  
  237.   
  238.     // STEP4: 销毁堆栈  
  239.     (void)DestroyStack(&S);  
  240.   
  241.     return;  
  242. }  
  243.   
  244. int main()  
  245. {  
  246.     BiTree T = NULL;  
  247.     int input;  
  248.   
  249.     while (1)  
  250.     {  
  251.         printf("----------------------------------\n");  
  252.         printf("二叉树基本操作\n");  
  253.         printf("----------------------------------\n");  
  254.         printf("0.建立二叉树的存储结构\n");  
  255.         printf("1.求解二叉树的前序遍历\n");  
  256.         printf("2.求解二叉树的中序遍历\n");  
  257.         printf("3.求解二叉树的后序遍历\n");  
  258.         printf("9.退出系统\n");  
  259.         printf("----------------------------------\n");  
  260.         printf("请选择:");  
  261.         scanf("%d", &input);  
  262.         getchar();  
  263.   
  264.         switch (input)  
  265.         {  
  266.             case 0:  
  267.                 printf("输入二叉树的先序序列结点值: --> ");  // 测试样例：ABC^^DE^G^^F^^^  
  268.                 CreateBiTree(&T);  
  269.                 printf("二叉树的链式存储结构建立完成!\n");  
  270.                 break;  
  271.   
  272.   
  273.             case 1:  
  274.                 printf("该二叉树的前序遍历序列（递归）是: --> ");   // 目标输出：ABCDEGF  
  275.                 PreOrderTraverse(T);  
  276.                 printf("\n");  
  277.   
  278.                 printf("该二叉树的前序遍历序列（非递归）是: --> ");  
  279.                 PreOrderTraverseNoRec(T);  
  280.                 printf("\n");  
  281.                 break;  
  282.   
  283.             case 2:  
  284.                 printf("该二叉树的中序遍历序列（递归）是:--> ");    // 目标输出：CBEGDFA  
  285.                 InOrderTraverse(T);  
  286.                 printf("\n");  
  287.   
  288.                 printf("该二叉树的中序遍历序列（非递归 空指针入栈）是:--> ");  
  289.                 InOrderTraverseNoRec1(T);  
  290.                 printf("\n");  
  291.   
  292.                 printf("该二叉树的中序遍历序列（非递归 空指针不入栈）是:--> ");  
  293.                 InOrderTraverseNoRec2(T);  
  294.                 printf("\n");  
  295.                 break;  
  296.   
  297.             case 3:  
  298.                 printf("该二叉树的后序遍历序列（递归）是: --> ");   // 目标输出：CGEFDBA  
  299.                 PostOrderTraverse(T);  
  300.                 printf("\n");  
  301.   
  302.                 printf("该二叉树的后序遍历序列（非递归）是: --> ");  
  303.                 PostOrderTraverseNoRec(T);  
  304.                 printf("\n");  
  305.                 break;  
  306.   
  307.             case 9:  
  308.                 printf("系统已退出！\n");  
  309.                 exit(0);  
  310.   
  311.             default:  
  312.                 printf("输入错误，退出！\n");  
  313.                 exit(0);  
  314.         }  
  315.     }  
  316.   
  317.     return 0;  
  318. }  
  319. </span>  

参考文章：http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

相关推荐