©2020-2024 ioDraw All rights reserved
<>二叉树
存储方式：顺序存储和链式存储：
关于二叉树常用性质：
度、叶子节点的公式推导：
1。N0 = N2+1
2。N0 = N2+1
3。
满二叉：第i层有2^i-1次个节点
深度为h的二叉树最多有：（2^h) -1个节点
<>树的遍历：
最好体现叶之后的空：
<>二叉树的遍历
**注意：**所有NULL判断都应该放在开头，否则会出现如下类似错误，尤其是在中序后序遍历中。开头缺少NULL判断。
* 前序 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf(
"NULL "); return; } printf("%d ", root->_data); BinaryTreePrevOrder(root->_left)
; BinaryTreePrevOrder(root->_right); }
* 中序 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "
); return; } BinaryTreeInOrder(root->_left); printf("%d ", root->_data);
BinaryTreeInOrder(root->_right); }
* 后序 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf(
"NULL "); return; } BinaryTreePostOrder(root->_left); printf("%d ", root->_data)
; BinaryTreePostOrder(root->_right); }
<>二叉树的遍历
<>遇到的问题
*
函数调用出错了，函数名写错了或参数写错了。
*
0XFFF,总之是节点不存在。
后来检查发现，是我调用create函数出错了，在头文件.h中的函数和实现的函数名不一样。
*
有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); }
<>关于树的知识
树的表示法和代码：
// 静态地定义度为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; } }
并查集是多棵树组成的数据结构