当前位置：首页 > news >正文

二叉树的初步学习

news 来源：原创 2025/9/6 12:59:57

前言

对于二叉树的学习不想其他数据结构一样，直接学习他的结构的构建。单纯的一个二叉树在实际中没什么作用，除非是加了限制条件的，比如大名鼎鼎的红黑树。但是对于初学者而言，刚开始就学习红黑树，会让你刚接触就想放弃。难度太大了。所以，对于新手学习二叉树，学习的是他的遍历和搜索功能。

正文

对于二叉树的学习，一种是堆结构，它适用于完全二叉树，底层一般是数组，但是局限性就是适用于堆结构；还有一种就是链式结构，左孩子右父亲，他几乎适用于所有的二叉树，但是要记住单纯的二叉树没有什么实际作用。我们这里介绍的是第二种。

简单构建与销毁

虽然我们这里不学习他的构建，但是我们还是要简单搭建一下，帮助我们学习他的遍历与搜索。最后也要把他销毁，有始有终，不能只管生不管养。

构建

//构建
typedef int BTDataType;
typedef struct TreeNode
{BTDataType data;struct TreeNode* left;struct TreeNode* right;
}BTNode;
BTNode* CreateNode(BTDataType data)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = data;node->left = NULL;node->right = NULL;return node;}
//手搓二叉树
BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);BTNode* node8 = BuyNode(8);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;//node3->left = node7;//node7->left = node8;return node1;
}

销毁

//一级指针 使用这自己置空
void BTNDestroy(BTNode* root)
{if(root == NULL){return;}BTNDestroy(root->left);BTNDestroy(root->right);free(root);
}

这里销毁二叉树也可以用二级指针，用二级指针就可以直接置空。

四大遍历

这里的前序中序后序采用的都是递归思路，层序采用的是队列结构

前序遍历（根左子树右子树）

这里的递归展开图，建议自己去画画，可以加深你的理解。中序和后序和这里是一样的。我就不画图啦

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

中序遍历（左子树根右子树）

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

后序遍历（左子树右子树根）

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

层序遍历

这里的层序遍历需要使用一个队列，先进先出的特点非常适合这里的层序遍历，这里我是用的是c语言，直接手搓了一个队列。如果是c++的话，就可以直接调用库函数的。

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!(QueueEmpty(&q))){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

搜索与查询

这里大部分的查询都是递归，如果和层序有关的一般就会适用于队列

求第k层的节点数

//求第k层的节点数
//树的第k层节点个数 = 左子树的k-1层个数 + 右子树的k-1层个数
int TreeLevel(BTNode* root, int k)
{assert(k > 0);if (root == nullptr){return 0;}if (k == 1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}

查询值为x的节点

这里思路还是递归，采用分支思想，从上开始往下比。

//查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == nullptr){return nullptr;}if (root->data == x){return root;}BTNode* lret = BinaryTreeFind(root->left, x);if (lret){return lret;}BTNode* rret = BinaryTreeFind(root->right, x);if (rret){return rret;}return nullptr;
}

查询二叉树的高度/深度

这里递归的思路，不要过于追求简介，要保存上次递归得到的高度，否则你每次查看你的高度都要重新递归一遍，这是很恐怖的，爆炸式增长。

//天坑写法
// 这里要执行的次数可不是简单的几次，每次返回值获取的时候都要重新递归一遍
// 最底层的员工要执行2^n次，这是个非常恐怖的时间复杂度 爆炸式增长
// 所以，写代码的时候不要过度追求三目操作符 外行人看来很酷 内行人看你就像看杀马特一样
//int TreeHeight(BTNode* root)
//{
//	if (root == nullptr)
//	{
//		return 0;
//	}
//	return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
//}
int TreeHeight(BTNode* root)
{if (root == nullptr){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

查询二叉树的节点数

这里的递归思路是，让最底层的节点干活，就像一个学校汇报人数一样，校长让教导主任干，教导主任让班主任干，层层递进。

//这里求size比较挫的法子是多弄一个参数 或者全局变量
//int size = 0;
//void TreeSize(BTNode* root)
//{
//	if (root == nullptr)
//	{
//		return;
//	}
//	size++;
//	TreeSize(root->left);
//	TreeSize(root->right);
//}
//优秀的解放 分治
int TreeSize(BTNode* root)
{return root == nullptr ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

判断一个二叉树是否是完全二叉树

这里的思路不是递归，是采用队列层序遍历节点，如果遇到空节点，就退出循环，开始判断剩余的队列是否还有非空节点，如果有那就不是完全二叉树，反之，就是完全二叉树。这里的队列完全适合了完全二叉树的特性

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}//判断是否是while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return 0;}}return 1;QueueDestroy(&q);
}

总结

二叉树的学习会用到大量的递归，这里也是练习递归的一个很好的章节。也许你可能会感到使用递归有点困难。这是因为你还没有理会到递归的精髓。这里实际上使用递归解决这些遍历是很简单的，如果使用非递归解决二叉树的问题，那才是真正的上难度了。

前言

正文