二叉树基础

#pragma once

#include
#include
#include
#include

typedef int TDatatype;
typedef struct BTree
{
	TDatatype val;
	BTree* left, *right;
}BTree;

BTree* CreateNode(TDatatype x);
void CreateTree(BTree* root, BTree* left, BTree* right);

void preorder(BTree* root);
void inorder(BTree* root);
void lastorder(BTree* root);
void destoryTree(BTree** root);
int Treesize(BTree* root);
int TreeLeafsize(BTree* root);
int TreeLevelsize(BTree* root, int k);
BTree* findTree(BTree* root, int x);
void TreeLevelOrder(BTree* root);
bool TreeComplete(BTree* root);
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

#include"binaryTree.h"

BTree* CreateNode(TDatatype x)
{
	BTree* node = (BTree*)malloc(sizeof(BTree));
	node->val = x;
	node->left = node->right = NULL;
	return node;
}

void CreateTree(BTree* root, BTree* left, BTree* right)
{
	assert(root);
	root->left = left;
	root->right = right;
}
void preorder(BTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d->", root->val);
	preorder(root->left);
	preorder(root->right);
}
void inorder(BTree* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	inorder(root->left);
	printf("%d->", root->val);
	inorder(root->right);
}
void lastorder(BTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	lastorder(root->left);
	lastorder(root->right);
	printf("%d->", root->val);
}
void destoryTree(BTree** root)
{
	assert(root);
	if (*root == NULL) return;
	BTree* left =(*root)->left;
	BTree* right = (*root)->right;
	free(*root);
	*root = NULL;
	destoryTree(&left);
	destoryTree(&right);
}
int Treesize(BTree* root)
{
	if (root==NULL) return 0;
	return Treesize(root->left) + Treesize(root->right) + 1;
}
int TreeLeafsize(BTree* root)
{
	if (root == NULL) return 0;
	return Treesize(root->left) + Treesize(root->right);
}
int TreeLevelsize(BTree* root, int k)
{
	if (root == NULL) return 0;
	if (k > 1) return TreeLevelsize(root->left, k-1) + TreeLevelsize(root->right, k - 1);
	return 1;
}
BTree* findTree(BTree* root, int x)
{
	if (root == NULL) return NULL;
	if (root->val == x) return root;
	BTree* node = findTree(root->left, x);
	if (node) return node;
	return findTree(root->right, x);
}
void TreeLevelOrder(BTree* root)
{
	assert(root);
	BTree* nums[1010] = { 0 };
	int hh = 0, tt = -1;
	nums[++tt] = root;
	while (hh <= tt)
	{
		BTree* node = nums[hh++];
		if (node == NULL)
		{
			printf("NULL ");
			continue;
		}
		printf("%d->", node->val);
		nums[++tt] = node->left;
		nums[++tt] = node->right;
	}
	puts("end");
}
bool TreeComplete(BTree* root)
{
	if (root == NULL) return true;
	BTree* nums[1010] = { 0 };
	int hh = 0, tt = -1;
	nums[++tt] = root;
	while (hh <= tt)
	{
		BTree* node = nums[hh++];
		if (node == NULL)
			return hh > tt;

		//不能把NULL节点录进去，不能让null影响结果

		if(node->left) nums[++tt] = node->left;
		if(node->right) nums[++tt] = node->right;
	}
	return true;
	
}
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

注意

1.在二叉树的销毁中，我们可是不用传二级指针，我们可以使用一级指针对他进行释放，但是，我们的各个根节点都不能置为NULL，除了root之外的节点都是安全的，但是对于root节点来说就是存在危险性的，我们必须在调用函数的时候手动置为NULL（最好使用二级指针）
2.在对树进行层序遍历的时候，需要使用队列
3.判断是不是完全二叉树时，我们需要知道完全二叉树的结构（除了底层之外，都是排列满的），在将节点加入队列的时候，我们需要进行判断，判断他的左右节点是不是NULL，只能将不为NULL的节点加入队列中，如果将NULL节点加入了队列中，那么会对hh和tt的比较造成错误影响，