于“树和二叉树”的算法训练

二叉树的基本功训练

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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

void visit(BiTree root)
{
    printf("%d ",root->data);
}

void PreOrder(BiTree root){     //先根遍历
    if(root == NULL)    return;
    visit(root);
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}

void InOrder(BiTree root){      //中根遍历
    if(root == NULL)    return;
    InOrder(root->lchild);
    visit(root);
    InOrder(root->rchild);
}

void PostOrder(BiTree root){    //后根遍历
    if(root == NULL)    return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    visit(root);
}

void FreeTree(BiTree root) {    //后根遍历释放内存
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    PreOrder(root); 
    printf("\n");

    InOrder(root);
    printf("\n");

    PostOrder(root);
    printf("\n");

    FreeTree(root);
}

2.二叉树的层序遍历

需要自己实现队列

TODO：实现链队列

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
#define MAX_QUEUE 10

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

typedef struct Queue{
    BiTree data[MAX_QUEUE];
    int front;
    int rear;
}Queue, *QueuePtr;

QueuePtr  InitQueue()             
{
    QueuePtr Q = (QueuePtr)malloc(sizeof(Queue));
    Q->front = 0;
    Q->rear = 0;
    return Q;
}

void FreeQueue(QueuePtr Q)
{
    free(Q);
}

bool isEmpty(QueuePtr Q)
{
    if(Q->front == Q->rear)
        return true;
    else
        return false;
}

bool isFull(QueuePtr Q)
{
    if((Q->rear+1) % MAX_QUEUE == Q->front)
        return true;
    else
        return false;
}

bool EnQueue(QueuePtr Q, BiTree node)
{
    if(isFull(Q))   return false;
    Q->data[Q->rear] = node;
    Q->rear = (Q->rear+1)%MAX_QUEUE;
    return true;
}

BiTree DeQueue(QueuePtr Q)
{
    if(isEmpty(Q))  return NULL;
    BiTree q;    
    q = Q->data[Q->front];
    Q->front = (Q->front+1)%MAX_QUEUE;
    return q;
}

void visit(BiTree root)
{
    printf("%d ",root->data);
}

void LevelOrder(BiTree root)
{
    QueuePtr Q = InitQueue();
    EnQueue(Q, root);
    while(!isEmpty(Q))
    {
        BiTree nod = DeQueue(Q);
        visit(nod);
        if(nod->lchild!=NULL)
            EnQueue(Q, nod->lchild);
        if(nod->rchild!=NULL)
            EnQueue(Q, nod->rchild);
    }
    FreeQueue(Q);
}

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    LevelOrder(root);
    FreeTree(root);
}

3.求二叉树的高度

  1. 用全局变量
  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
 
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

void visit(BiTree root)
{
    printf("%d ",root->data);
}

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

int height = 0;
void GetHegiht1(BiTree root, int h)
{
    if(root==NULL) return;
    if(h>height)    height = h;
    GetHegiht1(root->lchild, h+1);
    GetHegiht1(root->rchild, h+1);
}

int GetHegiht2(BiTree root)
{
    if(root==NULL)  return 0;
    int l = GetHegiht2(root->lchild); 
    int r = GetHegiht2(root->rchild);
    if(l>=r)    return l+1;
    else   return r+1; 
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->lchild->rchild = CreateNode(5);
    
    GetHegiht1(root, 1);        //初始高度应该为1，若为空树，则不会更新为h，直接输出height = 0
    printf("%d\n",height);

    printf("%d\n",GetHegiht2(root));

    FreeTree(root);
}

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
#define MAXHEIGH 10
int Width[MAXHEIGH];

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

void visit(BiTree root)
{
    printf("%d ",root->data);
}

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

void PreOrder(BiTree root,int level){
    if(root==NULL)  return;
    Width[level]++;
    PreOrder(root->lchild, level + 1);
    PreOrder(root->rchild, level + 1);
}

int GetWidth(BiTree root){
    if (root == NULL) return 0; //特判空树
    for(int i = 0; i < MAXHEIGH; i++)
    {
        Width[i] = 0;
    }
    PreOrder(root,0);
    int maxwidth = 0;
    for(int i = 0;i < MAXHEIGH; i++)
    {
        if(Width[i]>maxwidth)   maxwidth = Width[i];
    }
    return maxwidth;
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->rchild = CreateNode(5);
    root->rchild->lchild = CreateNode(6);
    root->rchild->rchild = CreateNode(7);
    
    printf("%d",GetWidth(root));

    FreeTree(root);
}

5.求二叉树的WPL

WPL：二叉树中所有叶子节点的权值与其到根节点路径长度的乘积之和。

WPL 仅计算叶子节点，且深度从 0 开始计数。

处理方法类似求树的高度，只不过我们需要在叶子节点处特判求WPL

  1. 使用全局变量WPL
  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
typedef struct BiTNode{
    int weight;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

BiTree CreateNode(int weight) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->weight = weight;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

int WPL = 0;
void GetWeight(BiTree root,int level){
    if(root==NULL)  return;
    if(root->lchild == NULL && root->rchild == NULL)    //是叶子节点
        WPL += root->weight * level;
    GetWeight(root->lchild, level + 1);
    GetWeight(root->rchild, level + 1);
}

int GetWeight2(BiTree root, int level){
    if(root==NULL)  return 0;
    if(root->lchild == NULL && root->rchild == NULL)
        return root->weight * level;
    return GetWeight2(root->lchild, level+1) + GetWeight2(root->rchild, level+1);
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->weight = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->rchild = CreateNode(5);
    root->rchild->lchild = CreateNode(6);
    root->rchild->rchild = CreateNode(7);
    
    GetWeight(root, 0);     //边的个数，根节点应该是0
    printf("%d\n",WPL);
    
    printf("%d\n",GetWeight2(root,0));
    
    FreeTree(root);
}

6.判定一棵二叉树是否为二叉排序树

二叉排序树定义：

  1. 左节点值 < 根节点值 < 右节点值
  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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

int tmp = -111111;
bool is_BST = true;
void inorder(BiTree root)
{
    if(root == NULL)    return;
    inorder(root->lchild);
    if(tmp <= root->data)    tmp =root->data;
    else    is_BST = false;
    inorder(root->rchild);
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->rchild = CreateNode(5);
    root->rchild->lchild = CreateNode(6);
    root->rchild->rchild = CreateNode(7);
    inorder(root);
    printf("%d",is_BST);
    FreeTree(root);
}

7.判定一棵二叉树是否平衡

后序遍历,从叶节点开始判断左右子树是否平衡

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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

int abs_(int x)
{
    return x>0?x:-x;
}

int postorder(BiTree node,bool* is_balance){
    if(node == NULL)    return 0;
    int l = postorder(node->lchild,is_balance) ;
    int r = postorder(node->rchild,is_balance) ;
    if(abs_(r-l) > 1)   *is_balance = false;
    return (l>r ? l:r)+1;
}

bool is_balance(BiTree node){
    bool is_balance = true;
    postorder(node, &is_balance);
    return is_balance;
}

int main()
{
    // 创建根节点
    BiTree root = CreateNode(1);
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->rchild = CreateNode(5);
    root->rchild->lchild = CreateNode(6);
    root->rchild->rchild = CreateNode(7);
    
    printf("%d",is_balance(root));
    FreeTree(root);
}

8.判定一棵二叉树是否为完全二叉树。

  1. 采用层序遍历
  2. 注意队列需要头指针和尾指针，队尾方便插入，队首方便删除。
  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
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

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;


typedef struct QueueNode
{
    BiTree data;
    struct QueueNode *next;
}QueueNode, *QueueNodePtr;

typedef struct LinkQueue
{
    QueueNode *front;
    QueueNode *tail;
}LinkQueue, *LinkQueuePtr;

// 初始化队列
LinkQueuePtr InitQueue() {
    LinkQueuePtr p = (LinkQueuePtr)malloc(sizeof(LinkQueue));
    // 创建一个头节点，方便操作
    QueueNodePtr head = (QueueNodePtr)malloc(sizeof(QueueNode));
    head->next = NULL;
    head->data = NULL;
    
    p->front = p->tail = head;	
    return p;
}

// 判断队列是否为空
bool is_empty(LinkQueuePtr link) {
    return link->front == link->tail;
}

// 入队操作
void EnQueue(LinkQueuePtr link, BiTree node) {
    QueueNodePtr q = (QueueNodePtr)malloc(sizeof(QueueNode));
    q->data = node;
    q->next = NULL;
    
    // 将新节点插入到队尾,队尾方便插入，队首方便删除
    link->tail->next = q;
    link->tail = q;
}

// 出队操作
BiTree DeQueue(LinkQueuePtr link) {
    if (is_empty(link)) {
        return NULL;
    }
    
    QueueNodePtr q = link->front->next;  // 要出队的节点
    BiTree data = q->data;
    
    link->front->next = q->next;
    
    // 如果出队的是最后一个节点，需要重置tail指针
    if (q == link->tail) {
        link->tail = link->front;
    }
    
    free(q);
    return data;
}

// 销毁队列
void DestroyQueue(LinkQueuePtr link) {
    while (!is_empty(link)) {
        DeQueue(link);
    }
    free(link->front);  // 释放头节点
    free(link);         // 释放队列结构
}

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

void judge(BiTree root, bool* is_complete_tree, bool* flag){
    if(root->lchild == NULL && root->rchild == NULL)   *flag = true;
    if(root->lchild == NULL && root->rchild != NULL)    *is_complete_tree = false;
      

    if(root->lchild != NULL && root->rchild == NULL)   
    {
        if(*flag)    *is_complete_tree = false;
        *flag = true;
    }
    if(root->lchild != NULL && root->rchild != NULL)
    {
        if(*flag)    *is_complete_tree = false;
    }
    
}

bool is_complete_tree(BiTree root){
    LinkQueuePtr qu = InitQueue();
    EnQueue(qu, root);
    bool is_complete_tree = true;
    bool flag = 0;      //表示层序遍历时出现过叶子或只有左孩子的分支节点
    while(!is_empty(qu))
    {
        BiTree node = DeQueue(qu);
        judge(node, & is_complete_tree, &flag);
        if(node->lchild != NULL)      EnQueue(qu, node->lchild);
        if(node->rchild != NULL)      EnQueue(qu, node->rchild);
    }
    return is_complete_tree;
}




int main() {
    // 测试用例1：完全二叉树
    BiTree root1 = CreateNode(1);
    root1->lchild = CreateNode(2);
    root1->rchild = CreateNode(3);
    root1->lchild->lchild = CreateNode(4);
    root1->lchild->rchild = CreateNode(5);
    root1->rchild->lchild = CreateNode(6);
    root1->rchild->rchild = CreateNode(7);
    
    printf("测试1（完全二叉树）: %d\n", is_complete_tree(root1)); // 应该输出1
    FreeTree(root1);
    
    // 测试用例2：非完全二叉树（右孩子缺少左兄弟）
    BiTree root2 = CreateNode(1);
    root2->lchild = CreateNode(2);
    root2->rchild = CreateNode(3);
    root2->lchild->lchild = CreateNode(4);
    root2->rchild->rchild = CreateNode(5); // 这里缺少左孩子
    
    printf("测试2（非完全二叉树）: %d\n", is_complete_tree(root2)); // 应该输出0
    FreeTree(root2);
    
    // 测试用例3：非完全二叉树（节点不连续）
    BiTree root3 = CreateNode(1);
    root3->lchild = CreateNode(2);
    root3->rchild = CreateNode(3);
    root3->lchild->rchild = CreateNode(4); // 缺少左孩子
    
    printf("测试3（非完全二叉树）: %d\n", is_complete_tree(root3)); // 应该输出0
    FreeTree(root3);
    
    return 0;
}

9.跨考基本训练1

比8更简便的判断方法，将所有非空节点都入队（顺序从左到右，从上到下），当遇到空节点后，检查队列中剩余节点是否全为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool is_complete_tree(BiTree root){
    LinkQueuePtr qu = InitQueue();
    if(root == NULL)    return true; 
    EnQueue(qu, root);
    while(!is_empty(qu))
    {
        BiTree node = DeQueue(qu);
        if(node!=NULL)
        {
            EnQueue(qu, node->lchild);
            EnQueue(qu, node->rchild);
        }
        else {	
            while(!is_empty(qu))
            {
                BiTree node1 = DeQueue(qu);
                if(node1!=NULL)
                    return false;
                
            }
        }
    }
    return true;
}

10.跨考基本训练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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}


int Get2branchnode(BiTree root){
    if(root == NULL)    return 0;
    int l = Get2branchnode(root->lchild);
    int r = Get2branchnode(root->rchild); 
    if(root->lchild != NULL && root->rchild != NULL)
    {
        return l + r + 1;
    }
    else {
        return l + r;
    }
}

int main() {
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->lchild->lchild = CreateNode(5);
    root->lchild->lchild->rchild = CreateNode(6);
    
    printf("%d",Get2branchnode(root));

    FreeTree(root);
}

11.跨考基本训练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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BiTNode));    
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->lchild);
    FreeTree(root->rchild);
    free(root);
}

void PreOrderKth(BiTree root, int k, int &count, int &result) {
    if (root == NULL || result != -1) return;   // 空树或已找到结果则返回
    
    count++;
    if (count == k) {
        result = root->data;
        return;
    }
    
    PreOrderKth(root->lchild, k, count, result);
    PreOrderKth(root->rchild, k, count, result);
}

int main() {
    // 创建根节点
    BiTree root = CreateNode(1);
    root->data = 1;
    root->lchild = CreateNode(2);
    root->rchild = CreateNode(3);
    root->lchild->lchild = CreateNode(4);
    root->lchild->lchild->lchild = CreateNode(5);
    root->lchild->lchild->rchild = CreateNode(6);
    int result = -1;
    int count = 0;
    PreOrderKth(root,4,count,result);
    printf("%d",result);
    FreeTree(root);
}

“二叉树”的真题训练

2014

1.设计思想

  1. 先序遍历，在遍历的同时记录节点当前的深度。
    1. 若该节点左右节点为空，即为叶子节点，计算其带权路径长度
    2. 若该节点左右节点非空，递归访问左右节点计算带权路径长度
    3. 节点为空，直接返回。

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
typedef struct BitNode{
    int weight;
    struct BitNode *left,*right;
}BitNode, *BiTree;

BiTree CreateNode(int data) {
    BiTree node = (BiTree)malloc(sizeof(BitNode));    
    node->weight = data;
    node->left= node->right = NULL;
    return node;
}

void FreeTree(BiTree root) {
    if (root == NULL) return;
    FreeTree(root->left);
    FreeTree(root->right);
    free(root);
}

int GetWPL(BiTree node, int dep){
    if(node == NULL)    return 0;
    if(node->left == NULL && node->right == NULL)   return node->weight*dep;  
    return GetWPL(node->left, dep+1) + GetWPL(node->right, dep+1);
}

int main()
{
    BiTree root = CreateNode(1);
    root->weight = 1;
    root->left = CreateNode(2);
    root->right = CreateNode(3);
    root->left->left = CreateNode(4);
    root->left->right = CreateNode(5);
    root->right->left = CreateNode(6);
    root->right->right = CreateNode(7);
    printf("%d",GetWPL(root, 0));
}

3.复杂度

时间复杂度O(n)，空间复杂度O(n)

4.改进

2017

1.设计思想

通过中序遍历实现，遍历表达式二叉树，将符号节点与其左子树和右子树结合起来

由于根节点回引入额外的括号，因此我们需要使用dep避免输出额外括号

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
96
97
98
99
100
typedef struct node{
    char data[10];
    struct node *left, *right;
}BTree;

BTree* CreateNode(const char data[10]) {
    BTree *node = (BTree*)malloc(sizeof(BTree));    
    strcpy(node->data, data);
    node->left= node->right = NULL;
    return node;
}

void FreeTree(BTree* root) {
    if (root == NULL) return;
    FreeTree(root->left);
    FreeTree(root->right);
    free(root);
}

void GetOpt(BTree* node,int dep)
{
    if(node==NULL)  return;
    if(node->left != NULL || node->right != NULL)  
    {
        if(dep!=0)  printf("(");
        GetOpt(node->left,dep+1);   
        printf("%s",node->data) ; 
        GetOpt(node->right,dep+1);
        if(dep!=0)  printf(")");
    }
    else {
        printf("%s",node->data);
    }
}

BTree* CreateExpressionTree1() {
    // 创建所有节点
    BTree* multiply1 = CreateNode("*");
    BTree* plus = CreateNode("+");
    BTree* multiply2 = CreateNode("*");
    BTree* a = CreateNode("a");
    BTree* b = CreateNode("b");
    BTree* c = CreateNode("c");
    BTree* minus1 = CreateNode("-");  // 一元负号
    BTree* d = CreateNode("d");
    
    // 构建树结构
    multiply1->left = plus;
    multiply1->right = multiply2;
    
    plus->left = a;
    plus->right = b;
    
    multiply2->left = c;
    multiply2->right = minus1;
    minus1->right = d;  // 一元运算符，只有右子树
    
    return multiply1;
}

BTree* CreateExpressionTree2() {
    // 创建所有节点
    BTree* plus = CreateNode("+");
    BTree* multiply = CreateNode("*");
    BTree* minus1 = CreateNode("-");  // 一元负号
    BTree* a = CreateNode("a");
    BTree* b = CreateNode("b");
    BTree* minus2 = CreateNode("-");  // 二元减法
    BTree* c = CreateNode("c");
    BTree* d = CreateNode("d");
    
    // 构建树结构
    plus->left = multiply;
    plus->right = minus1;
    
    multiply->left = a;
    multiply->right = b;
    
    minus1->left = NULL;     // 明确一元运算符左子树为空
    minus1->right = minus2;  // 一元负号作用于减法表达式
    
    minus2->left = c;
    minus2->right = d;
    
    return plus;
}

int main() {
    BTree* root1 = CreateExpressionTree1();
    GetOpt(root1,0);
    cout << endl;
    FreeTree(root1);

    BTree* root2 = CreateExpressionTree2();
    GetOpt(root2,0);
    cout << endl;
    FreeTree(root2);
    
    return 0;
}

3.复杂度

时间复杂度O(n)，空间复杂度O(n)

4.改进

2022

1.设计思想

  1. 二叉搜索树的关键特性是其中序遍历序列为一个严格递增的序列。
  2. 采用中序遍历判断二叉树的节点值是否为递增的，由于非空二叉树的节点值为正数，可以使用变量min-1作为初值判断是否为二叉排序树。
  3. 左孩子2i，右孩子2i+1，父节点【i/2】下取整

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
typedef struct {
    int SqBiTNode[MAX_SIZE];
    int ElemNum;
}SqBiTree;

int min_num = -1;
bool flag = true;

void judge(SqBiTree *T, int pos){
    if(pos >= T->ElemNum || flag == false || T->SqBiTNode[pos-1]==-1) return;   // 递归终止条件：越界、已发现不是BST、或当前是空节点
    // 1. 递归遍历左子树 (2*pos)
    judge(T,2*pos);     
    
    // 2. 处理当前节点
    if(T->SqBiTNode[pos-1] >= min_num)   
    {
        min_num = T->SqBiTNode[pos-1];
    }
    else {
        flag = false;
        return ;
    }
    // 3. 递归遍历右子树 (2*pos + 1)
    judge(T,2*pos+1);
}

bool Is_Search_Tree(SqBiTree *T){
    flag = true;
    min_num = -1;
    judge(T, 1);
    return flag;
}

int main()
{
    SqBiTree T1 = {{40, 25, 60, -1, 30, -1, 80, -1, -1, 27}, 10};
    SqBiTree T2 = {{40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35}, 11};
    printf("T1 is BST? %s\n", Is_Search_Tree(&T1) ? "Yes" : "No");
    printf("T2 is BST? %s\n", Is_Search_Tree(&T2) ? "Yes" : "No");
}

3.复杂度

时间复杂度O(n)，空间复杂度O(n)

4.改进