二叉树链式结构的实现和二叉树的遍历以及判断完全二叉树
二叉树的实现
定义结构体
我们首先定义一个结构来存放二叉树的节点
结构体里分别存放左子节点和右子节点以及节点存放的数据
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
构造一个二叉树
我们首先定义一个新建新节点的函数，方便构造二叉树
BTNode* buynode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc");
return NULL;
}
node->data = x;
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);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node2->right= node7;//满二叉树
return node1;
}
返回二叉树节点个数
这里有两种方法：
一种是遇到空节点直接返回，否则size++，然后再递归使用左节点和右节点，这种方法就做计数
第二种是直接递归使用左节点加右节点+1，这种方法更加简洁，但是可读性没有第一种方法这么好
int BinaryTreeSize(BTNode* root)
{
//static size = 0;
//if (root == NULL)
// return;
//size++;
//BinaryTreeSize(root->left);
//BinaryTreeSize(root->right);
//return size;
if (root == NULL)
return 0;
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
返回二叉树叶子节点个数
叶子节点就是没有孩子，即左节点和右节点都为空
当根节点root为空时直接返回0，当左节点left和右节点right都为空是就返回1，然后递归root的左节点和右节点相加，最后返回的就是叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
返回二叉树第k层节点个数
这里的二叉树根节点是第一层
首先k必须大于0，进行断言
如果根节点为空就直接返回0
如果k为1，就只有根节点一个节点，返回1
再递归左子树的k-1和右子树的k-1层节点数相加就是第k层的节点数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
二叉树查找值为x的节点
查找节点其实大家都有误区
例如：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BinaryTreeFind(root->left, x);
BinaryTreeFind(root->right, x);
}
但是这种情况下如果没有这个节点怎么办呢
所以这是错误滴
正确的在下面：
我们申请空间分别存放递归后左节点和右节点的返回值，如果不为空就返回
如果到最后还没有返回值就是二叉树中没有这个节点，直接返回空
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* node1 = BinaryTreeFind(root->left, x);
if (node1)
return node1;
BTNode* node2 = BinaryTreeFind(root->right, x);
if (node2)
return node2;
return NULL;
}
二叉树的销毁
很简单，但是记得手动置空
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);//为了防止出现野指针，需要使用者自己手动置空，即root==Null
}
求二叉树的高度
其实而二叉树的高度就是层数，我们只要计算层数最多的分支即可
如果左子树大于右子树就返回左子树的递归结果+1，右子树反之
大家看一下下面这段代码
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right) ? BinaryTreeHeight(root->left) + 1 : BinaryTreeHeight(root->right) + 1;
}
上面这段代码是有问题的，他没有将其记录下来，就回返回很多次去查询数据，导致超出时间限制
下面这段代码给出了解决的办法
记录即可
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftheight = BinaryTreeHeight(root->left);
int rightheight = BinaryTreeHeight(root->right);
return leftheight > rightheight ? leftheight + 1 : rightheight+1;
}
二叉树的遍历
前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
前序、中序以及后序遍历的实现
这三个遍历很简单，难得是层序遍历
前序就是先访问根节点，然后左子树右子树，用递归解决即可
前序
void BinaryTreePrevOrder(BTNode* root)
{
if (root)
{
putchar(root->_data);
BinaryTreePrevOrder(root->_left);
BinaryTreePrevOrder(root->_right);
}
}
中序
void BinaryTreeInOrder(BTNode* root)
{
if (root)
{
BinaryTreeInOrder(root->_left);
putchar(root->_data);
BinaryTreeInOrder(root->_right);
}
}
后序
void BinaryTreePostOrder(BTNode* root)
{
if (root)
{
BinaryTreePostOrder(root->_left);
BinaryTreePostOrder(root->_right);
putchar(root->_data);
}
}
层序遍历的实现
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
看图理解即可：
访问顺序是
A B C D E F G
层序遍历得实现其实要用到队列：
上图给了一个解释，大家可以研究研究
void BinaryTreeLevelOrder(BTNode* root)
{
Queue qu;
BTNode * cur;
QueueInit(&qu);
//首先压入根节点
QueuePush(&qu, root);
//循环的终止条件就是当队列为空时，此时二叉树层序遍历完成
while (!QueueIsEmpty(&qu))
{
//第一次进入循环时cur为队列的队首，即根节点
cur = QueueTop(&qu);
putchar(cur->data);
//当cur的左不为空是入队列
if (cur->left)
{
QueuePush(&qu, cur->left);
}
//当cur的右不为空是入队列
if (cur->right)
{
QueuePush(&qu, cur->right);
}
//删除此时的队首元素，并返回打印
QueuePop(&qu);
}
QueueDestory(&qu);
}
二叉树是否为完全二叉树
判断是否未完全二叉树的条件是什么呢
就是层序遍历完成时中间有无空节点！
我们首先将根节点压入队列
然后再将队列队首元素删除返回后，判断队首元素是否为空，为空则跳出while循环，就当他是个完全二叉树的所有节点已经全部压入
如果不是空就将左子树和右子树的根节点压入
然后我们再用层序遍历来判断后面是否有非空节点，如果有的话就不是完全二叉树，return false
否则是完全二叉树
看图分析即可：
bool 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;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//检查后面是否有非空节点，有非空就是非完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
好了，本文到此结束，感谢大家的支持！