结果应该是分别是：
广度优先: a ->b ->c ->d ->f ->e ->g
先序遍历: a ->b ->d ->e ->f ->g ->c
中序遍历: e ->d ->b ->g ->f ->a ->c
后序遍历: e ->d ->g ->f ->b ->c ->a
结果存在result里面，如果不存可以少一层变量
这个地方强烈建议读一下下面的第一个链接，我遵照着那篇文章实现的，只是用Go改写了而已。
首先定义一个数据结构，用来存储一些Node的信息。
这里是可以运行的，但是总会抛出一个数组越界的错误，我看了半天也没看出来哪里有问题，Mac版的devel我这边又有bug，没用起来。至少思路对了，我后面再看一下哪里的问题。(感谢 @RiXu 指正)
#include <iostream>using namespace stdtypedef struct _node{ int data struct _node *pLeftPtr struct _node *pRightPtr}BTreeNodeclass BinarySearchTree{public: BinarySearchTree() ~BinarySearchTree() bool Create(int* pIntArray,int arrLength) bool Insert(int data) // 查找节点，searchLength为搜索长度，返回值为true表示指定的数据存在，否则不存在 bool Find(int data, int* searchLength) // 中序输出二叉树 void MidOutput() // 释放内存 void Destroy() void Delete(int data)protected: bool Insert(BTreeNode* pRoot, int data) bool Find(BTreeNode* pRoot,int data, int *searchLength) void Delete(BTreeNode* &pRoot, int data) void MidOutput(BTreeNode* pRoot) void Destroy(BTreeNode* pRoot)private: BTreeNode* m_pRoot //二叉搜索树根节点}BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL}BinarySearchTree::~BinarySearchTree(){ Destroy()}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0i<arrLengthi++) { if(!Insert(*(pIntArray+i))) return false } return true}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode if(pNewNode == NULL) return false pNewNode->data = data pNewNode->pLeftPtr = NULL pNewNode->pRightPtr = NULL BTreeNode* pCurrentNode = pRoot BTreeNode* pParentNode = pCurrentNode// 保存父节点的指针 int flag = 0// 标记插入节点的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode }else{ while(pCurrentNode) { if(data <pCurrentNode->data) { pParentNode = pCurrentNode pCurrentNode = pCurrentNode->pLeftPtr flag = 0 }else if(data >pCurrentNode->data){ pParentNode = pCurrentNode pCurrentNode = pCurrentNode->pRightPtr flag = 1 } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode }else{ pParentNode->pRightPtr = pNewNode } } return true }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data)}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0 return false } BTreeNode* pCurrentNode = pRoot static int length = 0 while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length cout<<"数字"<<data<<"存在二叉树中,查找长度为: "<<endl<<length<<endl return true }else if(data <pCurrentNode->data) { length ++ pCurrentNode = pCurrentNode->pLeftPtr }else{ length ++ pCurrentNode = pCurrentNode->pRightPtr } } *searchLength = length cout<<"数字"<<data<<"不在二叉树中,查找长度为: "<<endl<<length<<endl length = 0// 每次查找结束，重新赋值为0 return false}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength)}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot if(pCurrentNode == NULL) return Destroy(pCurrentNode->pLeftPtr) Destroy(pCurrentNode->pRightPtr) delete pCurrentNode m_pRoot = NULL}void BinarySearchTree::Destroy(){ Destroy(m_pRoot)}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr) cout<<pRoot->data <<" " MidOutput(pRoot->pRightPtr) }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot)}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data)}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL &&pRoot->pRightPtr == NULL) // 叶子节点 { delete pRoot pRoot = NULL }else if(pRoot->pLeftPtr != NULL &&pRoot->pRightPtr == NULL){ // 只有左子树 BTreeNode* pNode = pRoot->pLeftPtr delete pRoot pRoot = pNode }else if(pRoot->pLeftPtr == NULL &&pRoot->pRightPtr != NULL){ // 只有右子树 BTreeNode* pNode = pRoot->pRightPtr delete pRoot pRoot = pNode }else{ // 有左右子树 // 找到左子树的最大节点 BTreeNode* pCurrentNode = pRoot->pLeftPtr BTreeNode* pParentNode = NULL while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode pCurrentNode = pCurrentNode->pRightPtr } pRoot->data = pCurrentNode->data if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr } delete pCurrentNode } }else if(data <pRoot->data) Delete(pRoot->pLeftPtr, data) else Delete(pRoot->pRightPtr, data)}void main(){ int data[8] cout<<"请输入整形数据, 数据用空格隔开, 回车键结束输入"<<endl for(int i=0i<8i++) cin>>data[i] // int data[8] = {13,15,6,20,14,5,7,18} BinarySearchTree tree tree.Create(data,sizeof(data)/sizeof(data[0])) cout<<"插入数据后的二叉树为: "<<endl tree.MidOutput() cout<<endl int len_1=0 int len_2=0 tree.Find(14,&len_1) tree.Find(21,&len_2) tree.Delete(20) cout<<"删除数字20后的二叉树结果: "<<endl tree.MidOutput() cout<<endl tree.Delete(15) cout<<"删除数字15后的二叉树结果: "<<endl tree.MidOutput() cout<<endl}
