数据结构-实验二

二叉树的操作与实现

1、二叉树的基本操作算法实现

(1) 利用(广义表)二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树 的二叉链式存储结构;(请勿根据扩展二叉树进行创建)

(2) 输出该二叉树(中序遍历序列);

(3) 输出‘H’结点的左、右孩子结点值;

(4) 输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

typedef struct Tree {// 定义一个二叉树
char data;
struct Tree* leftchild, * rightchild;
}tree,*treenode;

typedef struct Stack {// 定义一个栈
tree* data;
struct Stack* next;
}stack,*stacknode;

stacknode createstack() {
stacknode root = new stack;
root->data = NULL;
root->next = NULL;
return root;
}

void addstack(stacknode root, tree* data) {
stack* node = new stack;
node->data = data;
node->next = root->next;
root->next = node;
}

tree* popstack(stacknode& root) {
if (root->next == NULL) {
return NULL;
}else {
stack* node = root->next;
root->next = node->next;
tree* data = node->data;
delete node;
return data;
}
}

tree* topstack(stacknode& root) {
if (root->next == NULL) {
return NULL;
}
else {
stack* node = root->next;
return node->data;
}
}

bool empty(stacknode root) {
if (root->next == NULL) {
return true;
}
return false;
}

void createTree(treenode &root,string& stringdata) {// 创建二叉树
stacknode stackroot = createstack();
tree* current = NULL;
bool isleft = true;// 在这里判断,如果是true,就把新的节点加到左子树上去,如果是false的话,就把这个加到右子树上去
for (char it : stringdata) {// 如果是(的话,就是(前面的入栈,(后面的作为其左子树,","后面的就作为他的右子树
if (it == '(') {
addstack(stackroot, current);
isleft = true;
continue;
}
else if (it == ')') {
popstack(stackroot);
}
else if (it == ',') {
isleft = false;
}
else {
treenode node = new tree;
node->data = it;
node->leftchild = NULL;
node->rightchild = NULL;
if (empty(stackroot)) {
root = node;
}else {
tree* parent = topstack(stackroot);
if (isleft) {
parent->leftchild = node;
}
else {
parent->rightchild = node;
}
}
current = node;
}
}
}

void inorder(treenode& root) {// 中序遍历
if (root == NULL) {
return;
}
else {
inorder(root->leftchild);
cout << root->data << "---";
inorder(root->rightchild);
}
}

int returnlength(treenode root) { // 返回二叉树的高度
return root == NULL ? 0 : max(returnlength(root->leftchild),returnlength(root->rightchild)) + 1;
}

int returngeshu(treenode root) { // 返回二叉树节点的个数
return root == NULL ? 0 : returngeshu(root->leftchild) + returngeshu(root->rightchild) + 1;
}

int returnyezishu(treenode root) { // 返回叶子数目
if (root == NULL) {
return 0;
}
if (root->leftchild == NULL && root->rightchild == NULL)return 1;
return returnyezishu(root->leftchild) + returnyezishu(root->rightchild);
}

void printChildren(treenode root, char target) {// 输出任意结点的左右孩子结点值
if (root == NULL) {
return;
}
if (root->data == target) {
cout << "结点 " << target << " 的孩子: ";
if (root->leftchild) {
cout << "左孩子: " << root->leftchild->data << " ";
}else {
cout << "左孩子: NULL ";
}
if (root->rightchild) {
cout << "右孩子: " << root->rightchild->data << endl;
}else {
cout << "右孩子: NULL" << endl;
}
return;
}
printChildren(root->leftchild, target);
printChildren(root->rightchild, target);
}

int maxDegree(treenode root) {// 二叉树的度 // 直接利用上面的那两个叶子节点和总的节点来求
return (returngeshu(root) - returnyezishu(root)) * 2 + returnyezishu(root);
}

int main() {
cout << "请输入二叉树的广义表的表示形式:" << endl;
string stringdata;
cin >> stringdata;
treenode root;
createTree(root, stringdata);
inorder(root);// 中序遍历二叉树
cout << "输入任意结点,我会返回他的的左、右孩子结点值" << endl;
char target;
cin >> target;
printChildren(root, target);
cout << "这个二叉树的节点个数为:" << returngeshu(root) << endl;
cout << "这个二叉树的叶子节点个数为:" << returnyezishu(root) << endl;
cout << "这个二叉树的高度为:" << returnlength(root) << endl;
cout << "这个二叉树的度为:" << maxDegree(root) << endl;
return 0;
}
2.参考数据:
1
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
3.参考结果:
1
2
3
4
5
6
7
8
9
请输入二叉树的广义表的表示形式:
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
D---B---J---H---L---K---M---N---E---A---F---C---G---I---输入任意结点,我会返回他的的左、右孩子结点值
N
结点 N 的孩子: 左孩子: NULL 右孩子: NULL
这个二叉树的节点个数为:14
这个二叉树的叶子节点个数为:6
这个二叉树的高度为:7
这个二叉树的度为:22

2、二叉树的各种遍历算法实现

实现上述二叉树的先序、中序和后序遍历的递归和非递归算法。

1.先序,中序的非递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct Tree {
char data;// 数据
struct Tree* leftchild;// 左子树
struct Tree* rightchild;// 右子树
}tree, * treelist;
// 栈的创建
typedef struct stacknode {
tree* data;
struct stacknode* next;
}node, * stack;
// 二叉树的创建
void createTree(treelist& app) {
char ch;
cin >> ch;
if (ch == '#') {
app = NULL;
}
else {
app = new Tree;
app->data = ch;
createTree(app->leftchild);
createTree(app->rightchild);
}
}
// 初始化栈
void initstack(stack root) {
root->data = NULL;
root->next = NULL;
}
// 在栈中加入一些数据
void pushstack(stack root, tree* app) {
node* stackapp = (node*)malloc(sizeof(node));
stackapp->data = app;
stackapp->next = root->next;
root->next = stackapp;
}
// 判断栈是否为空
bool isempty(stack root) {
if (root->next == NULL) {
return true;
}
else {
return false;
}
}
// 将栈中的数据拿出来
node* popstack(stack root) {
if (isempty(root)) {
return NULL;
}
else {
node* app = root->next;
root->next = app->next;
return app;
}
}
// 先序遍历
// 基本思想很简单
void preorder(treelist app) {
treelist APP = app;
stack stackAPP = new node;
initstack(stackAPP);
while (APP || !isempty(stackAPP)) {
if (APP) {
cout << APP->data << "---";
pushstack(stackAPP, APP);
APP = APP->leftchild;
}
else {
APP = popstack(stackAPP)->data;
APP = APP->rightchild;
}
}
}
// 中序遍历
// 基本思想就是到左子树遍历到null的时候就出栈,打印出数据,只要为空就打印出栈中的数据
void inorder(treelist app) {
treelist APP = app;
stack stackAPP = new node;
initstack(stackAPP);
while (APP || !isempty(stackAPP)) {
if (APP) {
pushstack(stackAPP, APP);
APP = APP->leftchild;
}
else {
APP = popstack(stackAPP)->data;
cout << APP->data << "---";
APP = APP->rightchild;
}
}
}
int main() {
treelist app;
cout << "请输入二叉树的数据" << endl;
createTree(app);
cout << "先序遍历:";
preorder(app);
cout << "end" << endl;
cout << "中序遍历:";
inorder(app);
cout << "end" << endl;
return 0;
}

就是借用了栈的用法,先序遍历就是先把左边的输出出来,同时伴随着入栈操作,到后面左子树为空的时候就出栈搞右子树的内容输出出来,右子树空了就再出栈…….;

中序遍历: 基本思想就是到左子树遍历到null的时候就出栈,打印出数据,只要为空就打印出栈中的数据

2.后序遍历的非递归的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
using namespace std;

// 定义二叉树
typedef struct tree {
char data;
struct tree* lefttree, * righttree;
bool flage;
};
// 定义一个栈
typedef struct stack {
tree* data;
struct stack* next;
}*stacknode;
// 创建一个二叉树
void createtree(tree*& app) {
char data;
cin >> data;
if (data == '#') {
app = NULL;
}
else {
app = new tree;
app -> data = data;
app->flage = false;
createtree(app->lefttree);
createtree(app->righttree);
}
}
// 初始化一个栈
void initstack(stacknode &app) {
app->data = NULL;
app->next = NULL;
}
// 给栈加入一个数据到栈里面去
void addstack(stacknode& app, tree* data) {
stacknode node = new stack;
node->data = data;
node->next = app->next;
app->next = node;
}
// 栈弹出来一个元素
tree* popstack(stacknode& app) {
tree* data = app->next->data;
stacknode number = app->next;
app->next = number->next;
delete number;
return data;
}
// 查看栈头顶的那个元素
tree* checkstack(stacknode& app) {
return app->next->data;
}
// 判断栈是否为空
bool isempty(stacknode& app) {
if (app->next == NULL) {
return true;
}
else {
return false;
}
}
// 线索化二叉树
void postorder(tree* app) {
tree* APP = app;
stacknode stackdata = new stack;
initstack(stackdata);
while (APP || !isempty(stackdata)) {
if (APP) {
addstack(stackdata, APP);
APP = APP->lefttree;
}
else {
tree* top = checkstack(stackdata);
if (top->righttree && top->righttree->flage == false) {// 判断右节点是否被访问过,没有的户就把这个右节点存储到栈中
top = top->righttree;
addstack(stackdata, top);
APP = top->lefttree;
}
else {
tree* topdata = popstack(stackdata);
cout << topdata->data << "---";
topdata->flage = true;// 标记这个节点已经被访问过,后面不用再次访问这个节点了
}
}
}
}
int main() {
tree* app;
createtree(app);//创建一个二叉树
cout << "后序遍历二叉树采用非递归的方法:";
postorder(app);
cout << "end" << endl;
return 0;
}

这里与上面的两个遍历有一点不一样,这个借助了一个flag来判断右子树有没有被访问过,如果没有就入栈,直到为NULL的时候出栈;如果右子树被访问过,那么就是不入栈……,依此不断重复…

3、线索二叉树的遍历

中序线索化上述二叉树并找出根结点的前驱和后继。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct BiThrNode {
char data;// 数据
struct BiThrNode* leftchild;// 左指针
struct BiThrNode* rightchild;// 右指针
int LTag; // 左标志
int RTag; // 右标志
}BiThrNode, * BiThrTree;
// 全局定义一个线索化二叉树的一个全局变量
BiThrNode* pre = NULL;
// 二叉树的创建
void createTree(BiThrTree& app) {
char ch;
cin >> ch;
if (ch == '#') {
app = NULL;
}
else {
app = new BiThrNode;
app->data = ch;
app->LTag = 0;
app->RTag = 0;
createTree(app->leftchild);
createTree(app->rightchild);
}
}
// 线索化中序二叉树
void middleTree(BiThrTree &app) {
if (app) {
middleTree(app->leftchild);
// 在这里写一些线索化的代码
if (!app->leftchild) {// 如果左子树为空,线索化左子树
app->LTag = 1;
app->leftchild = pre;
}
if (pre != NULL && pre->rightchild == NULL) { // 如果pre的右子树为空的话,线索化最下面的这个节点前驱后继之类
pre->RTag = 1;
pre->rightchild = app;
}
pre = app;
middleTree(app->rightchild);
}
}
// 下面就是遍历线索化中序二叉树的方法
void middleprintf(BiThrTree& app) {
BiThrNode* current = app;
while (current && current->LTag == 0) {
current = current->leftchild;
}
while (current) {
cout << current->data << "---";
if (current->RTag == 1) {
current = current->rightchild;
}
else {
current = current->rightchild;
while (current && current->LTag == 0) {
current = current->leftchild;
}
}
}
}
int main() {
BiThrTree app;
createTree(app);
middleTree(app);
cout << "线索化中序二叉树的遍历为:";
middleprintf(app);
cout << "end" << endl;
return 0;
}

在这里的话就是使用递归的操作,加上了使用rTag与lTag两个标志,为0的时候表示的是左右子树,为1的时候就是表示有前驱或者后继,如果遍历到一个子树没有左子树的时候就指向他的前驱,右子树同理:指向后继……….;

线索化这个二叉树相当于就是重新对这个二叉树进行一个遍历以及对他的是否指向前驱或者后继还是左右子树进行一个修饰的过程;后面就是遍历线索二叉树,易于理解

4、构造哈夫曼树HT、哈夫曼编码HC、哈夫曼译码的算法实现。

在发送端,统计下面一段英文的不同字符个数和每个字符的出现频率,利用统 计数据构造构造哈夫曼树和哈夫曼编码;在接收端,将接收到的 0-1 序列恢复成英 文段落。

The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a failing political system. This jibes with other accounts. The Chinese leadership believes that the United States, and Western democracies in general, haven’t risen to the challenge of a globalized economy, which necessitates big changes in production patterns, as well as major upgrades in education and public infrastructure. In Trump and Trumpism, the Chinese see an inevitable backlash to this failure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#include<string>
#include<map>
using namespace std;

map<char, int>dataweight;// 存储权值的map容器
map<char, string>datacode;// 存储01数据的
map<string, char>codedatainformation;// 存储01对应的字符

#define max_size 9999
string stargeinformation;// 用来存储文章的内容

typedef struct {// 定义哈夫曼树
int weight;
int parent;
int leftchild;
int rightchild;
}Huffmannode,*HuffmanTree;

void getweight(string& app) {// 获取文章的各个字符的权重
for (auto spp : app) {
dataweight[spp]++;
}
}

HuffmanTree CreateHuffmanTree(int length) {// 创建一个哈夫曼树
int totallength = length * 2 - 1;
HuffmanTree tree = (HuffmanTree)malloc(sizeof(Huffmannode) * (totallength));// 首先要分配内存
for (int i = 0;i < totallength;i++) {//初始化所有的节点
tree[i].weight = 0;
tree[i].leftchild = -1;
tree[i].rightchild = -1;
tree[i].parent = -1;
}
int index = 0;//前面的length个节点要进行填充操作
for (auto it : dataweight) {
tree[index++].weight = it.second;
}
for (int i = length;i < totallength;i++) {// 接下来就是构造哈夫曼树
int minnumber1 = -1;
int minnumber2 = -1;
for (int j = 0;j < i;j++) {
if (tree[j].parent == -1) {// 如果在这个哈夫曼书中找到了这个父节点没有的节点的话就通过
if (minnumber1 == -1 || tree[minnumber1].weight > tree[j].weight) {// 找到两个最小的节点
minnumber2 = minnumber1;
minnumber1 = j;
}
else if (minnumber2 == -1 || tree[minnumber2].weight > tree[j].weight) {
minnumber2 = j;
}
}
}
tree[i].weight = tree[minnumber1].weight + tree[minnumber2].weight;
tree[i].leftchild = minnumber1;
tree[i].rightchild = minnumber2;
tree[minnumber1].parent = i;
tree[minnumber2].parent = i;
}
return tree;
}

void codehafuman(HuffmanTree& tree) {// 进行哈夫曼编码
int stroenumber = 0;
for (auto app : dataweight) {
char datachar = app.first;
string codedata = "";
int current = stroenumber;
int parent = tree[current].parent;
while (parent != -1) {
if (tree[parent].leftchild == current) {// 判断这个节点是不是在这个树的左子树
codedata = "0" + codedata;
}else {// 如果不是在左子树,那么就是在右子树了
codedata = "1" + codedata;
}
current = parent;
parent = tree[current].parent;
}
datacode[datachar] = codedata;
stroenumber++;
}
}

string encoding(string stargeinformation) {// 对文章进行编码
string codedata = "";
for (auto app : stargeinformation) {
codedata += datacode[app];
}
return codedata;
}

string skillcodehafuman(string& codedata,HuffmanTree&tree) {// 对哈夫曼编码进行解码
for (auto app : datacode) {// 对原来的马匹进行翻转成为一个新的map
codedatainformation[app.second] = app.first;
}
string stringdata = "";// 用来存储最后解码的字符
string datanumber = "";// 用来存储二进制数据,到后面可以通过map来实现stringdata的直接拼接
int number = dataweight.size() * 2 - 2;
for (auto it : codedata) {
if (it == '0') {
number = tree[number].leftchild;
datanumber += it;
}
else {
number = tree[number].rightchild;
datanumber += it;
}
if (tree[number].leftchild == -1 && tree[number].rightchild == -1) {
stringdata += codedatainformation[datanumber];
number = dataweight.size() * 2 - 2;
datanumber = "";
}
}
return stringdata;
}

int main() {
cout << "请输入文章内容:" << endl;
string line;
while (true) {
getline(cin, line); // 获取一行输入
if (line.empty()) {
break; // 输入空行时结束
}
stargeinformation += line + "\n"; // 将每一行文本添加到 stargeinformation 中,并加上换行符
}
getweight(stargeinformation);//获取文章中的数据的权重
HuffmanTree tree = CreateHuffmanTree(dataweight.size());// 构造哈夫曼树
codehafuman(tree);
string codedata = encoding(stargeinformation);
cout << codedata << endl;
cout << endl;
string relute = skillcodehafuman(codedata, tree);
cout << relute << endl;
free(tree);// 释放空间
return 0;
}

在这次的构造哈夫曼树编码的实验代码中,我使用3个map容器辅助存储字符的权值大小,以及存储单个字符的二进制编码,还有一个是逆序存储了二进制编码对应的字符;

基本思路就是书上的思路:这里数组来存储哈夫曼树,刚开始使用map的键值对存储输入字符的出现次数,接着利用map容器自带的size()表示长度,也就是叶子节点个数(有效存储信息的节点),往后就是依次储存到数组里面去;

后面在长度为n,在区间(n-n-2)里面存储度为二的父亲节点中依顺序在前n个节点依次找到两个权值最小的两个节点作为那个父亲节点的两个孩儿,依次往复,直到没有;

接着就是编码,从叶子节点往上面去编码左子树为0,右子树为1,直到根节点(根节点的parent为-1,这个判断是不是根节点),保存二进制到map容器中,键为字符,值为二进制编码,直到把所有的n个节点搞完;

然后又是利用循环对刚开始输入的文章进行循环,通过map存储的二进制数据对每一个字符进行编码;

最后就是译码了,,,从根节点出发一直到叶子节点,左子树为0,右子树为1,判断结束条件就是叶子节点的没有左右子树节点(leftchild==rightchile==-1),这样把这个二进制存下来,又通过最前面我提到的第三个map容器,他的作用就体现出来了,键存储的是之前的二进制编码,值就是字符,通过如此循环,再通过字符串的拼接就能译码成功了,就能重新搞出来一个刚才一样的文章了(^_^)

2.参考数据:
1
2
3
4
5
6
7
The Chinese official said he viewed the Trump Presidency not as an 
aberration but as the product of a failing political system. This jibes with other
accounts. The Chinese leadership believes that the United States, and Western
democracies in general, haven’t risen to the challenge of a globalized economy,
which necessitates big changes in production patterns, as well as major upgrades
in education and public infrastructure. In Trump and Trumpism, the Chinese see
an inevitable backlash to this failure.
3.参考结果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
请输入文章内容:
The Chinese official said he viewed the Trump Presidency not as an
aberration but as the product of a failing political system. This jibes with other
accounts. The Chinese leadership believes that the United States, and Western
democracies in general, haven’t risen to the challenge of a globalized economy,
which necessitates big changes in production patterns, as well as major upgrades
in education and public infrastructure. In Trump and Trumpism, the Chinese see
an inevitable backlash to this failure.

000101000000111101000000000101101100010111001111110010101000101001011110001011101010011111011110101011010011110000001111100100010110011001001001010011111000000000111100010111011000110101111101011111001010111101100101111011010010010110110000100001111011011001100011110100111111101001101110100011010110100001110111101110101000101111001011011111010000011100011110100111111100000000011111101011101111001010010001111000100011111001010100111101011101010010101011100111011011001010111111010111001100111011100010111100010101001111101110100001011110000010101110101101111000101000010110111111010110011011110100001011111110010011011100000001111100110000000001110111110100011010110001100011001000110110100001110101101111000101000000111101000000000101101100010111001111100110011010010010011101101110000101111010111111010000110011101100110010000010111111100000001010100011110000000001111100101101011010111000001010011111001011001000101010000010111000100111101001100100111110010111000101111000001110110110111010001010010010101111100111000110111010110001011001011111110110110111010101001011000111011101010011000100111000010101001000001011010010100010010100110001111101110110111001011011110001100111110000000001111110000000101010011100110010110010101001111110010101001111010111010101100111100111010010101001110110101100000101001111001110001100101101100101011101000010001001110100011001001000010111100000001110110001110000010111011110111000101010000010111111110100101101010111111000000010100110010101001011111110110110111110101110111100101001000111100010001011110010110111110101101010001000001110110110011100010011110100111111100100100110011100111111010011111101011110100101100111001110111110001111010101010111011101001001001011111101000110110110111001010010001111000101010001011110010110111101001100100111111010100011110100100111011110001111011011001010011011101001111000110110001111000100000011110110010101101111100101010011011100010111011000110101111101011111010011001001111000101110110001101011111010110110111010111000100111100000000011110100000000010110110001011100111101110010011110100011010011011110110110001100100010111000101011010010011001111110100101011000100101111100111010011100001111000110011111000000010110111111010100101010111001100011110110010101101010001

The Chinese official said he viewed the Trump Presidency not as an
aberration but as the product of a failing political system. This jibes with other
accounts. The Chinese leadership believes that the United States, and Western
democracies in general, haven’t risen to the challenge of a globalized economy,
which necessitates big changes in production patterns, as well as major upgrades
in education and public infrastructure. In Trump and Trumpism, the Chinese see
an inevitable backlash to this failure.