二叉树

存储方式：顺序存储和链式存储：

关于二叉树常用性质：
度、叶子节点的公式推导：
1。N0 = N2+1
2。N0 = N2+1
3。
满二叉：第i层有2^i-1次个节点
深度为h的二叉树最多有：（2^h) -1个节点

树的遍历：

最好体现叶之后的空：

二叉树的遍历

**注意：**所有NULL判断都应该放在开头，否则会出现如下类似错误，尤其是在中序后序遍历中。开头缺少NULL判断。

1. 前序

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);

}
1
2
3
4
5
6
7
8
9
10
11
12

2. 中序

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11

3. 后序

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreePostOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11

二叉树的遍历

遇到的问题

1. 函数调用出错了，函数名写错了或参数写错了。

2. 0XFFF,总之是节点不存在。
   后来检查发现，是我调用create函数出错了，在头文件.h中的函数和实现的函数名不一样。

3. 有NULL判断，但是还是说来到了非法地址。
   检查发现：该置NULL的地方没有值NULL。
   

OJ题

1. 单值二叉树
分析：

// 用异或可以的
// 递归思路：全部父亲和孩子相等，那就说明是单值
// 当然用一个set集合，最后求集合的大小：这样显然效率低
// 出口：为空返回True，空肯定不影响呀
// 先写错情况，不等就返回
// 如果走到下面，说明该局部都相等，需要再遍历到更深地方。
// 难点在：先写出false情况。
bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    // 
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;
    // 如果走到下面，说明都相等
    return isUnivalTree(root->left) && isUnivalTree(root->right);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

关于树的知识

树的表示法和代码：

// 静态地定义度为5的树，但是可能有的节点会浪费空间
#define N 5

struct TreeNode
{
	int data;
	struct TreeNode* childAddr[N];
	int childSize;
};



 //顺序表存储孩子节点指针
struct TreeNode
{
	int data;
	// 数组指针，需要用二级来存	普通非指针类型数据用一级指针存	而一级指针数据的数组用二级指针
	struct TreeNode** childAddr;
	int childSize;
	int childCapacity;
};


打印：

 //孩子兄弟表示法
typedef int DataType;
struct Node
{
	struct Node* firstC;	// 第一个孩子指针
	struct Node* pNext_Brother;	// 指向下一个兄弟节点
	DataType data;	// 数据域
};

```c

// 做孩子兄弟表示法的打印实现
typedef struct
{
	struct Node* child;	// 第一个孩子指针
	struct Node* brother;	// 指向下一个兄弟节点
	int data;	// 数据域
}Node;


void printTree(Node* par)
{
	if (par == NULL)
	{
		return;
	}
	//printf("%d ", par->data);
	Node* cur = par->child;
	while (cur)
	{
		// printf()
		printTree(cur);
		cur = cur->brother;
	}

}


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

并查集是多棵树组成的数据结构