#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef struct Node {
int data;
Node * left;
Node * right;
Node (int data) {
this->data = data;
}
}Node;
class MyTree{
public:
Node * root;
Node * insertNode(Node * root, int data);
void preOrderRead(Node * root);
void inOrderRead(Node *root);
void postOrderRead(Node *root);
void cengOrderRead(Node *root);
void shenduOrderRead(Node *root);
int getMaxDepth(Node *root);
int getMinDepth(Node *root);
int getMaxWidth(Node *root);
void deleteNode(int val, Node * root);
};
Node * MyTree::insertNode(Node * root, int data) {
if (root == NULL) {
this->root = new Node(data);
return this->root;
}
if (data <= root->data) {
if (root->left != NULL) {
insertNode(root->left, data);
}else {
root->left = new Node(data);
}
}
if (data > root->data) {
if (root->right != NULL) {
insertNode(root->right, data);
}else {
root->right = new Node(data);
}
}
return this->root;
}
void MyTree::preOrderRead(Node *root) {
if (root == NULL) return;
cout << root->data << endl;
preOrderRead(root->left);
preOrderRead(root->right);
}
void MyTree::inOrderRead(Node *root) {
if (root == NULL) return;
inOrderRead(root->left);
cout << root->data << endl;
inOrderRead(root->right);
}
void MyTree::postOrderRead(Node *root) {
if (root == NULL) return;
postOrderRead(root->left);
postOrderRead(root->right);
cout << root->data << endl;
}
// 层序遍历(广度优先遍历)
// 整体思路： 按照层级先将根节点存入队列中，再通过当前节点查找该节点的子节点并存入队列中，层层递进地实现层序遍历
void MyTree::cengOrderRead(Node *root) {
queue<Node *>queue;
vector<Node *>list;
queue.push(root);
while (queue.size() > 0) {
Node *node = queue.front(); //获取队列的第一个节点
queue.pop(); //将第一个节点pop出
list.push_back(node); // 将获取的节点直接存储入数组中
vector<Node *>childrens;
// 将队列第一个元素的子元素存入子数组
if (node->left != NULL) {
childrens.push_back(node->left);
}
if (node->right != NULL) {
childrens.push_back(node->right);
}
// 将子节点按照顺序存入队列
for (Node *childNode : childrens) {
queue.push(childNode);
}
}
for (int i = 0; i < list.size(); i++) {
cout << list[i]->data << endl;
}
}
// 深度遍历(深度优先遍历)
// 思路：该遍历方式通过栈来存储右、左节点，每次循环的时候只将栈顶的节点抛出输出并将其右、左子节点加入栈顶
void MyTree::shenduOrderRead(Node *root) {
vector<Node *>list;
if (root == NULL) return;
stack<Node *>stack;
stack.push(root);
while (stack.size() != 0) {
Node * node = stack.top(); // 获取栈顶的节点
stack.pop(); //将栈顶的节点推出
list.push_back(node);
if (node->right != NULL) {
stack.push(node->right);
}
if (node->left != NULL) {
stack.push(node->left);
}
}
for (int i = 0; i < list.size(); i++) {
cout << list[i]->data << endl;
}
}
// 获取最大深度
int MyTree::getMaxDepth(Node *root)
{
if (root == NULL) return 0;
int left = getMaxDepth(root->left);
int right = getMaxDepth(root->right);
return 1 + max(left, right);
}
// 获取最小深度
int MyTree::getMinDepth(Node *root)
{
if (root == NULL) return 0;
int left = getMaxDepth(root->left);
int right = getMaxDepth(root->right);
return 1 + min(left, right);
}
// 获取树的最大宽度
int MyTree::getMaxWidth(Node *root)
{
if (root==NULL) return 0;
queue<Node *>queue;
int maxWidth = 1;
queue.push(root);
while (true) {
int len = (int)queue.size();
if (len == 0) break;
while (len > 0) {
Node * t = queue.front();
queue.pop();
len--;
if (t->left != NULL) {
queue.push(t->left);
}
if (t->right != NULL) {
queue.push(t->right);
}
}
maxWidth = max(maxWidth, (int)queue.size());
}
return maxWidth;
}
// 删除树中值为data的节点
void MyTree::deleteNode(int data, Node * root) {
Node * p = root; // p指向要删除的节点，初始化指向根节点
Node * pp = NULL; // pp记录的是p的父节点
while (p != NULL && p->data != data) {
pp = p;
if (data > p->data) {
p = p->right;
}else {
p = p->left;
}
}
if (p == NULL) return; // 未找到要删除的值
// 要删除的节点有两个子节点
if (p->left != NULL && p->right != NULL) { // 查找右子树中最小节点
Node *minP = p->right;
Node *minPP = p; // minPP表示minP的父节点
while (minP->left != NULL) {
minPP = minP;
minP = minP->left;
}
p->data = minP->data; // 将minP的数据替换到p中
p = minP; // 下面就变成了删除minP了
pp = minPP;
}
// 删除节点是叶子节点或者仅有一个子节点
Node * child; // p的子节点
if (p->left != NULL) {
child = p->left;
}else if(p->right != NULL) {
child = p->right;
}else {
child = NULL;
}
if (pp == NULL) {
root = child; // 删除的是根节点
}else if(pp->left == p) {
pp->left = child; // 删除的是左孩子
}else {
pp->right = child; // 删除的是右孩子
}
}
int main(int argc, char *argv[]){
MyTree tree = MyTree();
tree.insertNode(tree.root, 5);
tree.insertNode(tree.root, 7);
tree.insertNode(tree.root, 6);
tree.insertNode(tree.root, 8);
tree.insertNode(tree.root, 3);
tree.insertNode(tree.root, 1);
tree.insertNode(tree.root, 4);
tree.insertNode(tree.root, 2);
tree.preOrderRead(tree.root);
cout << "中序遍历---" << endl;
tree.inOrderRead(tree.root);
cout << "---" << endl;
tree.postOrderRead(tree.root);
cout << "---" << endl;
tree.cengOrderRead(tree.root);
cout << "---" << endl;
tree.shenduOrderRead(tree.root);
cout << "---" << endl;
cout << "树的最大深度：" << tree.getMaxDepth(tree.root) << endl;
cout << "---" << endl;
cout << "树的最小深度：" << tree.getMinDepth(tree.root) << endl;
cout << "---" << endl;
cout << "树的最大宽度：" << tree.getMaxWidth(tree.root) << endl;
cout << "---" << endl;
tree.deleteNode(1, tree.root);
cout << "删除后的中序遍历：" << endl;
tree.inOrderRead(tree.root);
return 0;
}
网友评论