数据结构之二叉树递归操作

时间:2020-12-18 17:29:35
二叉树(binary tree)是n(n>=0)个结点的有限结合,该集合或者为空集( 空二叉树),或由一个根结点和两棵互不相交的,分别称为根结点的左子树( left subtree)和右子树(right subtree)的二叉树组成。
二叉树的特点:
1.每个结点最多有两棵字树,所以二叉树中不存在度大于2的结点
2.二叉树是有序的,其次序不能任意颠倒,即使树中的某个结点只有一棵
字树,也要区分它是左子树还是右子树。
下面介绍几种特殊的二叉树:
1.斜树
所有结点都只有左子树的二叉树称为左斜树;所有结点都只有右子树的二叉树称为右斜树。是两棵不同的二叉树。如下示意图。
数据结构之二叉树递归操作
2.满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右字树,并且所有叶子结点都在同一层上,这样的二叉树称为满二叉树。如下示意图。
      数据结构之二叉树递归操作
3.完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。显然一棵满二叉树必定是一棵完全二叉树,完全二叉树的特点是:
1.如果有度为1的结点,只可能有一个,且该结点只有左孩子。
2.叶子结点只能出现在最下面两层,且最下层的叶子结点都集中在二叉树左侧连续的位置。
              数据结构之二叉树递归操作
以上图画的不是太优雅,大家不要介意哈。
关于二叉树的更多的性质,请读者查看*( 点击打开链接)或者其他资料。

编程语言 中能用多种方法来构造二叉树。常用的是顺序存储结构和二叉链表存储结构。
顺序存储结构:
叉树可以用 数组 或线性表来存储,而且如果这是 满二叉树 ,这种方法不会浪费空间。用这种紧凑排列,如果一个结点的索引为i ,它的子结点能在索引2i +1和2i +2找到,并且它的父节点(如果有)能在索引 floor((i-1)/2) 找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的 访问的局部性 ,特别是在前序遍历中。然而,它需要连续的 存储空间 ,这样在存储高度为 h n 个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1,而实际却只有h个结点,空间的浪费太大,这是顺序存储结构的一大缺点。
                                                                数据结构之二叉树递归操作
对于顺序存储结构,本文不作介绍,这种存储结构的缺点导致物理空间的浪费,是我们难以接受的。下面重点介绍二叉链表存储结构。

二叉链表存储结构:

在使用记录内存地址指针的编程语言中,二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2,一些子结点指针可能为空值,或者为特殊的哨兵结点。 使用链表能避免顺序储存浪费空间的问题,算法和结构相对简单,但使用二叉链表,由于缺乏父链的指引,在找回父节点时需要重新扫描树得知父节点的节点地址。

                     数据结构之二叉树递归操作

以上的存储结构示意图我想看的很清楚,这种结构减少了一定空间的浪费,但是这一定是最好的存储结构么,后续的文章会谈及线索二叉链表。
对于二叉链表最重要的操作莫过于遍历了,概括来说有递归和非递归两种,本文介绍的是递归遍历二叉树。

点击(此处)折叠或打开

  1. #include<iostream>
  2. using namespace std;
  3. typedef struct node
  4. {
  5.     struct node *leftChild;
  6.     struct node *rightChild;
  7.     char data;
  8. }BiTreeNode, *BiTree;

  9. void createBiTree(BiTree &);
  10. void PreOrderBiTree(BiTree *);
  11. void InOrderBiTree(BiTree *);
  12. void PostOrderBiTree(BiTree *);
  13. int BiTreeDeep(BiTree *);
  14. int LeafTreecount(BiTree *);

  15. void createBiTree(BiTree &T)
  16. {
  17.     char c;
  18.     cin >> c;
  19.     if ('#' == c)
  20.         T = NULL;
  21.     else
  22.     {
  23.         T = new BiTreeNode;
  24.         T->data = c;
  25.         createBiTree(T->leftChild);
  26.         createBiTree(T->rightChild);
  27.     }
  28. }

  29. void PreOrderBiTree(BiTree &T)
  30. {
  31.     if (== NULL)
  32.         return;
  33.     cout << T->data << " ";
  34.     PreOrderBiTree(T->leftChild);
  35.     PreOrderBiTree(T->rightChild);

  36. }
  37. void InOrderBiTree(BiTree &T) {

  38.     if (== NULL)
  39.         return;
  40.         InOrderBiTree(T->leftChild);
  41.         cout << T->data << " ";
  42.         InOrderBiTree(T->rightChild);
  43.     
  44. }
  45. void PostOrderBiTree(BiTree &T) {
  46.     if (== NULL)
  47.         return;
  48.     PostOrderBiTree(T->leftChild);
  49.     PostOrderBiTree(T->rightChild);
  50.     cout << T->data<<" ";
  51. }

  52. int BiTreeDeep(BiTree T)
  53. {
  54.     int deep = 0;
  55.     if (T)
  56.     {
  57.         int leftdeep = BiTreeDeep(T->leftChild);
  58.         int rightdeep = BiTreeDeep(T->rightChild);
  59.         deep = leftdeep >= rightdeep ? leftdeep + 1 : rightdeep + 1;
  60.     }
  61.     return deep;
  62. }

  63. //求二叉树叶子结点个数

  64. int LeafTreecount(BiTree T,int &num)
  65. { 
  66.     if (T)
  67.     {
  68.         if (T->leftChild == NULL &&T->rightChild == NULL)
  69.             num++;
  70.         LeafTreecount(T->leftChild,num);
  71.         LeafTreecount(T->rightChild,num);

  72.     }
  73.     return num;
  74. }
  75. void DeleteBiTree(BiTree T) {
  76.     if (== NULL)
  77.         return;
  78.     DeleteBiTree(T->leftChild);
  79.     DeleteBiTree(T->rightChild);
  80.     delete T;
  81.     
  82. }
  83. int main()
  84. {
  85. BiTree T;
  86. cout << "输入的字符是:" << endl;
  87. createBiTree(T);
  88. cout << "前序遍历:" << endl;
  89. PreOrderBiTree(T); \
  90. cout << endl;
  91. cout <<"中序遍历:"<< endl;
  92. InOrderBiTree(T);
  93. cout << endl;
  94. cout << "后序遍历:" << endl; \
  95. PostOrderBiTree(T);
  96. cout << endl;
  97. cout << "二叉树的高度为:" << BiTreeDeep(T) << endl;
  98. int num = 0;
  99. cout << "二叉树的叶子结点个数为:" << LeafTreecount(T, num)<< endl;
  100. DeleteBiTree(T);
  101. cout << "树已销毁!!!" << endl;
  102. return 0;
  103. }

运行结果如下:

数据结构之二叉树递归操作
一定要注意创建的二叉树时的方法,上面也是通过递归的方法创建二叉树,根据前中后序遍历,很容易画出这棵二叉树:(如下字母即指结点又指结点数据域)
                                               数据结构之二叉树递归操作
下面详细的介绍是如何进行递归遍历的,以上面构建的二叉树为例:
前序遍历:
调用PostOrderBiTree(BiTree &T),T根结点不为空,打印字符A
再调用PreOrderBiTree(T->leftChild),访问根结点的左孩子,不为NULL,打印字符B
再次调用PreOrderBiTree(T->leftChild),访问B结点的左孩子,不为空,打印C
再次调用PreOrderBiTree(T->leftChild),访问结点C的左孩子,因为C没有左孩子,T=NULL,返回函数。调用PreOrderBiTree(T->rightChild),C的右孩子也为空,此时返回到 上一级递归的函数,也就是打印B结点的函数;此时调用PreOrderBiTree(T->rightChild),B没有右孩子,为空,此时返回到上一级递归的函数,就是打印A结点的函数;此时调用PreOrderBiTree(T->rightChild),打印了D;调用PreOrderBiTree(T->leftChild),因为D没有左孩子,T=NULL,返回函数,调用了PreOrderBiTree(T->rightChild),D也没有右孩子,T=NULL,返回函数,到此前序遍历了整个二叉树。
中序遍历:
调用PostOrderBiTree(BiTree &T),T根结点不为空
调用PreOrderBiTree(T->leftChild),访问根结点的左孩子B,不为NULL
调用PreOrderBiTree(T->leftChild),访问B结点的左孩子C,不为NULL
调用PreOrderBiTree(T->leftChild),访问C结点的左孩子,由于C结点没有左孩子,所以T=NULL,返回函数;打印字符C,又调用PreOrderBiTree(T->rightChild),因为C没有右PreOrderBiTree(T->rightChild)孩子,所以返回到上级递归函数,打印字符B;调用PreOrderBiTree(T->rightChild),由于B没有右孩子,返回到上级递归函数;打印字符A,调用了PreOrderBiTree(T->rightChild),访问了根结点的右孩子D,不为空;然后调用了PreOrderBiTree(T->leftChild),因为D没有左孩子,返回函数;打印字符D,又调用PreOrderBiTree(T->rightChild),因为D没有右孩子,返回函数,到此中序遍历了整个二叉树。
后序遍历操作读者感兴趣可以自己完成,这里不作赘述,从上面的分析,整个过程不是太复杂,关键要理解递归的思想。
代码中也简单实现了打印二叉树的叶子结点个数,二叉树的高度,以及销毁一棵二叉树。如果明白了二叉树的创建和遍历,那么树的其他操作对于我们也不是难事。