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

5.3.数据结构-c/c++二叉树代码

news 来源：原创 2024/9/20 14:35:04

二叉树的全部代码，可以直接运行

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
#include<queue>
using namespace std;//定义节点
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//创建一个新节点
BTNode* CreatNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));assert(node);//更新节点的值，并将左右指针置空node->data = x;node->left = nullptr;node->right = nullptr;return node;
}//前序遍历
void PrevOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}cout << (char)root->data << " ";	//访问根节点PrevOrder(root->left);		//访问左子树PrevOrder(root->right);		//访问右子树
}//中序遍历
void InOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//中序遍历前访问左子树，再访问根节点，最后访问右子树InOrder(root->left);		//访问左子树cout << (char)root->data << " ";	//访问根节点InOrder(root->right);		//访问右子树
}//后序遍历
void NextOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//后序遍历先访问左子树，在访问右子树。最后访问根节点NextOrder(root->left);		//访问左子树NextOrder(root->right);		//访问右子树cout << (char)root->data << " ";	//访问根节点
}//层序遍历(广度优先遍历)，该遍历需要我们使用到队列先进先出的特点
void TreeLeverOrder(BTNode* root)
{if (root == nullptr){return;}queue<BTNode*> q;q.push(root);while (!q.empty()){BTNode* front = q.front();if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}cout << (char)q.front()->data << " ";q.pop();}cout << endl;
}//销毁一棵树//使用后续销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}//求二叉树第k层结点的个数
int TreeKSize(BTNode* root, int k)
{if (root == nullptr)return 0;if (k == 1)return 1;return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}//查找某个结点是否在二叉树种
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return nullptr;if (root->data == x)return root;BTNode* node1 = TreeFind(root->left, x);if (node1 != nullptr)return node1;BTNode* node2 = TreeFind(root->right, x);if (node2 != nullptr)return node2;
}//遍历
void TreeSize1(BTNode* root, int* psize)
{if (root == nullptr)return;else(*psize)++;TreeSize1(root->left, psize);TreeSize1(root->right, psize);
}//分治
int TreeSize2(BTNode* root)
{if (root == nullptr)return 0;elsereturn 1 + TreeSize2(root->left) + TreeSize2(root->right);
}//求叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == nullptr)return 0;//保证遇到叶子节点的时候返回1if (root->left == nullptr && root->right == nullptr)return 1;//分治且其他所有节点都不返回return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}//求树的深度
int TreeDepth(BTNode* root)
{if (root == nullptr)return 0;int leftdepth = TreeDepth(root->left);int rightdepth = TreeDepth(root->right);if (leftdepth > rightdepth)return leftdepth + 1;elsereturn rightdepth + 1;
}//判断一棵树是否为完全二叉树
bool TreeComplete(BTNode* root)
{queue<BTNode*> q;//空树是完全二叉树if (!root)	return true;q.push(root);while (!q.empty()){BTNode* front = q.front();q.pop();if (front == nullptr)break;q.push(front->left);q.push(front->right);}//判断while (!q.empty()){BTNode* front = q.front();q.pop();if (front != nullptr)return false;}return true;
}int main()
{BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');BTNode* F = CreatNode('F');BTNode* G = CreatNode('G');A->left = B;A->right = C;B->left = D;B->right = E;C->left = F;C->right = G;int sizeA = 0;TreeSize1(A, &sizeA);cout << "TreeSize1:" << sizeA << endl;cout << "TreeSize2:" << TreeSize2(A) << endl;cout << "TreeLeafSize:" << TreeLeafSize(A) << endl;cout << "TreeDepth:" << TreeDepth(A) << endl;cout << "k=3 TreeKsize:" << TreeKSize(A, 3) << endl;if (TreeComplete(A))cout << "是完全二叉树" << endl;elsecout << "不是完全二叉树" << endl;return 0;
}