【数据结构】二叉树

链式二叉树的实现

平衡二叉搜索树

哈希表

B数

1
2
3
4
5
6
7
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

遍历方法

三个部分：根，左子树，右子树

  • 前序遍历
  • 中序遍历
  • 后续遍历
  • 层序遍历
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
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<stdbool.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc failed");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

/*前序遍历*/
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

/*中序遍历*/
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

/*后序遍历*/
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

int main()
{
	BTNode* root = CreatTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	return 0;
}

统计二叉树的结点数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*返回结点的数量*/
int TreeSize(BTNode* root,int*psize)
{
	if (root == NULL)
	{
		return;
	}
    
	++(*psize);
	TreeSize(root->left,psize);
	TreeSize(root->right,psize);
	return *psize;
}
int main()
{
	BTNode* root = CreatTree();
	int size = 0;
	size=TreeSize(root,&size);
	printf("%d", size);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/*分治*/
int TreeSize(BTNode* root)
{
	return root == NULL?0 : TreeSize(root->left) + TreeSize(root->right)+1;
}

int main()
{
	int size = 0;
	size=TreeSize(root);
	printf("%d", size);
	return 0;
}

统计树的高度

1
2
3
4
5
6
7
8
9
10
11
/*方法一：时间复杂度过高*/
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
		return TreeHeight(root->left) > TreeHeight(root->right) ?
		TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
/*较优写法*/
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int LeftHeight = TreeHeight(root->left) ;
	int RightHeight = TreeHeight(root->right);

	return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}

第K层的数据数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*第K层的数据数量*/
int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	int LeftK = TreeKLevel(root->left, k - 1);
	int RightK= TreeKLevel(root->right, k - 1);

	return LeftK + RightK;
}

int main()
{
	int k=3;
	int level = TreeKLevel(root,k);
	printf("%d\n", level);
	return 0;
}