二叉树操作与遍历实现

二叉树操作与遍历实现

在数据结构的学习中，二叉树是一个极其重要的概念。它不仅具有丰富的理论基础，还在实际应用中扮演着关键角色。本文将通过一段C语言代码，详细解析二叉树的创建、遍历、销毁以及一些基本操作的实现。

树的相关概念

1.树的相关术语

⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的⽗结点
⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点
结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0
树的度：⼀棵树中，最⼤的结点的度称为树的度；如上图：树的度为 6
叶⼦结点/终端结点：度为 0 的结点称为叶结点；如上图： B、C、H、I… 等结点为叶结点
分⽀结点/⾮终端结点：度不为 0 的结点；如上图： D、E、F、G… 等结点为分⽀结点
兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；
树的⾼度或深度：树中结点的最⼤层次；如上图：树的⾼度为 4
结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q
⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
森林：由 m（m>0） 棵互不相交的树的集合称为森林；

2.二叉树的概念

在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
特点：

1. ⼆叉树不存在度⼤于 2 的结点

2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

3. 对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

特殊二叉树：
满二叉树：⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为K，且结点总数是2的k次-1，就是满二叉树。完全二叉树：完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

3.二叉树的存储结构

1.顺序结构

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

2.链式结构

⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩 。

1. 二叉树的创建

树的表示

typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

1.1 创建节点

在创建二叉树之前，我们首先需要定义一个函数来创建单个节点。以下是buyNode函数的代码：

BTNode* buyNode(BTDataType x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->_data = x;root->_left = root->_right = NULL;
}

这个函数的作用是分配一块内存空间给一个新的节点，并将传入的数据x赋值给节点的_data成员，同时初始化左右子节点指针为NULL。

1.2 构建二叉树

接下来，我们通过BinaryTreeCreate函数来构建一个具体的二叉树。代码如下：

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');BTNode* nodeH = buyNode('H');BTNode* nodeG = buyNode('G');nodeA->_left = nodeB;nodeA->_right = nodeC;nodeB->_left = nodeD;nodeB->_right = nodeE;nodeE->_right = nodeH;nodeC->_left = nodeF;nodeC->_right = nodeG;return nodeA;
}

在这个函数中，我们手动创建了若干个节点，并通过指定左右子节点的方式，构建了一个具有特定结构的二叉树。例如，nodeA作为根节点，其左子节点是nodeB，右子节点是nodeC，以此类推。

2. 二叉树的销毁

为了避免内存泄漏，我们需要在二叉树不再使用时释放其占用的内存。以下是BinaryTreeDestory函数的代码：

void BinaryTreeDestory(BTNode** root)
{if (*root == NULL)return;BinaryTreeDestory((*root)->_left);BinaryTreeDestory((*root)->_right);free(*root);*root = NULL;
}

这个函数采用递归的方式，先销毁左右子树，然后释放当前节点的内存，并将指针置为NULL。

3. 二叉树的遍历

3.1 前序遍历

前序遍历的顺序是：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。以下是BinaryTreePrevOrder函数的代码：

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

3.2 中序遍历

中序遍历的顺序是：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。以下是BinaryTreeInOrder函数的代码：

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

3.3 后序遍历

后序遍历的顺序是：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。以下是BinaryTreePostOrder函数的代码：

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

3.4 层序遍历

用到了队列的相关知识
层序遍历是按照从上到下、从左到右的顺序依次访问二叉树的节点。以下是BinaryTreeLevelOrder函数的代码：

void BinaryTreeLevelOrder(BTNode* root)
{if (root == NULL)return;Queue* pq;QueueInit(pq);QueuePush(pq, root);while (!QueueEmpty(pq)){BTNode* top = QueueFront(pq);printf("%c ", top->_data);QueuePop(pq);if (top->_left)QueuePush(pq, top->_left);if (top->_right)QueuePush(pq, top->_right);}QueueDestroy(pq);
}

这个函数借助队列来实现层序遍历。首先将根节点入队，然后在队列不为空的情况下，依次出队一个节点并访问其值，接着将该节点的左右子节点依次入队。

4. 二叉树的其他操作

4.1 节点个数

BinaryTreeSize函数用于计算二叉树的节点个数。代码如下：

int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
}

这个函数通过递归的方式，分别计算左右子树的节点个数，然后加上当前节点的1，最终得到整棵树的节点总数。

4.2 叶子节点个数

BinaryTreeLeafSize函数用于计算二叉树的叶子节点个数。代码如下：

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);
}

这个函数同样采用递归的方式。如果当前节点是叶子节点（即左右子节点都为NULL），则返回1；否则，分别计算左右子树的叶子节点个数并相加。

4.3 第k层节点个数

BinaryTreeLevelKSize函数用于计算二叉树第k层的节点个数。代码如下：

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 0)return 1;return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

这个函数通过递归的方式，逐层向下遍历。当到达第k层时（k == 0），返回1；否则，分别计算左右子树在第k - 1层的节点个数并相加。

4.4 查找节点

BinaryTreeFind函数用于在二叉树中查找值为x的节点。代码如下：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;if(BinaryTreeFind(root->_left, x) != NULL)return BinaryTreeFind(root->_left, x);if (BinaryTreeFind(root->_right, x) != NULL)return BinaryTreeFind(root->_right, x);return NULL;
}

这个函数采用递归的方式，先判断当前节点是否为目标节点，如果不是，则分别在左右子树中递归查找。

4.5 判断是否为完全二叉树

用到了队列的相关知识
BinaryTreeComplete函数用于判断二叉树是否是完全二叉树。代码如下：

bool BinaryTreeComplete(BTNode* root)
{if (root == NULL)return;Queue* pq;QueueInit(pq);QueuePush(pq, root);while (!QueueEmpty(pq)){BTNode* top = QueueFront(pq);QueuePop(pq);if (top == NULL){break;}QueuePush(pq, top->_left);QueuePush(pq, top->_right);}while (!QueueEmpty(pq)){BTNode* top = QueueFront(pq);QueuePop(pq);if (top != NULL)return false;}return true;QueueDestroy(pq);
}

这个函数借助队列进行层序遍历。在遍历过程中，如果遇到第一个NULL节点后，后续队列中仍存在非NULL节点，则说明该树不是完全二叉树。

总结

本文通过代码详细介绍了二叉树的创建、遍历、销毁以及一些其他操作的实现。二叉树是一种非常重要的数据结构，在计算机科学中有广泛的应用，如表达式树、决策树等。掌握二叉树的操作对于学习数据结构和算法非常重要