#include<string>class Node
{
public:Node();~Node();std::string data;Node *lChild;Node *rChild;private:};Node::Node()
{
}Node::~Node()
{
}

#include "Node.h"
#include <iostream>
#include<stack>/*
初始化二叉树的表头
*/
Node *initial()
{Node *header = new Node;header->lChild = nullptr;header->rChild = nullptr;header->data = " ";return header;
}/*
创建根节点
*/
void createRoot(std::string data, Node *header)
{Node *root = new Node();root->data = data;root->lChild = nullptr;root->rChild = nullptr;header->lChild = root;//将树的根节点保存在头节点的左节点。以后的操作只要正对根节点就行了
}/*
给根结点添加左孩子节点，如果根节点本身就存在左孩子节点就将当前结点作为根节点的左孩子，之前的左孩子节点作为新的节点的左孩子节点
*/void insertL(std::string data, Node *header)
{Node *root = header->lChild;Node *lChild = new Node();lChild->data = data;lChild->rChild = nullptr;//新添加的节点应该是不含孩子节点的，但如果根节点本身就有左孩子节点，则此节点有左孩子节点if (root->lChild != nullptr)lChild->lChild = root->lChild;elselChild->lChild = nullptr;root->lChild = lChild;
}/*
给根结点添加右孩子节点，如果根节点本身就存在右孩子节点就将当前结点作为根节点的右孩子，之前的右孩子节点作为新的节点的右孩子节点
*/void insertR(std::string data, Node *header)
{Node *root = header->lChild;Node *rChild = new Node();rChild->data = data;rChild->lChild = nullptr;//新添加的节点应该是不含孩子节点的，但如果根节点本身就有右孩子节点，则此节点有右孩子节点if (root->rChild != nullptr)rChild->rChild = root->rChild;elserChild->rChild = nullptr;root->rChild = rChild;
}/*
删除某个节点的左子树
*/
void deleteL(Node *parent, Node *header)
{if (parent == nullptr || parent->lChild == nullptr)return;else{Node *lChild = parent->lChild;parent->lChild = nullptr;lChild = nullptr;free(lChild);}
}/*
删除某个节点的右孩子树
*/
void deleteR(Node *parent, Node *header)
{if (parent == nullptr || parent->rChild == nullptr)return;else{Node *rChild = parent->rChild;parent->rChild = nullptr;rChild = nullptr;free(rChild);}
}/*
查找某个数据的节点元素
*/Node *search(std::string data, Node *header)
{Node *root = header->lChild;Node *item = header->lChild;std::stack<Node *> nodeStack;nodeStack.push(item);//先序遍历查找节点	while (item != nullptr || nodeStack.size() != 0){while (item != nullptr){if (item->data == data)return item;if (item != header->lChild)nodeStack.push(item);item = item->lChild;}if (nodeStack.size() == 0)return nullptr;item = nodeStack.top();nodeStack.pop();item = item->rChild;}return nullptr;}/*
先序遍历二叉树
*/
void preTraveler(Node *header)
{Node *item = header->lChild;//需要用一个栈来保存所有访问过的元素，这样才能访问当前元素的父元素std::stack<Node *> nodeStack;nodeStack.push(item);//只有当栈没有元素了，item也是null的时候，才说明二叉树访问完毕while (item != nullptr || nodeStack.size() != 0){while (item != nullptr){//将左子树入栈std::cout << item->data << " ";if (item != header->lChild)nodeStack.push(item);item = item->lChild;}//如果栈中没有元素，说明所有的元素都访问过了。if (nodeStack.size() == 0)return;//弹出栈顶元素item = nodeStack.top();nodeStack.pop();item = item->rChild;}}/*
中序遍历二叉树
和先序遍历不同的地方在于，访问节点数据的位置不同。
先序遍历是先访问节点在入栈，中序遍历则是先入栈在访问节点
*/
void midTraveler(Node *header)
{Node *item = header->lChild;std::stack<Node *> nodeStack;nodeStack.push(item);while (item != nullptr || nodeStack.size() != 0){while (item != nullptr){if (item != header->lChild)nodeStack.push(item);item = item->lChild;}if (nodeStack.size() == 0)return;item = nodeStack.top();std::cout << item->data << " ";nodeStack.pop();item = item->rChild;}}

#include"BinaryTree.h"
#include<sstream>//fstreamint main()
{Node *header = initial();createRoot("root", header);//创建根节点//将偶数插入左子树，奇数插入右子树。//由于每次都插入到根节点的字数，导致数的结构是左子树只有左孩子，右子树只有右孩子。//其实insertL可以传递的header可以改成需要作为父元素的节点，这样就可避免除出现签名的情况std::stringstream inS;for (int i = 1; i <= 100; i++){inS <<std::unitbuf<< i<<std::nounitbuf;if (i % 2 == 0)insertL(inS.str(), header);elseinsertR(inS.str(), header);inS.str("");//必须情况内容，否则的话，会把前面的内容拼合起来}//先序遍历preTraveler(header);std::cout << std::endl;//中序遍历midTraveler(header);return 0;
}

---------文章写自：HyHarden---------

--------博客地址：http://blog.csdn.net/qq_25722767-----------