首页 > 其他 > 详细

数据结构——构造二叉树的方法汇总(递归与迭代构造)

时间:2020-05-21 21:01:17      阅读:78      评论:0      收藏:0      [点我收藏+]

序言

一、根据前序序列构造

1.1 控制台递归构造

1.2 字符串递归构造

1.3 字符串迭代构造

二、根据前(后)序序列和中序序列构造

2.1 字符串递归构造

2.2 字符串迭代构造

三、总结

四、参考文献

 

 

 

序言

  本篇文章将介绍二叉树的常见构造方法,总体涵盖控制台输入字符串构造和根据字符串构造,两者构造的区别是,前者构造序列需要从控制台输入,后者构造序列可以通过现有字符串直接构造;并且通过递归与迭代两种思路进行构造,我们将先通过递归进行构造,然后将递归转化为迭代,如果不知道如何将递归转化为迭代,请参看文章数据结构——递归与非递归

 

 

一、根据前序序列构造

  假设有如下一颗二叉树:

技术分享图片

 

 

   我们可以根据图示二叉树写出他的前序序列为:ABDC。如果反过来,已知前序序列ABDC,我们能不能根据前序序列画出二叉树呢,答案是不能。我们可以将二叉树稍微改造一下,用#代表空结点,改造结果如下所示:

技术分享图片

 

 

 我们写出改造后的二叉树的前序序列:AB#D##C##。现在我们就可以根据改造后的二叉树前序序列唯一地构造二叉树了。

 

1.1 控制台递归构造

  控制台递归构造,就是将前序序列通过控制台输入的方式逐一录入,然后将录入的前序序列通过递归进行构造。我们将二叉树采用二叉链表的方式进行存储,即结点包含三部分,数据域,左孩子和右孩子。如下图所示:

技术分享图片

 

 

 

给出二叉树结点的定义,代码如下:

1 /* 二叉树结点 */
2 template <typename DataType>
3 struct BiNode
4 {
5     DataType data;
6     BiNode<DataType>* lChild;
7     BiNode<DataType>* rChild;
8 };

 

我们给出二叉树的定义,代码如下:

 1 template <typename DataType>
 2 class BiTree
 3 {
 4 public:
 5     BiTree() { root = create(); }  // 构造函数
 6     ~BiTree();   // 析构函数
 7 private:
 8     BiNode<DataType>* create();    // 控制台递归构造二叉树
 9     BiNode<DataType>* root;        // 二叉树根结点
10 };    

 

接下来我们实现控制台递归构造二叉树的方法 BiNode<DataType>* create();代码如下:

 1 template <typename DataType>
 2 BiNode<DataType>* BiTree<DataType>::create()
 3 {
 4     BiNode<DataType>* bt;
 5     char ch;
 6     std::cin >> ch;  // 控制台录入
 7     if (# == ch)
 8     {
 9         bt = nullptr;
10     }
11     else
12     {
13         bt = new BiNode<DataType>;
14         bt->data = ch;
15         bt->lChild = create();    // 递归构造左子树
16         bt->rChild = create();    // 递归构造右子树
17     }
18     return bt;
19 }

 

 

1.2 字符串递归构造

字符串递归构造,就是传入一个字符串前序序列作为参数,然后进行递归构造二叉树。我们依旧采用二叉链表的方式,本文二叉树的存储结构我们一直采用二叉链表的方式。

修改二叉树的定义如下:

 1 template <typename DataType>
 2 class BiTree
 3 {
 4 public:
 5     BiTree() { root = create(); }
 6     BiTree(std::string tree, int index) { root = create(tree, index); }
 7     ~BiTree();
 8 private:
 9     BiNode<DataType>* create();  
10     BiNode<DataType>* create(std::string tree, int& index);
11     BiNode<DataType>* root;  // 二叉树根节点
12 };  

 

接下来我们实现字符串递归构造二叉树的方法 BiNode<DataType>* create(std::string tree, int& index);代码如下:

 1 template <typename DataType>
 2 BiNode<DataType>* BiTree<DataType>::create(std::string tree, int& index)
 3 {
 4     BiNode<DataType>* bt;
 5     char ch;
 6     ch = tree[index];
 7     if (# == ch)
 8     {
 9         bt = nullptr;
10     }
11     else
12     {
13         bt = new BiNode<DataType>;
14         bt->data = ch;
15         bt->lChild = create(tree, ++index);
16         bt->rChild = create(tree, ++index);
17     }
18     return bt;
19 }

 

 

1.3 字符串迭代构造

我们将字符串递归构造改写成字符串迭代构造。

修改二叉树定义, 代码如下:

 1 template <typename DataType>
 2 class BiTree
 3 {
 4 public:
 5     BiTree() { root = create(); }
 6     BiTree(std::string tree, int index) { root = create(tree, index); }
 7     BiTree(std::string tree) { createIter(tree, 0); }
 8     ~BiTree();
 9 private:
10     BiNode<DataType>* create();
11     BiNode<DataType>* create(std::string tree, int& index);
12     void createIter(std::string tree, int index);
13     BiNode<DataType>* root;
14 };

 

接下来我们实现字符串迭代构造二叉树的方法 void createIter(std::string tree, int index);代码如下:

 1 template <typename DataType>
 2 void BiTree<DataType>::createIter(std::string tree, int index)
 3 {
 4     root = new BiNode<DataType>;
 5     root->data = *;
 6     BiNode<DataType>* bt = root;
 7     BiNode<DataType>* stack[20];
 8     int top = -1;    // 栈顶指针
 9 
10     while (# != tree[index] || -1 != top)
11     {
12         while (# != tree[index])
13         {
14             if (bt == nullptr || * != bt->data)
15             {
16                 bt = new BiNode<DataType>;
17             }
18             bt->data = tree[index];
19             stack[++top] = bt;  // 保存现场
20             ++index;            // 修改局部变量
21             if (# == tree[index])
22             {
23                 bt->lChild = nullptr;
24             }
25             else {
26                 bt->lChild = new BiNode<DataType>;
27                 bt = bt->lChild;
28                 bt->data = *;
29             }
30         }
31 
32         bt = stack[top--];        // 恢复现场
33         ++index;                // 修改局部变量
34         if (# != tree[index])
35         {
36             bt->rChild = new BiNode<DataType>;
37             bt = bt->rChild;
38             bt->data = *;
39         }
40         else
41         {
42             bt->rChild = nullptr;
43         }
44     }
45 }

 

 

二、根据前(后)序序列和中序序列构造

  我们可以根据前序序列和中序序列唯一地确定二叉树,确定方法请参考文献2

2.1 字符串递归构造

修改二叉树定义, 代码如下:

 1 template <typename DataType>
 2 class BiTree
 3 {
 4 public:
 5     BiTree() { root = create(); }
 6     BiTree(std::string tree, int index) { root = create(tree, index); }
 7     BiTree(std::string tree) { createIter(tree, 0); }
 8     BiTree(std::string preOrder, std::string inOrder, int n) { root = create(preOrder, inOrder, n); }
 9     ~BiTree();
10 private:
11     BiNode<DataType>* create();
12     BiNode<DataType>* create(std::string tree, int& index);
13     void createIter(std::string tree, int index);
14     BiNode<DataType>* create(std::string preOrder, std::string inOrder, int length);
15 
16     BiNode<DataType>* root;
17 };

 

接下来我们实现字符串递归构造二叉树的方法BiNode<DataType>* create(std::string preOrder, std::string inOrder, int length);代码如下:

 1 template <typename DataType>
 2 BiNode<DataType>* BiTree<DataType>::create(std::string preOrder, std::string inOrder, int n)
 3 {
 4     BiNode<DataType>* bt;
 5 
 6     if (0 == n)
 7     {
 8         bt = nullptr;
 9     }
10     else
11     {
12         bt = new BiNode<DataType>;
13         bt->data = preOrder[0];
14         int n = inOrder.find(preOrder[0], 0);
15         std::string lPreOrder = preOrder.substr(1, n);
16         std::string lInOrder = inOrder.substr(0, n);
17         std::string rPreOrder = preOrder.substr(n + 1, preOrder.size() - 1 - n);
18         std::string rInOrder = inOrder.substr(n + 1, inOrder.size() - 1 - n);
19         bt->lChild = create(lPreOrder, lInOrder, n);
20         bt->rChild = create(rPreOrder, rInOrder, inOrder.size() - 1 - n);
21     }
22 
23     return bt;
24 }

 

 

2.2 字符串迭代构造

 

 

三、总结

 

 

四、参考文献

1、[二叉树地建立方法总结](https://www.cnblogs.com/llhthinker/p/4906631.html)

2、数据结构——从概念到C++实现(第三版) 王红梅、王慧、王新颖 编著

 

数据结构——构造二叉树的方法汇总(递归与迭代构造)

原文:https://www.cnblogs.com/balalawy/p/12933009.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!