数据结构题集(C语言版 清华大学出版社)

 1 // 35 顺序存储结构
 2 const int MAXSIZE = 20;
 3 typedef struct
 4 {
 5     Elemtype data[MAXSIZE+1]; // data[0]不存储元素，因为顺序存储结构二叉树的根节点从1开始层次遍历+1
 6     int length;
 7 }SqBiTree;
 8 void createSqBiTree(SqBiTree &st)
 9 {
10     Elemtype x;
11     int n;
12     cout << "n:";
13     cin >> n;
14     for  (int i = 0;i<n;i++)
15     {
16         cin>>x;
17         st.data[i+1] = x;
18     }
19     st.length = n;
20 }
21 void print(SqBiTree &st)
22 {
23     for (int i=1;i<=st.length;i++)
24         cout << st.data[i]<<‘ ‘;
25 }
26 // 求出下标志为I的结点对应的十进制整数
27 // 思路：parent = i/2,如果为偶数则为0，奇数则为1
28 int thirty_five(SqBiTree &st,int i)
29 {
30     int sum  =0;
31     int j = 0;
32     while (i)
33     {
34         if (i%2!=0)
35         {
36             sum += pow(2,j);
37         }
38         j++;
39         i = i/2;
40     }
41     return sum;
42 }
43 int main()
44 {
45     SqBiTree st ;
46     createSqBiTree(st);
47     cout << "i:";
48     int i;cin>>i;
49     cout << "十进制整数："<<thirty_five(st,i)<<endl;
50     return 0;
51 }

 1 // 36 判定两棵二叉树是否相似
 2 int similar(BiTree &t1,BiTree &t2)
 3 {
 4     if (t1==NULL && t2==NULL)
 5         return 1;
 6     if (t1!=NULL && t2!=NULL)
 7     {
 8         int l = similar(t1->lchild,t2->lchild);
 9         int r = similar(t1->rchild,t2->rchild);
10         return l&r;
11     }else
12     return 0;
13 }
14 int main()
15 {
16     BiTree t1,t2;
17     createBiTree(t1);
18     createBiTree(t2);
19     if (similar(t1,t2))
20         cout <<"similar!"<<endl;
21     else
22         cout <<"not similar!"<<endl;
23     return 0;
24 }

 1 // 39 增设双亲域和标志域时不用栈进行后序遍历的递推形式
 2 typedef struct NBiNode
 3 {
 4     Elemtype data;
 5     struct NBiNode *lchild,*rchild,*parent;
 6     int mark;// 0 1 2
 7 }NBiNode,*NBiTree;
 8 void createNBiTree(NBiTree &nt,NBiTree &parent)
 9 {
10     Elemtype x;
11     cin >> x;
12     if (x!=‘#‘)
13     {
14         nt = (NBiTree)malloc(sizeof(NBiTree));
15         nt->data = x;
16         nt->mark = 0;
17         nt->parent = parent;
18         createNBiTree(nt->lchild,nt);
19         createNBiTree(nt->rchild,nt);
20     }
21     else
22     {
23         nt = NULL;
24     }
25 }
26 /*
27 思路：
28 1. 从parent走到当前子树根节点，Mark为0，转为1
29 2. Mark为1时：转到左子树，设Mark为2
30 3. Mark为2时转到右子树，设Mark为0哦，访问结点
31 */
32 void postOrderUnWithPM(NBiTree &t)
33 {
34     NBiTree p = t;
35     while (p){
36        switch(p->mark)
37     {
38     case 0:
39         // 第一次访问P结点
40         p->mark  =1;
41         if (p->lchild)
42             p = p->lchild;
43         break;
44     case 1:
45         // 第二次访问P结点
46         p->mark = 2;
47         if (p->rchild)
48             p = p->rchild;
49         break;
50     case 2:
51         // 访问右结点结束后需要打印根节点
52         cout << p->data << ‘ ‘;
53         p->mark = 0;
54         p = p-> parent;
55         break;
56     }
57     }
58 
59 }
60 int main()
61 {
62     NBiTree nt;
63     NBiTree p;
64     p =NULL;
65     createNBiTree(nt,p);
66     postOrderUnWithPM(nt);
67 
68     return 0;
69 }

 1 // 40 只设双亲域不用栈如何中序遍历
 2 typedef struct NBiNode
 3 {
 4     Elemtype data;
 5     struct NBiNode *lchild,*rchild,*parent;
 6 }NBiNode,*NBiTree;
 7 void createNBiTree(NBiTree &nt,NBiTree &parent)
 8 {
 9     Elemtype x;
10     cin >> x;
11     if (x!=‘#‘)
12     {
13         nt = (NBiTree)malloc(sizeof(NBiTree));
14         nt->data = x;
15         nt->parent = parent;
16         createNBiTree(nt->lchild,nt);
17         createNBiTree(nt->rchild,nt);
18     }
19     else
20     {
21         nt = NULL;
22     }
23 }
24 
25 
26 void midOrder(NBiTree &nt)
27 {
28     NBiTree p = nt;
29     while (p)
30     {
31         if (p->lchild)
32         {
33             p = p->lchild;
34         }
35         else
36         {
37             cout << p->data <<‘ ‘; // 从左子树回到根节点，打印根节点；此时根据右子树是否为空进行判断
38             while (!p->rchild)
39             {//右子树为空，两种情况，1. 双亲的左子树：往上走，打印结点；2 双亲的右子树，不必打印
40                  while (p->parent && p->parent->rchild == p)
41                  {
42                      p = p->parent;
43                  }
44                  if (p->parent)
45                  {
46                      if (p->parent->lchild == p)
47                      {
48                          p = p->parent;
49                          cout << p->data << ‘ ‘; // 走到根节点又要判断右子树是否为空
50                      }
51                  }else
52                  {
53                      return ;// 右子树的双亲为空，那就是中序遍历完啦！
54                  }
55             }
56             // 右子树不为空，往右走
57             p = p->rchild;
58 
59         }
60     }
61 }
62 
63 int main()
64 {
65     NBiTree nt;
66     NBiTree p;
67     p =NULL;
68     createNBiTree(nt,p);
69     midOrder(nt);
70     return 0;
71 }

 1 // 45 
 2 // 递归，对于二叉树中的每一个元素值为X的结点，删去以他为根的子树，并释放相应空间
 3 // 递归清空子树
 4 void delete2(BiTree &t)
 5 {
 6     if (!t) return ;
 7     if (t->lchild)
 8         delete2(t->lchild);
 9     if (t->rchild)
10         delete2(t->rchild);
11     delete t;
12     t = NULL; // 
13 }
14 void deleteBiTree(BiTree &t,Elemtype x)
15 {
16     if (t)
17     {
18         if (t->data == x ) // string.h 和 string 这真的是两个头文件！
19             delete2(t);
20         else { // 如果删除了左右孩子就都没有了！★
21         deleteBiTree(t->lchild,x);
22         deleteBiTree(t->rchild,x);
23         }
24     }
25 }
26 
27 int main()
28 {
29     BiTree t;
30     createBiTree(t);
31     Elemtype x;
32     cout << "x:";
33     cin >> x;
34     deleteBiTree(t,x);
35     preOrder(t);
36     return 0;
37 }

 1 // 48 求两节点的共同祖先
 2 // 找到root到P的路径存到数组中
 3 // 思路：比较根节点和P指针是否相同，若相同返回1已找到；否则压入根节点，判断左右子树能否找到该结点并返回1
 4 // 如果左右子树均没有找到也就意味着该路径上没有P结点（走错路啦！）弹栈出根节点
 5 int findPath(BiTree &root,Elemtype &p,BiTree a[],int &top)
 6 {
 7     if (root->data == p )
 8         return 1; // 先比较根节点：相等则返回1，说明找到p,但此时路径数组为空，说明没有祖先
 9     a[++top] = root; // 根节点入栈
10     int has = 0;
11     if (root->lchild)
12         has = findPath(root->lchild,p,a,top);
13     if (has == 0 && root->rchild)
14         has = findPath(root->rchild,p,a,top);
15     if (has == 0)
16     {
17         top -- ;
18     }
19     return has;
20 }
21 
22 BiTree findGrandpa(BiTree &root,Elemtype p,Elemtype q)
23 {
24     int top1 = -1,top2 = -1; // TOP 指向a,b的顶层
25     // 存储两节点的路径到数组中，寻找相同的最靠右的部分
26     BiTree a[20]={};
27     BiTree b[20]={};
28     if (findPath(root,p,a,top1)!=0 && findPath(root,q,b,top2)!=0)
29     {
30         for (int i = top1;i>-1;i--)
31             for (int j = top2;j>-1;j--)
32             if (a[i]== b[j])
33                 return a[i];
34     }
35 }
36 int main()
37 {
38     BiTree t;
39     createBiTree(t);
40     Elemtype p,q;
41     cout <<"p,q:";
42     cin >> p >> q;
43     BiTree grand = findGrandpa(t,p,q);
44     cout << "grandpa : " << grand->data <<endl;
45     return 0;
46 }

 1 // 49 编写算法判定给定二叉树是否为完全二叉树
 2 /*
 3 1. 层次搜索
 4 2. 设一个布尔数组记录访问过的结点，检查数组中是否有false
 5 3. 递归算法：给出完全二叉树与原定义等价的递归定义，设计一个判别给定的二叉树是满二叉树、不满二叉树还是非完全二叉树的递归函数
 6 
 7 */
 8 const int Maxsize = 20;
 9 // 2. 检查数据中是否有false
10 bool isFull(BiTree &t)
11 {
12     BiTree  que[Maxsize];
13     int front = 0,rear = 0;
14     BiTree p;
15     Elemtype data[Maxsize] = {};
16     int i = 0;
17     if (t)
18     {
19         rear = (rear + 1)%Maxsize;
20         que[rear] = t;
21         data[i] = t->data;
22         while (front != rear)
23         {
24             front = (front+1)%Maxsize;
25             p = que[front];
26             if (p->lchild)
27             {
28                 rear = (rear+1)%Maxsize;
29                 que[rear]=p->lchild;
30                 data[++i] = p->lchild->data;
31             } // 有左子树则放入数据否则放入零
32             else
33                 data[++i] = 0;
34             if (p->rchild)
35             {
36                 rear = (rear+1)%Maxsize;
37                 que[rear]=p->rchild;
38                 data[++i] = p->rchild->data;
39             }
40             else
41                 data[++i] = 0;
42 
43         }
44         for (int j = 1;j<i;j++)
45     { // 检查是否有字母夹着单个0的情况，因为最后也都是0
46         if (data[j-1]!=0 && data[j+1]!=0 && data[j] == 0)
47             return false;
48     }
49     }
50     return true;
51 }
52 
53 // 用一个数组记录遍历过得结点序号，看是否连续
54 bool isFull2(BiTree &t)
55 {
56     int i=0,j=0;
57     BiTree que[Maxsize] = {}; // front
58     int order[Maxsize] = {}; // j i
59     BiTree p;
60     int front = 0,rear = 0;
61     if (t)
62     {
63         que[++rear] = t;
64         order[++i] = ++j; // order[1] = 1 根节点序号
65         while (front != rear)
66         {
67             p = que[++front];
68             if (order[i]!= order[i-1]+1) // 结点序号不连续
69                 return false;
70             if (p->lchild)
71             {
72                 que[++rear] = p->lchild;
73                 order[++i] = 2*p->data;
74             }
75             if (p->rchild)
76             {
77                 que[++rear] = p->rchild;
78                 order[++i] = 2*p->data+1;
79             }
80         }
81         return 1 ;
82     }
83 }
84 int main()
85 {
86     BiTree t;
87     createBiTree(t);
88     cout << isFull2(t)<< endl;
89     return 0;
90 }

  1 // 50
  2 /*
  3 1. 三元组序列 (F, C, L/R)
  4 2. ^代表根节点的双亲
  5 3. ^^代表输入终点
  6 4. 层次表示输入
  7 */
  8 BiTree three()
  9 {
 10     Elemtype thr[3];
 11     BiTree que[Maxsize];
 12     int front = 0,rear =0;
 13     BiTree t,p,q;
 14     cin >> thr[0] >>thr[1] >> thr[2];
 15     while (thr[0]!=‘^‘ || thr[1]!=‘^‘)
 16     {
 17         if (thr[0] == ‘^‘ )
 18         {
 19             t = (BiTree )malloc(sizeof(BiTree));
 20             t->data = thr[1];
 21             t->lchild = NULL;
 22             t->rchild = NULL;
 23             que[++rear] = t; // 根节点入队
 24             p = t;
 25             front = 1;
 26         }
 27         else
 28         {
 29             if (thr[2] == ‘L‘)
 30             {
 31                 p->lchild = q;
 32             }
 33             if (thr[2]==‘R‘)
 34             {
 35                 p->rchild = q;
 36             }
 37         }
 38 
 39         cin >> thr[0] >> thr[1] >> thr[2];
 40         q = (BiTree)malloc(sizeof(BiTree));
 41         q->data = thr[1];
 42         q->lchild  = NULL;
 43         q->rchild = NULL;
 44         que[++rear] = q;
 45         // 每输入一组，便把数据入队
 46         if (thr[0] != p->data)
 47         {
 48             // 出队
 49             p = que[++front];
 50         }
 51 
 52     }
 53     return t;
 54 }
 55 int main()
 56 {
 57     BiTree t;
 58     t = three();
 59     preOrder(t);
 60 
 61     return 0;
 62 }
 63 //51 输出以二叉树表示的算数表达式，如果右括号在输出时应添上
 64 bool isOperator(Elemtype c)
 65 {
 66     if (c==‘+‘ || c==‘-‘ || c==‘*‘ || c==‘/‘)
 67         return true;
 68     else
 69         return false;
 70 }
 71 bool lowPrior(Elemtype a,Elemtype b)
 72 {
 73     if ((a == ‘+‘ || a == ‘-‘)&&(b==‘*‘ || b == ‘/‘))
 74         return true;
 75     else
 76         return false;
 77 }
 78 void biao(BiTree &t)
 79 {
 80     if (t)
 81     {
 82         if (t->lchild)
 83         {
 84             if (isOperator(t->lchild->data) && lowPrior(t->lchild->data,t->data))
 85             {
 86                 // 如果左孩子是操作符并且优先级低于根节点
 87                 cout << ‘(‘ << ‘ ‘;
 88                 biao(t->lchild);
 89                 cout <<‘)‘ << ‘ ‘;
 90             }
 91             else
 92                 biao(t->lchild);
 93         }
 94 
 95         cout << t->data << ‘ ‘;
 96 
 97         if (t->rchild)
 98         {
 99             if (isOperator(t->rchild->data) && lowPrior(t->rchild->data,t->data))
100             {
101                 // 如果左孩子是操作符并且优先级低于根节点
102                 cout << ‘(‘ << ‘ ‘;
103                 biao(t->rchild);
104                 cout <<‘)‘ << ‘ ‘;
105             }
106             else
107                 biao(t->rchild);
108         }
109     }
110 }
111 
112 int main()
113 {
114     BiTree t;
115     createBiTree(t);
116     preOrder(t);
117     // biao(t);
118 
119     return 0;
120 }
121 // 52 一棵二叉树的繁茂度定义为各层节点数的最大值与树的高度的乘积
122 
123 int fanmao(BiTree &t)
124 {
125     int level,v,i,j;
126     float f;
127     int maxrow,maxcol ; // 最大行和最大列
128     BiTree que[Maxsize] =  {}; // 队列
129     int order[Maxsize] = {};// 存放各节点序号
130     int count[Maxsize] ={};//下标代表层，数组内容为各层结点个数
131     v = 0;i = 0;j = 0;maxcol = 0;maxrow = 0;
132     if (t)
133     {
134         que[j] = t;
135         order[j] = 1;
136         j ++ ;
137         while (i<j)
138         {
139             f = log(order[i])/log(2) ;
140         // 将 x 的自然对数值除以 n 的自然对数值，就可以对任意底 n 来计算数值 x 的对数值：Logn(x) = Log(x) / Log(n)
141             level = (int)f +1 ;// 当前i节点的层数
142             if (maxrow < level)
143                 maxrow = level;
144             count[level] ++;
145             // 求出每个节点当前层数，使当前层数的数据++
146             if (maxcol <count[level])
147                 maxcol = count[level];
148 
149             if (que[i]->lchild)
150             {
151                 que[j] = que[i]->lchild;
152                 order[j] = 2*order[i] ;// i是双亲节点，j是子节点
153                 j++;
154             }
155             if (que[i]->rchild)
156             {
157                 que[j] = que[i]->rchild;
158                 order[j] = 2*order[i]+1;
159                 j++;
160             }
161             i++;
162         }
163     }
164     v = maxcol * maxrow;
165     return v;
166 }
167 int main()
168 {
169     BiTree t;
170     createBiTree(t);
171     cout << fanmao(t);
172 
173 
174     return 0;
175 }