二叉树操作题

---

title: 二叉树操作三道题（分享）
author: Codemon
date: 2022-11-12 09:06:11
tags:

---

二叉树操作三道题

#include
#include
#include
#include
#include
using namespace std;
typedef struct node
{
    char val;
    struct node* left;
    struct node* right;
} node;
#define ALLOC_(name, xx) \
node * name = (node*)malloc(sizeof(node)); \
name->val = xx; \
name->left = name->right = NULL;

void buildTree(node*& t)
{
    char a, b, c;
    cin >> a;
    if (a == '#')
        return;
    map<char, node*> mp;
    ALLOC_(root, a);
    mp[root->val] = root;
    while (cin >> a)
    {
        if (a == '#')
            break;
        cin >> b >> c;
        auto parent = mp.find(a);
        if (b != '0') {
            auto left = mp.find(b);
            if (left == mp.end())
            {
                ALLOC_(p, b);
                mp[p->val] = p;
                left = mp.find(p->val);
            }
            parent->second->left = left->second;
        }
        if (c != '0') {
            auto right = mp.find(c);
            if (right == mp.end())
            {
                ALLOC_(p, c);
                mp[p->val] = p;
                right = mp.find(p->val);
            }
            parent->second->right = right->second;
        }
       
        

    }
    t = root;
    return;

}

void Swap(node*& T1, node*& T2)//交换两个二叉树结点指针的指向
{
    node* t = T1;
    T1 = T2;
    T2 = t;
}
void NodeSwap(node*& T)//交换二叉树每个结点的左孩子和右孩子
{
    //此算法根据二叉树先序遍历算法改造而来
    if (T != NULL)
    {
        if (T->left != NULL && T->right != NULL)//如果T的左孩子和右孩子都不空
        {
            //将"交换二叉树每个结点的左孩子和右孩子"转换为"交换二叉树每个结点的左孩子的数据域和右孩子的指针域".
            Swap(T->left, T->right);
        }
        else if (T->left != NULL && T->right == NULL)//如果T的左孩子不空且右孩子为空
        {
            //将T的左子树变为右子树
            T->right = T->left;
            T->left = NULL;
        }
        else if (T->left == NULL && T->right != NULL)//如果T的左孩子为空且右孩子不为空
        {
            //将T的右子树变为左子树
            T->left = T->right;
            T->right = NULL;
        }
        else//如果T的左孩子和右孩子都为空
        {
            //空操作
            ;
        }
        NodeSwap(T->left);
        NodeSwap(T->right);
    }
    else
    {
        ;
    }
}

void FloorPrint_QUEUE(node*& Tree) //层序遍历_队列实现
{
    queue <node*> q;
    if (Tree != NULL)
    {
        q.push(Tree);   //根节点进队列
    }

    while (q.empty() == false)  //队列不为空判断
    {
        cout << q.front()->val << " ";
    
        if (q.front()->left != NULL)   //如果有左孩子，leftChild入队列
        {
            q.push(q.front()->left);
            cout << q.front()->left->val<<" ";
        }
        else {
            cout << "0" << " ";
        }
        if (q.front()->right != NULL)   //如果有右孩子，rightChild入队列
        {
            q.push(q.front()->right);
            cout << q.front()->right->val << endl;
        }
        else {
            cout << "0" << endl;
        }
        q.pop();  //已经遍历过的节点出队列
    }

}

int main() {
    node* T;
    buildTree(T);
    NodeSwap(T);
    FloorPrint_QUEUE(T);
    return 0;
}
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

#include
#include
#include
#include
using namespace std;
typedef struct node
{
    char val;
    struct node* left;
    struct node* right;
} node;
#define ALLOC_(name, xx) \
node * name = (node*)malloc(sizeof(node)); \
name->val = xx; \
name->left = name->right = NULL;

void buildTree(node*& t)
{
    char a, b, c;
    cin >> a;
    if (a == '#')
        return;
    map<char, node*> mp;
    ALLOC_(root, a);
    mp[root->val] = root;
    while (cin >> a)
    {
        if (a == '#')
            break;
        cin >> b >> c;
        auto parent = mp.find(a);
        if (b != '0') {
            auto left = mp.find(b);
            if (left == mp.end())
            {
                ALLOC_(p, b);
                mp[p->val] = p;
                left = mp.find(p->val);
            }
            parent->second->left = left->second;
        }
        if (c != '0') {
            auto right = mp.find(c);
            if (right == mp.end())
            {
                ALLOC_(p, c);
                mp[p->val] = p;
                right = mp.find(p->val);
            }
            parent->second->right = right->second;
        }
       
        

    }
    t = root;
    return;

}

int GetHeight(node* BT) {
    int h1;
    int h2;
    if (!BT)
        return 0;
    else {
        h1 = GetHeight(BT->left);
        h2 = GetHeight(BT->right);
        return h1 > h2 ? ++h1 : ++h2;
    }
}

int main() {
    node* T;
    buildTree(T);
    cout << GetHeight(T) << endl;
    return 0;
}
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

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

using namespace std;
#define len1 sizeof(BiTNode)
#define len2 sizeof(queue)
typedef char ElemType;//元素类型


typedef struct BiTNode {
 ElemType data;
 struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;

//辅助队列
typedef struct SqQueue {
 BiTree p;  //树的结点的指针
 struct SqQueue* pnext;
}SqQueue, * queue;


void createTree(BiTree& T)
{
 ElemType x;
 BiTree tree = NULL;//树根
 BiTree pnew = NULL;
 queue phead = NULL, ptail = NULL, listnew = NULL, pcur = NULL;
 int temp;
 do
 {
  scanf("%c", &x);
  if (x == '#')break;
  temp = getchar();
  pnew = (BiTree)calloc(1, len1);//新的树的节点
  pnew->data = x;
  listnew = (queue)calloc(1, len2);
  listnew->p = pnew;//树的结点入列
  if (tree == NULL)
  {
   tree = pnew;
   phead = listnew;
   ptail = listnew;
   pcur = listnew;
   continue;
  }
  else
  {
   ptail->pnext = listnew;  //尾插法使listnew入列
   ptail = listnew;
  }

  if (pcur->p->lchild == NULL )
  { 
   pcur->p->lchild = pnew;
  }
  else if (pcur->p->rchild == NULL )
  {
   pcur->p->rchild = pnew;
   pcur = pcur->pnext;
  }

 } while (1);
 T = tree;
}
int getLeafNum(BiTree root)
{
 if (NULL == root || root->data == '0')
 {
  return 0;
 }
 if ((NULL == root->lchild || root->lchild->data == '0') && (NULL == root->rchild|| root->rchild->data == '0'))
 {
  return 1;
 }

 int leftLeafNum = getLeafNum(root->lchild);
 int rightLeafNum = getLeafNum(root->rchild);
 int leafNum = leftLeafNum + rightLeafNum;
 return leafNum;
}

int main() {
 BiTree T;
 createTree(T);
 int s;
 s = getLeafNum(T);
 cout << s << endl;
 return 0;
}
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