数据结构第五章学习小结

第五章学了一个新的数据结构—树，其中运用比较广泛的应该是二叉树，二叉树和前面几种数据结构一样，有顺序存储和链式存储两种：

顺序存储：

1 #define MAXSIZE 100 //二叉树的最大结点数

2 typedef TElemType SqBiTree[MAXSIZE]; //0号单元存储根结点

链式存储：

1 typedef struct BiTNode
2 {
3     TElemType data;     //结点数据域 
4     struct BiTNode *lchild,*rchild;  //指向左右孩子的指针 
5 }BiTNode,*BiTree;

二叉树的基本操作有遍历和创建二叉树：

1.遍历和赋值都有四种，分为：先序，中序，后序，层次

先序：根节点->左子树->右子树

中序：左子树->根节点->右子树

后序：左子树->右子树->根节点

层次：从上到下，从左到右

（1）中序遍历（分为递归和非递归两种）：

递归算法：

1 void InOrder(BiTree T)
2 {//中序遍历二叉树T的递归算法 
3     if(T)
4     {
5         InOrder(T->lchild);
6         cout << T -> data;
7         InOrder(T->rchild);
8     } 
9 }//改变输出语句的顺序，就可以实现先序和后序的递归算法

非递归算法：

 1 void InOrder(BiTree T)
 2 {//中序遍历二叉树T的非递归算法
 3     InitStack(S);
 4     BiTNode *p = T;
 5     BiTNode *q = new BiTNode;
 6     while(p||!StackEmpty(S))
 7     {
 8         if(p)
 9         {
10             Push(S,p);
11             p = p -> lchild;
12         }
13         else
14         {
15             Pop(S,q);
16             cout << q -> data;
17             p = q -> rchild;
18         }
19     }
20 }

（2）创建二叉树：

也有四种：先序，中序，后序，层次

 1 void create(BiTree &T)
 2 {//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T 
 3     char ch;
 4     cin >> ch;
 5     if(ch=='#') T = NULL;
 6     else
 7     {
 8         T = new BiTNode;
 9         T -> data = ch;
10         create(T->lchild);
11         create(T->rchild);
12     }
13 }//改变输入语句的顺序，就可以实现先序和后序的递归算法

PTA作业的编程题就是运用了遍历和创建，代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef struct BiTNode
 5 {
 6     char data; 
 7     struct BiTNode *lchild,*rchild;
 8 }BiTNode,*BiTree;
 9 
10 void create(BiTree &T)
11 {//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T 
12     char ch;
13     cin >> ch;
14     if(ch=='#') T = NULL;
15     else
16     {
17         T = new BiTNode;
18         T -> data = ch;
19         create(T->lchild);
20         create(T->rchild);
21     }
22 }
23 
24 void InOrder(BiTree T)
25 {//中序遍历二叉树T的递归算法 
26     if(T)
27     {
28         InOrder(T->lchild);
29         cout << T -> data;
30         InOrder(T->rchild);
31     } 
32 }
33 
34 /*
35 void InOrder(BiTree T)
36 {////中序遍历二叉树T的非递归算法
37     InitStack(S);
38     BiTNode *p = T;
39     BiTNode *q = new BiTNode;
40     while(p||!StackEmpty(S))
41     {
42         if(p)
43         {
44             Push(S,p);
45             p = p -> lchild;
46         }
47         else
48         {
49             Pop(S,q);
50             cout << q -> data;
51             p = q -> rchild;
52         }
53     }
54 }
55 */
56 
57 int CountLeaves(BiTree T)
58 {//统计T指向的二叉树的叶子节点个数 
59     if(T==NULL)  return 0;
60     
61     if(T->lchild==NULL&&T->rchild==NULL)
62     {
63         return 1;
64     }
65 
66     return CountLeaves(T->lchild) + CountLeaves(T->rchild); 
67 }
68 
69 void Destory(BiTree T)
70 {
71     if(T==NULL) return;
72     
73     Destory(T->lchild);  //释放左子树的空间 
74     Destory(T->rchild);  //释放右子树的空间 
75     
76     delete T;   //释放根节点 
77 }
78 
79 int main()
80 {
81     BiTree T = NULL;
82     create(T);
83     InOrder(T);
84     cout <<endl;
85     cout << CountLeaves(T) <<endl;
86     Destory(T);
87     return 0;
88 }

还学了哈夫曼算法，这种算法用于算最优二叉树很方便，并且哈夫曼树有一个很显著的特点:权值越大的结点离根结点越近，他的KMP也是最小的。

我当时学的时候有些没学懂，所以我看了两次老师的视频后自己去找了资料，如果大家还是有些不明白的话，可以去看看这篇博客，我觉得讲的很清楚，而且很好理解https://blog.csdn.net/dongfei2033/article/details/80657360

PTA上的实践题：

  1 7-1 名单叶子 （20 分）
  2 给定一棵树，您应该按照从上到下，从左到右的顺序列出所有叶子。
  3 
  4 输入规格：
  5 每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数? (≤10），即树中节点的总数-因此，节点的编号从0到 N ? 1。然后?后面紧跟着几行，每行对应一个节点，并给出该节点左右子节点的索引。如果孩子不存在，将在该位置放置“-”。任何一对孩子都用空格隔开。
  6 
  7 输出规格：
  8 对于每个测试用例，按从上到下，从左到右的顺序在一行中打印所有叶子的索引。相邻数字之间必须恰好有一个空格，行尾不得有多余的空格。
  9 
 10 输入样例：
 11 8
 12 1 -
 13 - -
 14 0 -
 15 2 7
 16 - -
 17 - -
 18 5 -
 19 4 6
 20 样本输出：
 21 4 1 5
 22 */
 23 #include <iostream>
 24 #include <queue>
 25 using namespace std;
 26 
 27 typedef struct 
 28 {
 29     int lch;
 30     int rch;
 31 }Node;
 32 
 33 typedef struct
 34 {
 35     Node data[10];
 36     int root;  //根节点编号 
 37 }Tree;
 38 
 39 void Create(Tree &T)
 40 {//读入数据，同时找出根节点
 41     int n,i;
 42     cin >> n;
 43     bool check[10] = {false};
 44     char a,b;
 45     for(i=0;i<n;i++)
 46     {
 47         cin >> a >> b;
 48         if(a=='-')
 49         {
 50             T.data[i].lch = -1;
 51         }
 52         else
 53         {
 54             T.data[i].lch = a-'0';
 55             check[a-'0'] = true;
 56         }
 57         
 58         if(b=='-')
 59         {
 60             T.data[i].rch = -1;
 61         }
 62         else
 63         {
 64             T.data[i].rch = b-'0';
 65             check[b-'0'] = true;
 66         }
 67     }
 68     
 69     //找出根节点,写入T.root
 70     for(i=0;i<n;i++)
 71     {
 72         if(check[i]==false)
 73         {
 74             T.root = i;
 75             break;
 76         }    
 77     } 
 78 }
 79 
 80 void LevelOrder(Tree T)
 81 {
 82     queue<int> Q;
 83     Q.push(T.root);  //根结点入队
 84     
 85     int k;
 86     bool flag = false;
 87     while(!Q.empty())
 88     {
 89         k = Q.front();  //获取队头元素的值，给k 
 90         Q.pop();  //对头元素出队
 91         if(T.data[k].lch==-1&&T.data[k].rch==-1)
 92         {
 93             if(flag==false)
 94             {
 95                 cout << k;
 96                 flag = true;    
 97             }
 98             else
 99             {
100                 cout << " " << k;    
101             }    
102         }
103         else
104         {
105             if(T.data[k].lch!=-1)
106             {
107                 Q.push(T.data[k].lch);
108             }
109             if(T.data[k].rch!=-1)
110             {
111                 Q.push(T.data[k].rch);
112             }
113          } 
114          
115     } 
116 }
117 
118 int main()
119 {
120     Tree T;
121     Create(T); //读入数据，同时找出根节点
122     cout << T.root <<endl;
123     LevelOrder(T);
124     return 0; 
125      
126 }
这道题难在找根结点，老师讲的方法很巧妙，在输入的时候就已经开始对每个结点进行标记了，最后的时候再根据结点的特点找出根结点

 1 7-2 树的同构 (20分)
 2 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。
 3 例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
 4 现给定两棵树，请你判断它们是否是同构的。
 5 */
 6 
 7 #include <iostream>
 8 using namespace std;
 9 
10 struct Tree
11 {
12     char element;
13     int lch;
14     int rch;
15 }t1[11], t2[11];
16 
17 int Create(Tree T[])
18 {//读入数据，同时找出根节点
19     int n,i;
20     cin >> n;
21     bool check[10] = {false};
22     char a,b;
23     for(i=0;i<n;i++)
24     {
25         cin >> T[i].element >> a >> b;
26         if(a=='-')
27         {
28             T[i].lch = -1;
29         }
30         else
31         {
32             T[i].lch = a-'0';
33             check[a-'0'] = true;
34         }
35         
36         if(b=='-')
37         {
38             T[i].rch = -1;
39         }
40         else
41         {
42             T[i].rch = b-'0';
43             check[b-'0'] = true;
44         }
45     }
46     
47     //找出根节点,写入T.root
48     for(i=0;i<n;i++)
49     {
50         if(check[i]==false)
51         {
52             return i;
53         }    
54     } 
55     return -1;
56 }
57 
58 
59 bool isomorphic(int r1, int r2) {
60     if (r1 == -1&&r2 == -1)
61         return true;
62     if (r1 != -1&&r2 == -1)
63         return false;
64     if (r2 != -1&&r1 == -1)
65         return false;
66     if (t1[r1].element != t2[r2].element)
67         return false;
68     return (isomorphic(t1[r1].lch, t2[r2].lch) && isomorphic(t1[r1].rch, t2[r2].rch))||(isomorphic(t1[r1].lch, t2[r2].rch) && isomorphic(t1[r1].rch, t2[r2].lch));
69 }
70 
71 
72 
73 int main() {
74  
75     int r1, r2;
76 
77     r1=Create(t1);
78     r2=Create(t2);
79     if(isomorphic(r1, r2))
80         cout << "Yes";
81     else
82         cout << "No";
83     return 0;
84 }

这道题我开始一直在报错，后来找了很久，发现是一个小地方错了，

 1 17 int Create(Tree T[])
 2 18 {//读入数据，同时找出根节点
 3 19     int n,i;
 4 20     cin >> n;
 5 21     bool check[10] = {false};
 6 22     char a,b;
 7 23     for(i=0;i<n;i++)
 8 24     {
 9 25         cin >> T[i].element >> a >> b;
10 26         if(a=='-')
11 27         {
12 28             T[i].lch = -1;
13 29         }
14 30         else
15 31         {
16 32             T[i].lch = a-'0';
17 33             check[a-'0'] = true;
18 34         }
19 35         
20 36         if(b=='-')
21 37         {
22 38             T[i].rch = -1;
23 39         }
24 40         else
25 41         {
26 42             T[i].rch = b-'0';
27 43             check[b-'0'] = true;
28 44         }
29 45     }
30 46     
31 47     //找出根节点,写入T.root
32 48     for(i=0;i<n;i++)
33 49     {
34 50         if(check[i]==false)
35 51         {
36 52             return i;
37 53         }    
38 54     } 
39 55     return -1;
40 56 }

这里有可能是个空表，所以要另外给它返回值

这一章的内容比较有趣，也有些内容比较难理解，但是查了博客后就会好理解很多，真的很推荐大家在理解不了一些内容的时候可以去看看别人写的博客，有的时候说不定看了之后就会茅塞顿开。

感觉自己有时候很粗心，很不应该犯的错误经常会犯，希望以后的学习可以细心一点，多打一些代码，从中反思总结出对自己有益的知识。