#pragma once //Tree.h
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<list>//队列 队尾插入 队头删除
struct node
{
struct node *lchild, *rchild, *father;
int data;
};
template<class T>
class Tree
{
private:
node *root;
public:
Tree();
~Tree();
void insert(T data);
node* findNode(int data);
void preOrder(node *p);//先序遍历
void inOrder(node* p);
void lasOrder(node* p);
void clear(node* p);
node* getRoot();
void leverOrder();
void deleByData(int data);
};
template<class T>
Tree<T>::Tree() :root(nullptr){}
template<class T>
Tree<T>::~Tree()
{
clear(root);
root = nullptr;
}
template<class T>
void Tree<T>::insert(T data)
{
if (nullptr == root)//判断是否空树
{
root = new node;
root->data = data;
root->lchild = root->rchild = root->father = nullptr;
}
else
{
node *p = root;
while (true)
{
if (p->data <= data)
{
if (nullptr == p->rchild)
{
p->rchild = new node;
p->rchild->lchild = p->rchild->rchild = nullptr;
p->rchild->father = p->rchild;
p->rchild->data = data;
break;
}
p = p->rchild;
}
else
{
if (nullptr == p->lchild)
{
p->lchild = new node;
p->lchild->lchild = p->lchild->rchild = nullptr;
p->lchild->data = data;
p->lchild->father = p->lchild;
break;
}
p = p->lchild;
}
}
}
}
template<class T>
node * Tree<T>::findNode(int data)
{
node * p = root;
while (nullptr != p)
{
if (p->data == data)
break;
else if (p->data < data)
p = p->rchild;
else p = p->lchild;
}
return p;
}
template<class T>
void Tree<T>::preOrder(node* p)
{
if (nullptr != p)
{
std::cout << p->data << '\t';
preOrder(p->lchild);
preOrder(p->rchild);
}
}
template<class T>
void Tree<T>::inOrder(node*p)//中序遍历
{
if (p != nullptr)
{
inOrder(p->lchild);
std::cout << p->data << '\t';
inOrder(p->rchild);
}
}
template<class T>
void Tree<T>::lasOrder(node*p)
{
if (p != nullptr)
{
lasOrder(p->lchild);
lasOrder(p->rchild);
std::cout << p->data << '\t';
}
}
template<class T>
void Tree<T>::clear(node*p)
{
if (p != nullptr)
{
clear(p->lchild);
clear(p->rchild);
delete p;
}
}
template<class T>
node* Tree<T>::getRoot()
{
return root;
}
template<class T>
void Tree<T>::leverOrder()
{
using std::list;
list<node*>lis;
lis.push_back(root);
node*p;
while (lis.empty() == 0)//lis不空
{
p = lis.front();//得到队头元素
if (nullptr!=p)
{
lis.push_back(p->lchild);
lis.push_back(p->rchild);
std::cout << p->data << '\t';
}
lis.pop_front();//出队
}
}
template<class T>
void Tree<T>::deleByData(int data)
{
node*p = findNode(data);//查找要删除的节点
if (p == nullptr) return;
else if (p == root)//要删除的是根节点
{
if (root->lchild == nullptr&&root->rchild == nullptr)//只有一个节点
{
delete root;//直接删除
root = nullptr;
}
else if (root->lchild == nullptr)//左边为空 右边不为空
{
root = root->rchild;
delete p;//释放节点
}
else if (root->rchild == nullptr)//右边为空 左边不为空
{
root = root->lchild;
delete p;//释放节点
}
else
{
node*q = root->lchild;
while (q->rchild != nullptr)
{
q = q->rchild;//继续往右找
}
q->father->rchild = nullptr;
q->father = root->father;
q->lchild = root->lchild;
q->rchild = root->rchild;
root = q;//新的根节点
delete p;//释放之前的根节点
}
}
}
声明:本文为原创,作者为 对弈,转载时请保留本声明及附带文章链接:http://www.duiyi.xyz/c%e5%ae%9e%e7%8e%b0%e9%9b%b7%e9%9c%86%e6%88%98%e6%9c%ba-48/