C/C++实现树操作的实例代码

时间:2022-01-02 04:15:35

预处理命令

?
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int elemtype;
typedef struct tNode* tree;
typedef struct tNode {
 elemtype elem;
 tree left;
 tree right;
}tNode;

计算树的节点个数

?
1
2
3
4
5
6
7
//明确函数的功能:返回传入树的节点个数
//定好尾头:尾:当传入的节点尾NULL时 头:1 + count(t->left) + count(t->right)
int count(tree t)
{
 if (t == NULL) return 0;
 return 1 + count(t->left) + count(t->right);
}

求树中节点数据为num的节点个数

?
1
2
3
4
5
6
7
8
9
10
11
12
13
//明确函数功能:返回节点数据为num的节点个数
//定好尾头:尾:NULL 头:1 + func(左) + func(右) // 或者 func(左) + func(右)
int count_num(tree t, elemtype num)
{
 if (t == NULL) return 0;
 else
 {
 if (t->elem == num)
 return 1 + count_num(t->left, num) + count_num(t->right, num);
 else
 return count_num(t->left, num) + count_num(t->right, num);
 }
}

求树中节点数据的总和

?
1
2
3
4
5
6
7
8
9
//明确函数功能:返回总和
//定好尾头:尾:NULL 头:root-> elem + func(左) + func(右)
int add(tree t)
{
 if (t == NULL)
 return 0;
 else
 return t->elem + add(t->left) + add(t->right);
}

判断树中有无数据为num的节点

?
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
//两种方式:一种是可以达成目的就结束,一种是需要遍历完全才结束
//明确函数功能:判断其中有没有值为num的节点返回1或0
//定好尾头:尾:值为num ,头:
int inTree_1(tree t, elemtype num)
{
 if (t->elem == num)
 return TRUE;
 else
 {
 if (t->left != NULL)
 intree(t->left, num); // 使用递归将其递到子节点
 if (t->right != NULL)
 intree(t->right, num);
 }
 return FALSE;
}
//确定函数功能:根据num的有无,返回0/非0
//定好尾头:尾:NULL 头:有:return 1 + func(左)+func(右) 无:func(左)+func(右)
int inTree_2(tree t, elemtype num)
{
 if (t == NULL) return 0;
 int res;
 if (t->elem == num)
 res = 1+ intree(t->left, num) + intree(t->right, num);
 if (t->elem == num)
 res = intree(t->left, num) + intree(t->right, num);
 return res;
}

计算值为num的个数

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int count_elem(tree t, elemtype val, int* num)
{
 int val_l, val_r;
 if (t->left == NULL)
 return t->elem;
 if (t->right == NULL)
 return t->elem;
 else
 {
 val_l = count_elem(t->left, val, num);
 if (val == val_l)
 (*num)++;
 val_r = count_elem(t->right, val, num);
 if (val == val_r)
 (*num)++;
 return t->elem;
 }
 return *num;
}

打印trunk

?
1
2
3
4
5
6
7
8
9
10
//明确函数功能:打印trunk
//定好尾头 尾:NULL 头:第一步是判断本节点是否是树干然后打印,再func(左)去打印左边的树干 func(右)去打印右边的树干
void print_trunk(tree t)
{
 if (t == NULL) return;
 if (t->right != NULL || t->left != NULL)
 printf("%d", t->elem);
 print_trunk(t->right);
 print_trunk(t->left);
}

判断两棵树是否一样

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int same(tree t1, tree t2)
{
 if (count(t1) == count(t2))
 {
 if (t1->elem != t2->elem)
 return FALSE;
 if (t1->left != NULL && t2->left != NULL)
 same(t1->left, t2->left);
 if (t1->right != NULL && t2->right != NULL)
 same(t1->right, t2->right);
 return TRUE;
 }
 else return FALSE;
}

求树的高度

?
1
2
3
4
5
6
7
#define max(x, y) (x > y) ? x : y
 
int height(tree t)
{
 if (t == NULL)return -1;
 return 1 + max(height(t->right), height(t->left));
}

打印树中某值的层数

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//明确函数功能:寻找放入的数的层数并打印
//确定尾://找到特定值的节点 找到NULL 头:若是则打印,若不是则去左右子树寻找layer++,当孩子寻找完都没有时layer--
bool flag = false; //flag标记可以用于提前结束递归
void getTreeLayer(Node * root, int num, int &layer)
{
 if (root == NULL) return;
 if (flag == true) return;
 if (root->data == num) {
 cout << "num值" << num << "的层数为:" << layer << endl;
 flag = true;
 return;
 }
 layer++;
 getTreeLayer(root->lChild, num);
 getTreeLayer(root->rChild, num);
 layer--;
}

求节点的路径

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> path;
bool flag = false; //flag标记可以用于提前结束递归
void getTreeLayer(Node * root, int num, int &layer)
{
 if (root == NULL) return;
 if (flag == true) return;
 if (root->data == num) {
 for(int x : path)
 cout << x << " ";
 bool flag = true;
 return;
 }
 path.push_back();
 getTreeLayer(root->lChild, num);
 getTreeLayer(root->rChild, num);
 path.pop_back();
}

总结

以上所述是小编给大家介绍的C/C++实现树操作的实例代码,希望对大家有所帮助!

原文链接:https://blog.csdn.net/a13352912632/article/details/104263371