C++实现二叉树

//二叉树.cpp
#include "stdafx.h"
#include<iostream>
#include<cstdlib>
#include <ctime>
#include<list>
using namespace std;
struct node
{
int data;
node * father;
node * lchild;
node * rchild;
};


class tree
{
private:
node * root;//根节点
public:
tree();
~tree();
void insert(int data);
node * findNode(int data);
void preOrder(node *p);//前
void inOrder(node *p);//中
void lastOrder(node *p);//后
void clear(node *p);//清空树，即删除整棵树
node* getRoot();
void levelOrder();//层次遍历
void deleteByData(int data);//删除节点（较复杂）
};


tree::tree()
{
root = nullptr;
}
tree::~tree()
{
clear(root); 
root = nullptr;
}
void tree::insert(int data)
{
if (root == nullptr)//是否是空树
{
root = new node;
root->data = data;
root->lchild = root->rchild = nullptr;
}
else
{
node *p, *q;
p = root;
while (true)
{
if (p->data <= data)
{
if (p->rchild == nullptr)
{
p->rchild = new node;
p->rchild->lchild = p->rchild->rchild = nullptr;
p->rchild->data = data;
break;
}
p = p->rchild;
}
else
{
if (p->lchild == nullptr)
{
p->lchild = new node;
p->lchild->lchild = p->lchild->rchild = nullptr;
p->lchild->data = data;
break;
}
p = p->lchild;
}
}
}
}
node * tree::findNode(int data)
{
node *p = root;
while (p != nullptr)
{
if (p->data == data)
break;
else if (p->data < data)
p = p->rchild;
else p = p->lchild;
}
return p;
}
void tree::preOrder(node *p)//前
{
if (p != nullptr)
{
cout << p->data << '\t';
preOrder(p->lchild);
preOrder(p->rchild);
}
}
void tree::inOrder(node *p)//中
{
if (p != nullptr)
{
inOrder(p->lchild);
cout << p->data << '\t';


inOrder(p->rchild);
}
}
void tree::lastOrder(node *p)//后
{
if (p != nullptr)
{
lastOrder(p->lchild);
lastOrder(p->rchild); cout << p->data << '\t';
}
}
void tree::clear(node *p)
{
if (p != nullptr)
{
clear(p->lchild);
clear(p->rchild);
p = nullptr;
}
}
node* tree::getRoot()
{
return root;
}
void tree::levelOrder()
{
list<node*>lis;
lis.push_back(root);
node *p;
while (lis.empty() == 0)
{
p = lis.front();
if (p != nullptr)
{
lis.push_back(p->lchild);
lis.push_back(p->rchild);
}
cout << p->data << '\t';
}
lis.pop_front();//出队
}
void tree::deleteByData(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指向最大的节点
//将这个节点拿下来 root代替
q->father->rchild = nullptr;
q->father = root->father;
q->lchild = root->lchild;
q->rchild = root->rchild;
root = q;
delete root;
}




}




int _tmain(int argc, _TCHAR* argv[])
{
tree mytree;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
{
mytree.insert(rand() % 100);
}


cout << "前序遍历："<<endl ;
mytree.preOrder(mytree.getRoot());
cout << endl;


cout << "中序遍历：" << endl;
mytree.inOrder(mytree.getRoot());
cout << endl;


cout << "后序遍历：" << endl;
mytree.lastOrder(mytree.getRoot());
cout << endl;


mytree.levelOrder();
cout << endl;


system("pause");
return 0;
}