有序二叉树：
二叉树：每个节点有且只有2个孩子
有序二叉树：左孩子<根<右孩子（升序二叉树）
左孩子>根>右孩子（降序二叉树）
叶子节点：没有孩子的节点
有序二叉树节点定义：（数据+左孩子+右孩子）
template<class T>
class Tree{
struct Node{
T data;//数据
Node* left;//左孩子
Node* right;//右孩子
};
Node* pRoot;//根节点
public:
//构造器
Tree(){
pRoot = NULL;//默认根节点为NULL
}
//析构器
~Tree(){
// if(pRoot)
// _clear();
// pRoot = NULL;
}
//添加节点
void insert(const T& data);//插入数据data
void printT();//遍历打印整棵树
void _insert(Node** pRoot, const T& data);//往pRoot里插入数据data
// _clear(){
//
// }
Node* createNode(const T& data){//创造一个Node节点
Node* pNew = new Node;
pNew->data = data;
pNew->left = pNew->right = NULL;
return pNew;
}
void _printTree(Node* pRoot);//遍历打印整棵树
};
完整代码实现：
#include<iostream>
#include<vector>
#include<string.h>
template<class T>
class Tree{
struct Node{
T data;//数据
Node* left;//左孩子
Node* right;//右孩子
};
Node* pRoot;//根节点
public:
//构造器
Tree(){
pRoot = NULL;//默认根节点为NULL
}
//析构器
~Tree(){
// if(pRoot)
// _clear();
// pRoot = NULL;
}
//添加节点
void insert(const T& data);//插入数据data
void printT();//遍历打印整棵树
void _insert(Node** pRoot, const T& data);//往pRoot里插入数据data
// _clear(){
//
// }
Node* createNode(const T& data){//创造一个Node节点
Node* pNew = new Node;
pNew->data = data;
pNew->left = pNew->right = NULL;
return pNew;
}
void _printTree(Node* pRoot);//遍历打印整棵树
};
template<class T>
//遍历打印整棵树
void Tree<T>::_printTree(Node* pRoot){
//Node* pTemp = *pRoot;
if(pRoot != NULL){
printf("%d ", pRoot->data);
}
if(pRoot == NULL){
_printTree(pRoot->left);
_printTree(pRoot->right);
}
printf("
");
}
template<class T>
void Tree<T>::_insert(Node** pRoot, const T& data){
Node* pNew = createNode(data);
//新节点成为根节点
if( (*pRoot) == NULL ){
*pRoot = pNew;
return;
}
//新节点成为左节点
if((*pRoot)->data > data){
_insert(&((*pRoot)->left), data);
}
//新节点成为右节点
if((*pRoot)->data < data){
_insert(&((*pRoot)->right), data);
}
/*
Node* pTemp = (*pRoot);
while(pTemp){
if(pTemp->left){
if()
}else if(pTemp->right){
}else{
if(pTemp->data > data)
pTemp->left = pNew;
if(pTemp->data < data)
pTemp->right = pNew;
}
if(pTemp->data == data)
return;
}
*/
/*
if(this->pRoot){//this->pRoot不为NULL,说明要插入的不是根节点
while(this->pRoot->left){
}
}else{//this->pRoot为NULL，插入根节点
this->pRoot = pNew;
}
*/
}
template<class T>
void Tree<T>::insert(const T& data){
_insert(&pRoot, data);//往pRoot里插入数据data
}
template<class T>
void Tree<T>::printT(){
_printTree(pRoot);
}
int main(){
Tree<int> t;
t.insert(2);
t.insert(0);
t.insert(3);
t.insert(4);
t.printT();
return 0;
}
有点问题：
创建应该没有问题，打印的时候只打印了根节点就结束了，没找到问题所在。