• 数据结构·二叉树

    目录

    续上篇 -- 数据结构·堆·完全二叉树

    二叉树的性质

    再次认知二叉树

    二叉树的遍历

    附上队列的实现

    Queue.c

    Queue.h

    Test.c

    解析一 

    解析二 

    解析三 

    深度优先与广度优先

    关于二叉树的一些oj题目

    965. 单值二叉树

    100. 相同的树

    572. 另一棵树的子树

    144. 二叉树的前序遍历

    94. 二叉树的中序遍历

    145. 二叉树的后序遍历

    KY11 二叉树遍历

    101. 对称二叉树

    结束语 

    续上篇 -- 数据结构·堆·完全二叉树

    二叉树的性质

    几个关于性质的题目

    1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为（ ）
    A 不存在这样的二叉树
    B 200
    C 198
    D 199
    2. 下列数据结构中，不适合采用顺序存储结构的是（ ）
    A 非完全二叉树
    B 堆
    C 队列
    D 栈
    3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
    A n
    B n+1
    C n-1
    D n/2
    4. 一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（ ）
    A 11
    B 10
    C 8
    D 12
    5. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）
    A 383
    B 384
    C 385
    D 386
    答案 -- 选择查看
    1.B  -- 根据性质第3条很容易得出 -- 叶子指的是度为0结点
    2.A  -- 这里的队列其实也不应该使用顺序存储，但是相比A来说就离谱了 -- 看补图
    3.A  -- 2n就一定是非满二叉树了，所以有一个度为1的结点，再利用性质3可以得出 
    4.B  -- 对于高度h的计算公式：2^(h-1) <= N <= 2^h-1 
    5.B  -- 根据二叉树的性质这个一定是满二叉树,所以没有度为1的结点,再利用性质3可以得出 

    对于2的补图

    再次认知二叉树

    基于上述才可以引入 二叉树的遍历 这一概论

    二叉树的遍历

    学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

    按照规则，二叉树的遍历有： 前序 / 中序 / 后序的递归结构遍历 ：
    1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
    2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。
    3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。

    根 左子树 右子树             -- 1概述

    左子树 根 右子树             -- 2概述

    左子树 右子树 根             -- 3概述

    为了后续更好的理解二叉树的实现，下面写一个简单的只遍历的测试用例

    附上队列的实现

    数据结构·栈与队列介绍与实现

    Queue.c

    1. #include "Queue.h"
    2.  
    3. //初始化  -- 到现在有三种不用二级指针来初始化结构体了 返回值、头节点
    4. void QueueInit(Queue* pq)
    5. {
    6. 	assert(pq);	//因为这里是自己创立的节点是不可能为空的，为空就是出问题了
    7. 	pq->head = pq->tail = NULL;
    8. 	pq->size = 0;
    9. }
    10.  
    11. //销毁
    12. void QueueDestroy(Queue* pq)
    13. {
    14. 	assert(pq);
    15. 	QNode* cur = pq->head;
    16. 	while (cur)
    17. 	{
    18. 		QNode* del = cur;
    19. 		cur = cur->next;
    20. 		free(del);
    21. 	}
    22.  
    23. 	pq->head = pq->tail = NULL;	//要改变什么就需要什么的指针，这里置空就可以了
    24. }
    25.  
    26. //入队列 -- 根据队列的性质 只尾插
    27. void QueuePush(Queue* pq, QDataType x)
    28. {
    29. 	assert(pq);
    30. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    31. 	if (newnode == NULL)
    32. 	{
    33. 		perror("malloc fail");
    34. 		exit(-1);
    35. 	}
    36. 	else
    37. 	{
    38. 		newnode->data = x;
    39. 		newnode->next = NULL;	//这里置空，下面就不需要置空了
    40. 	}
    41.  
    42. 	if (pq->tail == NULL)
    43. 	{
    44. 		pq->head = pq->tail = newnode;
    45. 	}
    46. 	else
    47. 	{
    48. 		pq->tail->next = newnode;
    49. 		pq->tail = newnode;
    50. 	}
    51.  
    52. 	pq->size++;
    53. }
    54.  
    55. //出队列 -- 根据队列的性质 只头删
    56. void QueuePop(Queue* pq)
    57. {
    58. 	assert(pq);
    59. 	assert(!QueueEmpty(pq));
    60.  
    61. 	if (pq->head->next == NULL)	//防止只剩下一个节点时候再删，就会导致野指针
    62. 	{
    63. 		free(pq->head);
    64. 		pq->tail = pq->head = NULL;
    65. 	}
    66. 	else
    67. 	{
    68. 		QNode* del = pq->head;
    69. 		pq->head = pq->head->next;
    70.  
    71. 		free(del);
    72. 		del = NULL;
    73. 	}
    74.  
    75. 	pq->size--;
    76. }
    77.  
    78. //查看头
    79. QDataType QueueFront(Queue* pq)
    80. {
    81. 	assert(pq);
    82. 	assert(!QueueEmpty(pq));
    83.  
    84. 	return pq->head->data;
    85. }
    86.  
    87. //查看尾
    88. QDataType QueueBack(Queue* pq)
    89. {
    90. 	assert(pq);
    91. 	assert(!QueueEmpty(pq));
    92.  
    93. 	return pq->tail->data;
    94. }
    95.  
    96. //判断是否为空
    97. bool QueueEmpty(Queue* pq)
    98. {
    99. 	assert(pq);
    100.  
    101. 	return pq->head == NULL && pq->tail == NULL; //理论上两个都应该为空才为空，一般一个为空就都会为空，不是就出问题了
    102. }
    103.  
    104. //查看节点长度
    105. int QueueSize(Queue* pq)
    106. {
    107. 	assert(pq);
    108.  
    109. 	//这样写就变为O(N)级别了 为此需要稍作修改
    110. 	//QNode* cur = pq->head;
    111. 	//int n = 0;
    112. 	//while (cur)
    113. 	//{
    114. 	//	++n;
    115. 	//	cur = cur->next;
    116. 	//}
    117.  
    118. 	//return n;
    119.  
    120. 	return pq->size;
    121. }

    Queue.h

    1. #pragma once
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8.  
    9.  
    10.  
    11. typedef int BTDataType;
    12. typedef struct BinaryTreeNode
    13. {
    14. 	BTDataType data;
    15. 	struct BinaryTreeNode* left;
    16. 	struct BinaryTreeNode* right;
    17. }BTNode;
    18.  
    19.  
    20. //能用单链表解决问题就可以用单链表 -- 没必要使用双向循环链表，这属于有点小题大做了
    21.  
    22. //用C写的话就得把 -- 之前写的队列用上
    23. typedef BTNode* QDataType;
    24. typedef struct QueueNode
    25. {
    26. 	struct QueueNode* next;
    27. 	QDataType data;
    28. }QNode;
    29.  
    30. //再定义一个节点来存放两个指针，方便后面操作
    31. typedef struct Queue
    32. {
    33. 	//尾指针
    34. 	QNode* tail;
    35. 	//头指针
    36. 	QNode* head;
    37. 	int size;
    38. }Queue;
    39.  
    40. //初始化  -- 到现在有三种不用二级指针来初始化结构体了 返回值、哨兵位的头节点和这里的创立一个新的结构体放俩这种
    41. void QueueInit(Queue* pq);
    42.  
    43. //销毁
    44. void QueueDestroy(Queue* pq);
    45.  
    46. //入队列 -- 根据队列的性质 只尾插
    47. void QueuePush(Queue* pq,QDataType x);
    48.  
    49. //出队列 -- 根据队列的性质 只头删
    50. void QueuePop(Queue* pq);
    51.  
    52. //查看头
    53. QDataType QueueFront(Queue* pq);
    54.  
    55. //查看尾
    56. QDataType QueueBack(Queue* pq);
    57.  
    58. //判断是否为空
    59. bool QueueEmpty(Queue* pq);
    60.  
    61. //查看节点长度
    62. int QueueSize(Queue* pq);

    Test.c

    1. #include 
    2. #include 
    3. #include 
    4. #include "Queue.h"
    5.  
    6. //typedef int BTDataType;
    7. //typedef struct BinaryTreeNode
    8. //{
    9. //	BTDataType data;
    10. //	struct BinaryTreeNode* left;
    11. //	struct BinaryTreeNode* right;
    12. //}BTNode;
    13.  
    14.  
    15. // 二叉树前序遍历
    16. void PreOrder(BTNode* root)
    17. {
    18. 	if (root == NULL)
    19. 	{
    20. 		printf("NULL ");
    21. 		return;
    22. 	}
    23. 	printf("%d ", root->data);
    24. 	PreOrder(root->left);
    25. 	PreOrder(root->right);
    26. }
    27. // 二叉树中序遍历
    28. void InOrder(BTNode* root)
    29. {
    30. 	if (root == NULL)
    31. 	{
    32. 		printf("NULL ");
    33. 		return;
    34. 	}
    35. 	InOrder(root->left);
    36. 	printf("%d ", root->data);
    37. 	InOrder(root->right);
    38. }
    39. // 二叉树后序遍历
    40. void PostOrder(BTNode* root)
    41. {
    42. 	if (root == NULL)
    43. 	{
    44. 		printf("NULL ");
    45. 		return;
    46. 	}
    47. 	PostOrder(root->left);
    48. 	printf("%d ", root->data);
    49. 	PostOrder(root->right);
    50. }
    51. //会发现其实遍历的代码很简单，只是理解起来要复杂
    52.  
    53.  
    54. //遍历计算的思路
    55. //int count = 0;
    56. //void TreeSize_1(BTNode* root)
    57. //{
    58. //	if (root == NULL)
    59. //		return;
    60. //
    61. //	++count;
    62. //	TreeSize_1(root->left);
    63. //	TreeSize_1(root->right);
    64. //
    65. //	return;
    66. //}
    67.  
    68. //层序遍历 -- 用C的方法就得用到队列 -- 解析二
    69. void TreeLevelOrder(BTNode* root)
    70. {
    71. 	Queue q;
    72. 	QueueInit(&q);
    73. 	
    74. 	if (root)
    75. 		QueuePush(&q, root);	//QueueNode* 里面包含一个BTNode*的指针
    76.  
    77. 	while (!QueueEmpty(&q))
    78. 	{
    79. 		BTNode* front = QueueFront(&q);
    80. 		QueuePop(&q);
    81. 		printf("%d ", front->data);
    82.  
    83. 		//下一层入队列
    84. 		if(front->left)
    85. 			QueuePush(&q, front->left);
    86. 		if (front->right)
    87. 			QueuePush(&q, front->right);
    88. 	}
    89. 	printf("\n");
    90.  
    91. 	QueueDestroy(&q);
    92. }
    93.  
    94.  
    95.  
    96. //二叉树的结点数 -- 切割子问题的思路
    97. int TreeSize(BTNode* root)
    98. {
    99. 	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
    100. 	//解释起来就是：左子树 + 右子树 + 根
    101. }
    102.  
    103. //二叉树的叶子结点数
    104. int TreeLeafSize(BTNode* root)
    105. {
    106. 	if (root == NULL)
    107. 		return 0;
    108. 	if (root->left == NULL && root->right == NULL)
    109. 		return 1;
    110.  
    111. 	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
    112. }
    113.  
    114. //二叉树的高度 -- 解析一
    115. int TreeHeight(BTNode* root)
    116. {
    117. 	if (root == NULL)
    118. 		return 0;
    119.  
    120. 	int lh = TreeHeight(root->left);
    121. 	int rh = TreeHeight(root->right);
    122.  
    123. 	return	lh > rh ? lh + 1 : rh + 1;
    124. }
    125.  
    126. //第k层节点个数
    127. int TreeKlevel(BTNode* root, int k)
    128. {
    129. 	assert(k > 0);
    130.  
    131. 	if (root == NULL)
    132. 		return 0;
    133. 	if (k == 1)
    134. 		return 1;
    135.  
    136. 	//转化成求子树第k-1层
    137. 	return TreeKlevel(root->left, k-1) + TreeKlevel(root->right, k-1);
    138. }
    139.  
    140. //返回x所在的节点
    141. BTNode* TreeFind(BTNode* root, BTDataType x)
    142. {
    143. 	if (root == NULL)
    144. 		return NULL;
    145. 	if (root->data == x)
    146. 		return root;
    147.  
    148. 	BTNode* lret = TreeFind(root->left, x);
    149. 	if (lret)
    150. 		return lret;
    151. 	BTNode* rret = TreeFind(root->right, x);
    152. 	if (rret)
    153. 		return rret;
    154.  
    155. 	return NULL;
    156. }
    157.  
    158.  
    159. //判断是否为完全二叉树 -- 利用队列的方法
    160. int BinaryTreeComplete(BTNode* root)
    161. {
    162. 	Queue q;
    163. 	QueueInit(&q);
    164.  
    165. 	if (root)
    166. 		QueuePush(&q, root);	//QueueNode* 里面包含一个BTNode*的指针
    167.  
    168. 	while (!QueueEmpty(&q))
    169. 	{
    170. 		BTNode* front = QueueFront(&q);
    171. 		QueuePop(&q);
    172.  
    173. 		//遇到空就跳出循环 -- 解析3
    174. 		if (front == NULL)
    175. 			break;
    176.  
    177. 		QueuePush(&q, front->left);
    178. 		QueuePush(&q, front->right);
    179. 	}
    180. 	
    181. 	//遇到空以后，后面全是空，则是完全二叉树
    182. 	//遇到空以后，后面存在非空，则不是完全二叉树
    183. 	while (!QueueEmpty(&q))
    184. 	{
    185. 		BTNode* front = QueueFront(&q);
    186. 		QueuePop(&q);
    187.  
    188. 		//遇到空就跳出循环 -- 解析3
    189. 		if (front != NULL)
    190. 		{
    191. 			QueueDestroy(&q);
    192. 			return false;
    193. 		}
    194.  
    195. 	}
    196.  
    197. 	QueueDestroy(&q);
    198. 	return true;
    199. }
    200.  
    201.  
    202. BTNode* CreateTree()
    203. {
    204. 	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    205. 	assert(n1);
    206. 	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    207. 	assert(n2);
    208. 	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    209. 	assert(n3);
    210. 	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    211. 	assert(n4);
    212. 	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    213. 	assert(n5);
    214. 	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    215. 	assert(n6);
    216. 	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
    217. 	assert(n7);
    218.  
    219. 	n1->data = 1;
    220. 	n2->data = 2;
    221. 	n3->data = 3;
    222. 	n4->data = 4;
    223. 	n5->data = 5;
    224. 	n6->data = 6;
    225.  
    226. 	//为测试高度添加的一个结点
    227. 	n7->data = 7;
    228.  
    229. 	n1->left = n2;
    230. 	n1->right = n4;
    231. 	n2->left = n3;
    232. 	n2->right = NULL;
    233. 	n4->left = n5;
    234. 	n4->right = n6;
    235. 	n3->left = NULL;
    236. 	n3->right = NULL;
    237. 	n5->left = NULL;
    238. 	n5->right = NULL;
    239. 	n6->left = NULL;
    240. 	n6->right = NULL;
    241.  
    242. 	//为测试高度添加的一个结点
    243. 	n3->right = n7;
    244. 	n7->left = NULL;
    245. 	n7->right = NULL;
    246.  
    247. 	return n1;
    248. }
    249.  
    250.  
    251. //二叉树的销毁 -- 后序销毁
    252. void BinaryTreeDestroy(BTNode* root)
    253. {
    254. 	//当左右子树都为空时就释放
    255. 	if (root == NULL)
    256. 		return;
    257.  
    258. 	BinaryTreeDestroy(root->left);
    259. 	BinaryTreeDestroy(root->right);
    260. 	free(root);
    261. }
    262.  
    263. int main()
    264. {
    265. 	BTNode* root = CreateTree();
    266. 	//前序遍历
    267. 	PreOrder(root);
    268. 	printf("\n");
    269.  
    270. 	//中序遍历
    271. 	InOrder(root);
    272. 	printf("\n");
    273.  
    274. 	//后序遍历
    275. 	PostOrder(root);
    276. 	printf("\n");
    277.  
    278. 	//遍历计算
    279. 	//先归零再计算，因为是全局变量
    280. 	//count = 0;	
    281. 	//TreeSize_1(root);
    282. 	//printf("Tree size:%d\n", count);
    283.  
    284. 	//结点数
    285. 	printf("Tree size:%d\n", TreeSize(root));
    286.  
    287. 	//叶子数
    288. 	printf("Tree Leaf size:%d\n", TreeLeafSize(root));
    289.  
    290. 	//高度
    291. 	printf("Tree Height size:%d\n", TreeHeight(root));
    292.  
    293. 	//第k层节点个数
    294. 	printf("Tree K Level:%d\n", TreeKlevel(root, 4));
    295.  
    296. 	//返回x所在的节点
    297. 	printf("Tree Find:%p\n", TreeFind(root, 7));
    298. 	//有了节点的地址可以改该节点的值
    299. 	BTNode* p = TreeFind(root, 7);
    300. 	p->data *= 10;
    301. 	//前序遍历
    302. 	PreOrder(root);
    303. 	printf("\n");
    304.  
    305. 	//层序遍历
    306. 	TreeLevelOrder(root);
    307.  
    308. 	//判断是否为完全二叉树 -- true 与 false 本质上就是1与0
    309. 	printf("Tree BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
    310.  
    311. 	//因为里面没有实现置空，所以在外部需要置空 -- 要实现置空得使用二级指针
    312. 	BinaryTreeDestroy(root);
    313. 	root = NULL;
    314.  
    315. 	return 0;
    316. }

     

    结果与前面分析是一致的 

    解析一 

    分析高度的递归路线

    其他的递归路线大同小异，画图便自然理解

    解析二 

    分析层序遍历 -- 利用队列的方法去实现

     

    解析三 

    完全二叉树与非完全二叉树的解析 

    深度优先与广度优先

    DFS -- 深度优先遍历

    前序遍历 -- 遍历顺序和访问数据都符合

    中序遍历 -- 遍历符合

    后序遍历 -- 遍历符合

    递归先往深走，遇到不满足条件再往回退，走其他分支路径 -- 往一个方向走

    BFS -- 广度优先遍历

    层序遍历 

    关于二叉树的一些oj题目

    965. 单值二叉树

    965. 单值二叉树 -- leetcode链接

    递归解决 -- 让子树去比较

    1. bool isUnivalTree(struct TreeNode* root){
    2.     if(root == NULL)
    3.         return true;
    4.     if(root->left && root->val != root->left->val)
    5.         return false;
    6.     if(root->right && root->val != root->right->val)
    7.         return false;
    8.  
    9.     return isUnivalTree(root->left) && isUnivalTree(root->right);
    10. }

    100. 相同的树

    100. 相同的树  -- -- leetcode链接

    1. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    2.     
    3.     if(p == NULL && q == NULL)
    4.         return true;
    5.     if(p == NULL || q == NULL)
    6.         return false;
    7.     if(p->val != q->val)
    8.         return false;
    9.     return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    10. }

    572. 另一棵树的子树

    572. 另一棵树的子树  -- leetcode链接

    上面一题刚好可以为下面一题服务 

    1. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    2.     
    3.     if(p == NULL && q == NULL)
    4.         return true;
    5.     if(p == NULL || q == NULL)
    6.         return false;
    7.     if(p->val != q->val)
    8.         return false;
    9.     return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    10. }
    11.  
    12.  
    13. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    14.     if(root == NULL)
    15.         return false;
    16.  
    17.     if(isSameTree(root,subRoot))
    18.         return true;
    19.  
    20.     return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
    21.  
    22. }

    144. 二叉树的前序遍历

    144. 二叉树的前序遍历  -- -- leetcode链接

    1. //查看节点数
    2. int TreeSize(struct TreeNode* root)
    3. {
    4.     if(root == NULL)
    5.         return 0;
    6.     return TreeSize(root->left) + TreeSize(root->right) + 1;
    7. }
    8.  
    9. //前序遍历
    10. void preorder(struct TreeNode* root, int* a, int* pi)
    11. {
    12.     if(root == NULL)
    13.         return;
    14.     
    15.     a[*pi] = root->val;
    16.     (*pi)++;
    17.  
    18.     preorder(root->left, a, pi);
    19.     preorder(root->right, a, pi);
    20. }
    21.  
    22. int* preorderTraversal(struct TreeNode* root, int* returnSize){
    23.     
    24.     int n = TreeSize(root);
    25.     int* a = (int*)malloc(sizeof(int)*n);
    26.  
    27.     int i = 0;
    28.     preorder(root, a, &i);
    29.     //这里是返回数组的大小，因为C不支持一次返回两个值，利用输出型参数可以解决
    30.     *returnSize = n;
    31.  
    32.     return a;
    33. }

    94. 二叉树的中序遍历

    94. 二叉树的中序遍历  -- leetcode链接

    1. //查看节点数
    2. int TreeSize(struct TreeNode* root)
    3. {
    4.     if(root == NULL)
    5.         return 0;
    6.     return TreeSize(root->left) + TreeSize(root->right) + 1;
    7. }
    8.  
    9. //中序遍历
    10. void preorder(struct TreeNode* root, int* a, int* pi)
    11. {
    12.     if(root == NULL)
    13.         return;
    14.     
    15.     preorder(root->left, a, pi);
    16.     a[*pi] = root->val;
    17.     (*pi)++;
    18.     preorder(root->right, a, pi);
    19. }
    20.  
    21. int* inorderTraversal(struct TreeNode* root, int* returnSize){
    22.     
    23.     int n = TreeSize(root);
    24.     int* a = (int*)malloc(sizeof(int)*n);
    25.  
    26.     int i = 0;
    27.     preorder(root, a, &i);
    28.     //这里是返回数组的大小，因为C不支持一次返回两个值，利用输出型参数可以解决
    29.     *returnSize = n;
    30.  
    31.     return a;
    32. }

    145. 二叉树的后序遍历

    145. 二叉树的后序遍历  -- leetcode链接

    1. //查看节点数
    2. int TreeSize(struct TreeNode* root)
    3. {
    4.     if(root == NULL)
    5.         return 0;
    6.     return TreeSize(root->left) + TreeSize(root->right) + 1;
    7. }
    8.  
    9. //后序遍历
    10. void preorder(struct TreeNode* root, int* a, int* pi)
    11. {
    12.     if(root == NULL)
    13.         return;
    14.     
    15.     preorder(root->left, a, pi);
    16.     preorder(root->right, a, pi);
    17.     a[*pi] = root->val;
    18.     (*pi)++;
    19. }
    20.  
    21. int* postorderTraversal(struct TreeNode* root, int* returnSize){
    22.     
    23.     int n = TreeSize(root);
    24.     int* a = (int*)malloc(sizeof(int)*n);
    25.  
    26.     int i = 0;
    27.     preorder(root, a, &i);
    28.     //这里是返回数组的大小，因为C不支持一次返回两个值，利用输出型参数可以解决
    29.     *returnSize = n;
    30.  
    31.     return a;
    32. }

    KY11 二叉树遍历

    二叉树遍历_牛客题霸_牛客网 (nowcoder.com) -- 题目链接

    1. #include 
    2. #include 
    3. #include 
    4. typedef char BTDataType;
    5. typedef struct BinaryTreeNode
    6. {
    7. 	BTDataType data;
    8. 	struct BinaryTreeNode* left;
    9. 	struct BinaryTreeNode* right;
    10. }BTNode;
    11.  
    12. //中序遍历
    13. void InOrder(BTNode* root)
    14. {
    15. 	if (root == NULL)
    16. 	{
    17. 		return;
    18. 	}
    19. 	InOrder(root->left);
    20. 	printf("%c ", root->data);
    21. 	InOrder(root->right);
    22. }
    23.  
    24. // 通过前序遍历的数组"abc##de#g##f###"构建二叉树
    25. BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
    26. {
    27.     if(a[*pi] == '#')
    28.     {
    29.          (*pi)++;
    30.          return NULL;
    31.     }
    32.        
    33.     
    34.     BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    35.     
    36.     root->data = a[*pi];
    37.     (*pi)++;
    38.     
    39.     root->left = BinaryTreeCreate(a, pi);
    40.     root->right = BinaryTreeCreate(a, pi);
    41.     
    42.     return root;
    43. }
    44.  
    45.  
    46. int main()
    47. {
    48.     char str[100] = {0};
    49.     scanf("%s",str);
    50.     
    51.     int i = 0;
    52.     BTNode* root =  BinaryTreeCreate(str, &i);
    53.     assert(root);
    54.     
    55.     InOrder(root);
    56.     
    57.     return 0;
    58. }

    101. 对称二叉树

    101. 对称二叉树  -- leetcode链接

    1. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    2.     
    3.     if(p == NULL && q == NULL)
    4.         return true;
    5.     if(p == NULL || q == NULL)
    6.         return false;
    7.     if(p->val != q->val)
    8.         return false;
    9.     return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
    10. }
    11.  
    12.  
    13. bool isSymmetric(struct TreeNode* root){
    14.     if(root == NULL)
    15.         return true;
    16.  
    17.     return isSameTree(root->left,root->right);
    18.     
    19. }

    根据另一棵树的子树改编过来

    结束语 

    兔子不吃窝边草，窝边有草何必满山跑
                                                                    ——俗语 

  • 相关阅读:
    让你的 Runner 可视化，使用 Prometheus + Grafana 实现极狐GitLab Runner 可视化
    NLP(自然语言处理)
    Linux 中 Find 命令的高级用法
    应届生仅凭啃透这份987页的Java面试宝典，一个月拿下美团面试官
    信息学奥赛一本通：1104：计算书费
    基于Java毕业设计短视频交流点播系统源码+系统+mysql+lw文档+部署软件
    1162 Postfix Expression
    炒股警钟长鸣
    为什么MySQL索引选择B+树而不使用B树？
    向量叉乘的几何意义及其模的计算
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126444692