数据结构——二叉树的实现

news/2024/10/21 6:38:18/

什么是二叉树？

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
在这里插入图片描述

1.通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

在这里插入图片描述
这段代码实现了根据前序遍历的数组构建二叉树的过程。其原理是通过递归实现的，对于当前节点，如果它是空节点或者数组已经遍历完，那么返回NULL，否则创建新节点并赋初值，然后递归构建左子树和右子树。具体实现如下：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{//如果数组已经遍历完或者当前节点是空节点，返回空指针if (*pi >= n || a[*pi] == '#'){//当前节点为空，返回NULL(*pi)++;return NULL;}//创建新节点并赋初值BTNode* root = new BTNode;root->_data = a[*pi];root->_left = NULL;root->_right = NULL;//递归构建左子树和右子树(*pi)++;root->_left = BinaryTreeCreate(a, n, pi);(*pi)++;root->_right = BinaryTreeCreate(a, n, pi);return root;
}

其中，a表示前序遍历的数组，n表示数组的长度，pi表示数组的当前位置。如果数组已经遍历完或者当前节点是空节点，那么返回空指针。否则，创建一个新节点，并将当前位置向后移动一位，然后递归构建左子树和右子树。最终返回根节点，即构建好的二叉树。

2.二叉树销毁

这段代码实现了二叉树的销毁过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则递归销毁左子树和右子树，最后释放当前节点的内存。具体实现如下：

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL)//如果当前节点为空，直接返回return;//递归销毁左子树和右子树BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));//释放当前节点的内存free(*root);*root = NULL;
}

其中，root表示当前节点的指针，如果当前节点为空，直接返回；否则递归销毁左子树和右子树，最后释放当前节点的内存，并将当前节点的指针设置为NULL。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，将每个节点释放，并将其左右子节点的内存全部释放。最终得到一个空的二叉树。

3.二叉树节点个数

在这里插入图片描述

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//如果当前节点为空返回0return 0;//返回左子树节点个数加上右节点个数再加上1（当前节点）return BinaryTreeSize(root->_left) +BinaryTreeSize(root->_right) + 1;
}

4.二叉树叶子节点个数

这段代码实现了计算二叉树节点个数的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回0；否则返回左子树节点个数加上右子树节点个数再加上1（当前节点）。具体实现如下：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//如果当前节点为空，返回0return 0;if (root->_left == NULL && root->_right == NULL){//如果当前节点是叶子节点，返回1return 1;}// 返回左子树叶子节点个数加上右子树叶子节点个数return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

其中，root表示当前节点，如果当前节点为空，直接返回0；否则递归计算左子树节点个数和右子树节点个数，最终返回左子树节点个数加上右子树节点个数再加上1（当前节点），即整棵二叉树的节点个数。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，并将每个节点的左右子树节点个数相加，最终得到整棵二叉树的节点个数。

5.二叉树第k层节点个数

这段代码实现了计算二叉树叶子节点个数的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回0；如果它是叶子节点，返回1；否则返回左子树叶子节点个数加上右子树叶子节点个数。具体实现如下：

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root==NULL)//如果当前节点为空，返回0return 0;if (k == 1)//如果当前节点是第k层节点，返回1return 1;// 返回左子树第 k-1 层节点个数加上右子树第 k-1 层节点个数int leftk = BinaryTreeLevelKSize(root->_left, k - 1);int rightk = BinaryTreeLevelKSize(root->_right, k - 1);return leftk + rightk;
}

其中，root表示当前节点，如果当前节点为空，直接返回0；如果当前节点是叶子节点，返回1；否则递归计算左子树叶子节点个数和右子树叶子节点个数，最终返回左子树叶子节点个数加上右子树叶子节点个数，即整棵二叉树的叶子节点个数。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，并将每个节点的左右子树叶子节点个数相加，最终得到整棵二叉树的叶子节点个数。

6.二叉树查找值为x的节点

这段代码实现了在二叉树中查找值为x的节点的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，返回NULL；如果它的值等于x，返回指向当前节点的指针；否则在左子树中查找x，如果找到了，返回指向左子树中x的节点的指针；否则在右子树中查找x，如果找到了，返回指向右子树中x的节点的指针；如果左右子树都没有找到，返回NULL。具体实现如下：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)//如果当前节点为空,返回NULLreturn 0;if (root->_data == x)//如果当前节点的值等于x，返回指向当前节点的指针return root;//在左子树中查找xBTNode* lret = BinaryTreeFind(root->_left, x);// 如果在左子树中找到了 x，返回指向左子树中 x 的节点的指针if (lret){return lret;}//在右子树中查找xBTNode* rret = BinaryTreeFind(root->_right, x);// 如果在右子树中找到了 x，返回指向右子树中 x 的节点的指针if (rret){return rret;}//否则，返回NULLreturn NULL;
}

其中，root表示当前节点，x表示要查找的值。如果当前节点为空，返回NULL；如果当前节点的值等于x，返回指向当前节点的指针；否则在左子树中查找x，如果找到了，返回指向左子树中x的节点的指针；否则在右子树中查找x，如果找到了，返回指向右子树中x的节点的指针；如果左右子树都没有找到，返回NULL。递归过程会一直向下遍历二叉树，直到找到值为x的节点或者遍历到叶子节点，然后逐层返回，找到值为x的节点或者返回NULL。

7.二叉树前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
这段代码实现了二叉树的先序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则打印当前节点的值，并递归遍历左子树和右子树。具体实现如下：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){//如果当前节点为空，直接返回return;}// 打印当前节点的值，并递归打印左子树和右子树printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先打印当前节点的值，然后递归遍历左子树和右子树。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，逐个打印节点的值，最终得到整棵二叉树的先序遍历序列。

8.二叉树中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
这段代码实现了二叉树的中序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则先递归遍历左子树，打印当前节点的值，再递归遍历右子树。具体实现如下：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){// 如果当前节点为空，直接返回return;}// 递归打印左子树，打印当前节点的值，再递归打印右子树	BinaryTreePrevOrder(root->_left);printf("%c ", root->_data);BinaryTreePrevOrder(root->_right);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先递归遍历左子树，打印当前节点的值，再递归遍历右子树。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，逐个打印节点的值，最终得到整棵二叉树的中序遍历序列。

9.二叉树后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
这段代码实现了二叉树的后序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则先递归遍历左子树和右子树，再打印当前节点的值。具体实现如下：

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){// 如果当前节点为空，直接返回return;}// 递归打印左子树和右子树，再打印当前节点的值BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);printf("%c ", root->_data);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先递归遍历左子树和右子树，再打印当前节点的值。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，最终得到整棵二叉树的后序遍历序列。

10.层序遍历

这段代码实现了二叉树的层序遍历过程。其原理是通过队列实现的，先将根节点入队，然后循环从队列中取出节点并打印节点的值，如果节点有左子节点，就将左子节点入队，如果节点有右子节点，就将右子节点入队，直到队列为空为止。具体实现如下：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{if (root == nullptr) {return;}std::queue<BTNode*> q;q.push(root);while (!q.empty()) {BTNode* node = q.front();q.pop();std::cout << node->_data << " ";if (node->_left != nullptr) {q.push(node->_left);}if (node->_right != nullptr) {q.push(node->_right);}}
}

其中，root表示根节点。首先将根节点入队，然后循环从队列中取出节点并打印节点的值，如果节点有左子节点，就将左子节点入队，如果节点有右子节点，就将右子节点入队，直到队列为空为止。这个过程会按照层序遍历的顺序依次遍历二叉树的每一层节点，从而得到整棵二叉树的层序遍历序列。

11.判断二叉树是否是完全二叉树

这段代码实现了判断二叉树是否为完全二叉树的过程。其原理是通过层序遍历和队列实现的，在层序遍历的过程中判断每个节点是否有左右子树，如果有就将它们入队，如果没有就将一个标志位设为1，表示之后遍历到的节点必须都是叶子节点，否则该树就不是完全二叉树。如果遍历到了一个节点，发现它的左子树或右子树为空，且之前已经出现过空子树，则该树就不是完全二叉树。如果遍历到队列中所有节点，均无右子树，则该树是完全二叉树。具体实现如下：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {if (root == NULL) {// 空树是完全二叉树return 1;}BTNode* queue[1000];int front = 0, rear = 0;queue[rear++] = root;int flag = 0; // 是否出现过空子树的标志while (front < rear) {BTNode* node = queue[front++];if (node->_left != NULL) {// 如果之前出现过空子树，则该树不是完全二叉树if (flag) {return 0;}queue[rear++] = node->_left;}else {flag = 1;}if (node->_right != NULL) {// 如果之前出现过空子树，则该树不是完全二叉树if (flag) {return 0;}queue[rear++] = node->_right;}else {flag = 1;}}// 如果队列中所有节点均无右孩子，则该树是完全二叉树return 1;
}

其中，root表示根节点。首先判断根节点是否为空，如果是，则空树是完全二叉树，直接返回1。然后定义一个队列，将根节点入队，并定义一个标志位flag表示是否出现过空子树。接下来，在队列不为空的情况下，从队列中取出一个节点，判断该节点的左右子树是否为空，如果有子树，则将子树入队；如果子树为空，则将标志位flag设为1表示之后遍历到的节点必须都是叶子节点。如果遍历到了一个节点，发现它的左子树或右子树为空，且之前已经出现过空子树，则该树就不是完全二叉树，直接返回0。如果遍历到队列中所有节点，均无右子树，则该树是完全二叉树，返回1。这个过程可以判断二叉树是否为完全二叉树。

12.完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<assert.h>
#include<stdio.h>
#include<limits.h>
#include<stdbool.h>
#include<queue>
using namespace std;
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{//如果数组已经遍历完或者当前节点是空节点，返回空指针if (*pi >= n || a[*pi] == '#'){//当前节点为空，返回NULL(*pi)++;return NULL;}//创建新节点并赋初值BTNode* root = new BTNode;root->_data = a[*pi];root->_left = NULL;root->_right = NULL;//递归构建左子树和右子树(*pi)++;root->_left = BinaryTreeCreate(a, n, pi);(*pi)++;root->_right = BinaryTreeCreate(a, n, pi);return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL)//如果当前节点为空，直接返回return;//递归销毁左子树和右子树BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));//释放当前节点的内存free(*root);*root = NULL;
}// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//如果当前节点为空返回0return 0;//返回左子树节点个数加上右节点个数再加上1（当前节点）return BinaryTreeSize(root->_left) +BinaryTreeSize(root->_right) + 1;
}// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//如果当前节点为空，返回0return 0;if (root->_left == NULL && root->_right == NULL){//如果当前节点是叶子节点，返回1return 1;}// 返回左子树叶子节点个数加上右子树叶子节点个数return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root==NULL)//如果当前节点为空，返回0return 0;if (k == 1)//如果当前节点是第k层节点，返回1return 1;// 返回左子树第 k-1 层节点个数加上右子树第 k-1 层节点个数int leftk = BinaryTreeLevelKSize(root->_left, k - 1);int rightk = BinaryTreeLevelKSize(root->_right, k - 1);return leftk + rightk;
}// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)//如果当前节点为空,返回NULLreturn 0;if (root->_data == x)//如果当前节点的值等于x，返回指向当前节点的指针return root;//在左子树中查找xBTNode* lret = BinaryTreeFind(root->_left, x);// 如果在左子树中找到了 x，返回指向左子树中 x 的节点的指针if (lret){return lret;}//在右子树中查找xBTNode* rret = BinaryTreeFind(root->_right, x);// 如果在右子树中找到了 x，返回指向右子树中 x 的节点的指针if (rret){return rret;}//否则，返回NULLreturn NULL;
}// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){//如果当前节点为空，直接返回return;}// 打印当前节点的值，并递归打印左子树和右子树printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){// 如果当前节点为空，直接返回return;}// 递归打印左子树，打印当前节点的值，再递归打印右子树	BinaryTreePrevOrder(root->_left);printf("%c ", root->_data);BinaryTreePrevOrder(root->_right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){// 如果当前节点为空，直接返回return;}// 递归打印左子树和右子树，再打印当前节点的值BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);printf("%c ", root->_data);
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{if (root == nullptr) {return;}std::queue<BTNode*> q;q.push(root);while (!q.empty()) {BTNode* node = q.front();q.pop();std::cout << node->_data << " ";if (node->_left != nullptr) {q.push(node->_left);}if (node->_right != nullptr) {q.push(node->_right);}}}// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {if (root == NULL) {// 空树是完全二叉树return 1;}BTNode* queue[1000];int front = 0, rear = 0;queue[rear++] = root;int flag = 0; // 是否出现过空子树的标志while (front < rear) {BTNode* node = queue[front++];if (node->_left != NULL) {// 如果之前出现过空子树，则该树不是完全二叉树if (flag) {return 0;}queue[rear++] = node->_left;}else {flag = 1;}if (node->_right != NULL) {// 如果之前出现过空子树，则该树不是完全二叉树if (flag) {return 0;}queue[rear++] = node->_right;}else {flag = 1;}}// 如果队列中所有节点均无右孩子，则该树是完全二叉树return 1;
}
int main()
{BTDataType a[] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' };int n = sizeof(a) / sizeof(a[0]);int i = 0;BTNode* root = BinaryTreeCreate(a, n, &i);//cout << root << endl;/*cout <<"BinaryTreeSize:" << BinaryTreeSize(root) << endl;cout << "BinaryTreeLeafSize:" << BinaryTreeLeafSize(root) << endl;cout <<"BinaryTreeLevelKSize:" << BinaryTreeLevelKSize(root, 1) << endl;cout << "BinaryTreeFind:" << BinaryTreeFind(root, 'A') << endl;*///BinaryTreePrevOrder(root);//BinaryTreeInOrder(root);//BinaryTreePostOrder(root);//BinaryTreeLevelOrder(root);//cout<<BinaryTreeComplete(root) << endl;//cout << BinaryTreeComplete(root) << endl;
}

http://www.ppmy.cn/news/893879.html

相关文章

邓应海：黄金冲高回落，欧盘继续看跌！最新黄金走势分析！

邓应海：黄金冲高回落，欧盘继续看跌！最新黄金走势分析！

每次交易都是一个新的开始&#xff0c;过去的就让他过去&#xff0c;不要沉浸在上次交易获利后的激动&#xff0c;也不要悲伤于上次交易带给你的痛苦&#xff0c;我们要做的&#xff0c;只是往前看。 投资者本周还将聆听美联储成员的一些讲话。 美联储理事夸尔斯周三表示&#…
阅读更多...
“夕阳无限好，只是近黄昏”改一个什么字让意境与原句截然不同？

“夕阳无限好，只是近黄昏”改一个什么字让意境与原句截然不同？

这样的改字儿拼意境的&#xff0c;真的很费脑细胞啊&#xff01; 据说—— 古代的诗人&#xff0c;都费脑筋地改来改去&#xff0c;还起了个很难听的名字&#xff0c;叫&#xff1a;推敲。 《刘公嘉话》还为此编造出了唐代贾岛推敲的故事&#xff0c;但故事就是故事&#xff…
阅读更多...
炒股赚钱最重要的是炒股心态和纪律

炒股赚钱最重要的是炒股心态和纪律

(1) 看不懂,看不准,没把握时坚决不进场 (2)先学会做空,再学会做多 (3)君子问凶不问吉,高手看盘先看跌 (4) 贪婪与恐惧,投资之大忌 (5)侥幸是加大风险的罪魁,犹豫则是错失良机的祸首,心态第一,策略第二,技术只有屈居第三 (6)任何时候不要轻易满仓,这样做,有利于保持平常心态…
阅读更多...
股市学习稳扎稳打（一）认识市场上的各路游资

股市学习稳扎稳打（一）认识市场上的各路游资

文章目录 股市学习稳扎稳打（一）认识市场上的各路游资相关阅读1、佛山无影脚-廖国沛2、割肉荣3、孙哥-孙煜4、小鳄鱼5、欢乐海岸6、炒股养家7、章盟主-章建平8、赵老哥-赵强股市学习稳扎稳打（一）认识市场上的各路游资 @ 如果觉得本文对你有帮助，可以一键三连支持，谢谢 @ 感…
阅读更多...
股票投资长期持续稳定盈利 ​（干货）

股票投资长期持续稳定盈利 ​（干货）

它山之石 可以攻玉&#xff0c; 持续跟踪高瓴资本、顶级公募基金 通过分析卓越投资者的逻辑&#xff0c;站在巨人的肩膀上进行投资是通往成功的不二法门。 我们买股票&#xff0c;买的到底是什么&#xff1f;如何才能盈利&#xff0c;到底赚的是什么钱。所有进入股市的投资者都…
阅读更多...
教你炒股票15：没有趋势，没有背驰

教你炒股票15：没有趋势，没有背驰

教你炒股票15&#xff1a;没有趋势&#xff0c;没有背驰。(2006-12-08 11:55:57) 娇&#xff1a;这里的没有趋势没有背驰的趋势指创出明显的高低点 有人很关心诸如庄家、主力之类的事情&#xff0c;但散户、庄家的位次分野这类事情不过是市场之“不患”下的“患”&#xff0c…
阅读更多...
上班族如何用好炒股经

上班族如何用好炒股经

阅读更多...
股市绿油油，牛年基金热还会持续吗？不妨看书学习一下

股市绿油油，牛年基金热还会持续吗？不妨看书学习一下

刚在资本市场尝到甜头的基金投资者遭遇利润回吐&#xff0c;关于#牛年基金热还会持续吗#的讨论正在发酵。 最近的基金实在是太太太火了&#xff01;当“基金”成为了热搜的常驻嘉宾&#xff0c;大家打招呼的方式已经从&#xff1a;你吃了吗&#xff1f;变成了&#xff1a;你买了…
阅读更多...
最新文章

Copyright @ 2022~2023