第七章、树和二叉树

7.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
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include <iostream>
#include <string.h>
#include <map>
#include<stack>
#include<queue>
#include<unordered_map>
using namespace std;
#pragma warning(disable:4996)

typedef char ElemType;
#define MaxSize 100

typedef struct node{
	ElemType data;    //数据元素
	struct node* lchild;  //指向左孩子
	struct node* rchild;  //指向右孩子
}BTNode;

/*创建二叉树*/
void CreateBTNode(BTNode *& b,char *str) {
	BTNode* St[MaxSize], * p=NULL;  //St数组作为顺序栈
	int top = -1, k, j = 0;	   //top为栈顶指针
	char ch;
	b = NULL;					//初始时二叉链为空
	ch = str[j];
	while (ch!='\0')			//循坏扫描str中的每个字符
	{
		switch (ch) {
		case '(':top++; St[top] = p; k = 1; break; //开始处理左孩子节点
		case ')':top--; break;  //栈顶节点的子树处理完毕
		case ',':k = 2; break;  //开始处理右孩子节点
		default:p = (BTNode*)malloc(sizeof(BTNode)); //创建一个节点，由p指向它
			p->data = ch;   //存放节点值
			p->lchild = p->rchild = NULL;  //左右指针都设置空
			if (b = NULL)b = p;  //弱国没有建根，则p所指为根
			else {
				switch (k)
				{
				case 1:St[top]->lchild = p; break; //新建节点作为栈顶节点的左孩子
				case 2:St[top]->rchild = p; break; //新建节点作为栈顶指针的右孩子
				}
			}
		}
		j++;		//继续扫描str
		ch = str[j];
	}
}


/*查找节点*/
BTNode* FindNode(BTNode* b, ElemType x)  //返回data域为x的节点指针
{
    BTNode* p;
    if (b == NULL)
        return NULL;
    else if (b->data == x)
        return b;
    else
    {
        p = FindNode(b->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);
    }
}
/*左孩子*/
BTNode* LchildNode(BTNode* p)   //返回*p节点的左孩子节点指针
{
    return p->lchild;
}
/*右孩子*/
BTNode* RchildNode(BTNode* p)   //返回*p节点的右孩子节点指针
{
    return p->rchild;
}
/*二叉树深度*/
int BTNodeDepth(BTNode* b)  //求二叉树b的深度
{
    int lchilddep, rchilddep;
    if (b == NULL)
        return(0);                          //空树的高度为0
    else
    {
        lchilddep = BTNodeDepth(b->lchild);   //求左子树的高度为lchilddep
        rchilddep = BTNodeDepth(b->rchild);   //求右子树的高度为rchilddep
        return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
    }
}
/*输出二叉树*/
void DispBTNode(BTNode* b)  //以括号表示法输出二叉树
{
    if (b != NULL)
    {
        printf("%c", b->data);
        if (b->lchild != NULL || b->rchild != NULL)
        {
            printf("(");
            DispBTNode(b->lchild);
            if (b->rchild != NULL) printf(",");
            DispBTNode(b->rchild);
            printf(")");
        }
    }
}
/*销毁二叉树*/
void DestroyBTNode(BTNode*& b)   //销毁二叉树
{
    if (b != NULL)
    {
        DestroyBTNode(b->lchild);
        DestroyBTNode(b->rchild);
        free(b);
    }
}

//先序遍历
void PreOrder(BTNode* b) {
    if (b != NULL) {
        printf("%c ", b->data);
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}

// 中序遍历
void InOrder(BTNode* b) {
    if (b != NULL) {
        PreOrder(b->lchild);
        printf("%c ", b->data);
        PreOrder(b->rchild);
    }
}

//后序遍历
void PostOrder(BTNode* b) {
    if (b != NULL) {
        PreOrder(b->lchild);
        PreOrder(b->rchild);
        printf("%c ", b->data);
    }
}


/*层次遍历，队列*/
void LevelOrder(BTNode* b) {
    BTNode* p;
    queue<BTNode*> myQueue; //定义
    myQueue.push(b);  //根节点入队
    while (!myQueue.empty())
    {	//取得头元素
        p = myQueue.front(); myQueue.pop();
        printf("%c ", p->data);
        if (p->lchild != NULL)  //加入左孩子
            myQueue.push(p->lchild);
        if (p->rchild != NULL)  //加入右孩子
            myQueue.push(p->rchild);
    }
}

//判断是否是完全二叉树
bool IsComplete(BTNode* b) {
    if (b == NULL)return true;
    bool leaf = false;
    queue<BTNode*>q;
    q.push(b);
    while (!q.empty()) {
        BTNode* p = q.front();
        q.pop();
        if ((leaf && (p->lchild != NULL || p->rchild != NULL)) || (p->lchild == NULL && p->rchild != NULL))//这些判断条件是所有的不满足是完全二叉树的条件。条件一（第二个||前面的条件）：上述的状态已经发生，但是当前访问到的节点不是叶节点（有左孩子或者右孩子）。条件二：当前节点有右孩子，没有左孩子
            return false;
        if (p->lchild != NULL)//左孩子不为空，加入到队列中去
            q.push(p->lchild);
        if (p->rchild != NULL)//右孩子不为空，加入到队列中去
            q.push(p->rchild);
        if ((p->lchild != NULL && p->rchild == NULL) || (p->lchild == NULL && p->rchild == NULL))//这个if语句就是判断状态是否要发生
            leaf = true;
    }
    return true;
}
//翻转二叉树
void invertTree(BTNode* b) {

    if (b == NULL) return;

    BTNode* temp = b->lchild;   //左右节点交换
    b->lchild = b->rchild;
    b->rchild = temp;

    invertTree(b->lchild);      //递归左子树
    invertTree(b->rchild);      //递归右子树
}


//将二叉树的叶子节点按照从左到右的顺序连成一个单链表，表头指针为head
void linkLeafNode(BTNode* p, BTNode*& head, BTNode*& tail) {
    if (p != NULL) {//边界条件
        //判断是否是叶子节点
        if (p->lchild == NULL && p->rchild == NULL) {
            if (head == NULL) {//还没有填元素
                head = p;//头
                tail = p;//尾
            }
            else {
                tail->rchild = p;//不是叶子节点，tail右孩子指向p
                tail = p; //尾巴指向p
            }
        }
        linkLeafNode(p->lchild, head, tail);//从左到右
        linkLeafNode(p->rchild, head, tail);
    }
}

int main() {
    char* str = (char*)malloc(100);
    printf("(1),输入二叉树的元素：\n");
    scanf("%s", str);// A(B(D,E),C(F,G))
    //printf("%s",str);

    BTNode* btnode;
    BTNode* head, * tail;
    printf("(2),创建二叉树：\n");
    CreateBTNode(btnode, str);
    DispBTNode(btnode);

    //printf("\n层次遍历：\n");
    //LevelOrder(btnode);
    //head = tail = NULL;
    //linkLeafNode(btnode,head,tail);

    //printf("\n叶子节点如下所示：\n");
    //LevelOrder(head);

    /*if (IsComplete(btnode)) {
        printf("\n该二叉树是完全二叉树！\n");
    }
    else {
        printf("\n该二叉树不是完全二叉树！\n");
    }*/
    printf("\n(3),翻转二叉树:\n");
    invertTree(btnode);
    DispBTNode(btnode);
}

先序遍历,非递归实现，栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*先序遍历,非递归实现，栈*/
void PreOrderl(BTNode* b) {
    BTNode* p;
    stack<BTNode*> myStack; //定义栈
    if (b != NULL) {
        myStack.push(b);  //根节点进栈
        while (!myStack.empty())  //栈不空时循环
        {
            p = myStack.top(); //退栈节点p并访问它
            myStack.pop();
            printf("%c ", p->data);
            if (p->rchild != NULL)  //有右孩子时将其进栈
                myStack.push(p->rchild);
            if (p->lchild != NULL)//有左孩子时将其进栈
                myStack.push(p->lchild);
        }
        printf("\n");
    }
}

三种遍历-迭代

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
//前序遍历
void preOrderIteration(TreeNode *root) {
    if (root == nullptr)
        return;
    stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode* temp = stack.top(); stack.pop();
        cout << temp->val << " ";
        if (temp->right != nullptr)stack.push(temp->right);
        if (temp->left != nullptr)stack.push(temp->left);
    }
}

//中序遍历
void inOrderIteration(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    TreeNode* cur = root;
    stack<TreeNode*> stack;
    while (!stack.empty() || cur != nullptr) {
        while (cur != nullptr) {
            stack.push(cur);
            cur = cur->left;
        }
        TreeNode* node = stack.top(); stack.pop();
        cout << node->val << " ";
        if (node->right != nullptr) {
            cur = node->right;
        }
    }
}

//后序遍历
void postOrderIteration(TreeNode* head) {
    if (head == nullptr) {
        return;
    }
    stack<TreeNode*> stack1;
    stack<TreeNode*> stack2;
    stack1.push(head);
    while (!stack1.empty()) {
        TreeNode* node = stack1.top(); stack1.pop();
        stack2.push(node);
        if (node->left != nullptr) {
            stack1.push(node->left);
        }
        if (node->right != nullptr) {
            stack1.push(node->right);
        }
    }
    while (!stack2.empty()) {
        cout << stack2.top()->val << " ";
        stack2.pop();
    }
}

例 7.11 计算节点个数

1589587621308.png

1
2
3
4
5
int Nodes(BTNode *b) {
    int num1, num2;
    if (b == NULL)return 0;
    else return Nodes(b->lchild) +Nodes(b->rchild)+1;
}

例 7.12 输出叶子节点

[例7.12]假设二叉树采用二叉链存储结构存储，试设计一个算法，输出一棵给定二叉树的所有叶子结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//从左到右输出
void DispLeaf(BTNode *b) {
    if (b!=NULL) {
        if (b->lchild == NULL && b->rchild == NULL)
            printf("%c ",b->data);
        DispLeaf(b->lchild);
        DispLeaf(b->rchild);
    }
}

//从右到左输出
void DispLeaf1(BTNode* b) {
    if (b != NULL) {
        if (b->lchild == NULL && b->rchild == NULL)
            printf("%c ", b->data);
        DispLeaf1(b->rchild);
        DispLeaf1(b->lchild);
    }
}

例 7.13 求节点值 x 节点所在层次

1
2
3
4
5
6
7
8
9
10
11
/*x,要查的节点值，h高度默认为1*/
int Level(BTNode *b,ElemType x,int h=1) {
    int L;
    if (b == NULL)return 0;
    else if (b->data == x)return h;
    else {
        L = Level(b->lchild,x,h+1);
        if (L != 0)return 1;
        else return Level(b->rchild,x,h+1);
    }
}

例 7.14 求第 k 层节点个数

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
/*基于先序遍历思路*/
void Lnodenum(BTNode *b,int h,int k,int &n) {
    if (b==NULL) {
        return;
    }
    else {
        if (h == k)n++;
        else if (h<k) {
            Lnodenum(b->lchild,h+1,k,n);
            Lnodenum(b->rchild,h+1,k,n);
        }
    }
}
/*使用全局变量*/
int n = 0;
void Lnodenum(BTNode* b, int h, int k) {
    if (b == NULL) {
        return;
    }
    else {
        if (h == k)n++;
        else if (h < k) {
            Lnodenum(b->lchild, h + 1, k);
            Lnodenum(b->rchild, h + 1, k);
        }
    }
}