当前位置:编程学习 > C/C++ >>

二叉树用C++如何实现?

我想要一个可以编译运行的实现二叉树的c++源代码,可以帮忙讲解一下程序原理吗(稍稍详细一点)?

我只有这么多分了……

追问:谢谢,还想请问一下,二叉树的应用是在哪些方面呢?

 

答案:一个二叉树类,你可以直接用,后面是测试代码

可能有错误,但是我还没有发现^0^

// class for binary tree
// 1/9/2010

// head def //////////////////////////////////////////////

#ifndef _BINARY_TREE_H_NONO_
#define _BINARY_TREE_H_NONO_

// include //////////////////////////////////////////////

#include<Windows.h>

// class //////////////////////////////////////////////

// binary tree node

template<class DataType>
class BinaryTreeNode;

template<class DataType>
class BinaryTreeNode{
private:
 DataType m_Weight;
 BinaryTreeNode<DataType>* m_Left;
 BinaryTreeNode<DataType>* m_Right;
 BinaryTreeNode<DataType>* m_Father;
 void Init();
public:
 BinaryTreeNode();
 DataType GetWeight();
 BinaryTreeNode<DataType>* GetLeftSon();
 BinaryTreeNode<DataType>* GetRightSon();
 BinaryTreeNode<DataType>* GetFather();
 void SetWeight(DataType);
 void SetLeftSon(BinaryTreeNode<DataType>*);
 void SetRightSon(BinaryTreeNode<DataType>*);
 void SetFather(BinaryTreeNode<DataType>*);
};

// binary tree

template<class DataType>
class BinaryTree{
private:
 BinaryTreeNode<DataType>* m_Root;
 BinaryTreeNode<DataType>* m_Edit;
 void Init();
 void _Delete(BinaryTreeNode<DataType>* Node);
public:
 BinaryTree();
 ~BinaryTree();
 bool GotoFather();
 bool GotoLeftSon();
 bool GotoRightSon();
 void SetLeftTree(BinaryTree*);
 void SetRightTree(BinaryTree*);
 void SetLeftNode(DataType);
 void SetRightNode(DataType);
 void Delete();
 DataType View();
};

// action //////////////////////////////////////////////

// binary tree node

template<class DataType>
BinaryTreeNode<DataType>::BinaryTreeNode(){
 Init();
}

template<class DataType>
void BinaryTreeNode<DataType>::Init(){
 m_Weight=0;
 m_Left=NULL;
 m_Right=NULL;
 m_Father=NULL;
 return;
}

template<class DataType>
BinaryTreeNode<DataType>* BinaryTreeNode<DataType>::GetLeftSon(){
 return m_Left;
}

template<class DataType>
BinaryTreeNode<DataType>* BinaryTreeNode<DataType>::GetRightSon(){
 return m_Right;
}

template<class DataType>
DataType BinaryTreeNode<DataType>::GetWeight(){
 return m_Weight;
}

template<class DataType>
void BinaryTreeNode<DataType>::SetLeftSon(BinaryTreeNode<DataType>* Node){
 m_Left=Node;
 return;
}

template<class DataType>
void BinaryTreeNode<DataType>::SetRightSon(BinaryTreeNode<DataType>* Node){
 m_Right=Node;
 return;
}

template<class DataType>
void BinaryTreeNode<DataType>::SetWeight(DataType Weight){
 m_Weight=Weight;
 return;
}

template<class DataType>
BinaryTreeNode<DataType>* BinaryTreeNode<DataType>::GetFather(){
 return m_Father;
}

template<class DataType>
void BinaryTreeNode<DataType>::SetFather(BinaryTreeNode* Node){
 m_Father=Node;
}

// binary tree

template<class DataType>
BinaryTree<DataType>::BinaryTree(){
 Init();
}

template<class DataType>
void BinaryTree<DataType>::Init(){
 m_Root=new BinaryTreeNode<DataType>;
 m_Edit=m_Root;
 return;
}

template<class DataType>
BinaryTree<DataType>::~BinaryTree(){
 m_Edit=m_Root;
 Delete();
}

template<class DataType>
void BinaryTree<DataType>::_Delete(BinaryTreeNode<DataType>* Node){
 if(Node!=NULL){
  _Delete(Node->GetLeftSon());
  _Delete(Node->GetRightSon());
  delete Node;
 }
 return;
}

template<class DataType>
void BinaryTree<DataType>::Delete(){
 BinaryTreeNode<DataType>* p_Node=m_Edit->GetFather();
 if(p_Node->GetLeftSon()==m_Edit)
  p_Node->SetLeftSon(NULL);
 else
  p_Node->SetRightSon(NULL);
 _Delete(m_Edit);
 m_Edit=p_Node;
 return;
}

template<class DataType>
bool BinaryTree<DataType>::GotoFather(){
 if(m_Edit==NULL||m_Edit->GetFather()==NULL)
  return false;
 m_Edit=m_Edit->GetFather();
 return true;
}

template<class DataType>
bool BinaryTree<DataType>::GotoLeftSon(){
 if(m_Edit==NULL||m_Edit->GetLeftSon()==NULL)
  return false;
 m_Edit=m_Edit->GetLeftSon();
 return true;
}

template<class DataType>
bool BinaryTree<DataType>::GotoRightSon(){
 if(m_Edit==NULL||m_Edit->GetRightSon()==NULL)
  return false;
 m_Edit=m_Edit->GetRightSon();
 return true;
}

template<class DataType>
void BinaryTree<DataType>::SetLeftNode(DataType Weight){
 BinaryTreeNode<DataType>* p_New=new BinaryTreeNode<DataType>;
 p_New->SetFather(m_Edit);
 m_Edit->SetLeftSon(p_New);
 m_Edit=p_New;
 m_Edit->SetWeight(Weight);
 return;
}

template<class DataType>
void BinaryTree<DataType>::SetRightNode(DataType Weight){
 BinaryTreeNode<DataType>* p_New=new BinaryTreeNode<DataType>;
 p_New->SetFather(m_Edit);
 m_Edit->SetRightSon(p_New);
 m_Edit=p_New;
 m_Edit->SetWeight(Weight);
 return;
}

template<class DataType>
DataType BinaryTree<DataType>::View(){
 return m_Edit->GetWeight();
}

// head end //////////////////////////////////////////////

#endif

测试代码

#include"BinaryTree.h"
#include<iostream>

using namespace std;

int main(){
 BinaryTree<int> Test;
 cout<<endl<<"A Ineger Binary Tree Created"<<endl;
 cout<<"1.Go To Father Node"<<endl;
 cout<<"2.Go To Left Node"<<endl;
 cout<<"3.Go To Right Node"<<endl;
 cout<<"4.Create Left Node"<<endl;
 cout<<"5.Create Right Node"<<endl;
 cout<<"6.Delete"<<endl;
 cout<<"7.Clear"<<endl;
 cout<<"8.View"<<endl;
 cout<<"?.Help"<<endl;
 cout<<"0.Quit"<<endl;
 while(1){
  char ch;
  int w;
  cin>>ch;
  switch(ch){
  case '1':
   if(!Test.GotoFather())
    cout<<"Error"<<endl;
  break;
  case '2':
   if(!Test.GotoLeftSon())
    cout<<"Error"<<endl;
  break;
  case '3':
   if(!Test.GotoRightSon())
    cout<<"Error"<<endl;
  break;
  case '4':
   cout<<"Left Node Weight <Enter>"<<endl;
   cin>>w;
   Test.SetLeftNode(w);
  break;
  case '5':
   cout<<"Right Node Weight <Enter>"<<endl;
   cin>>w;
   Test.SetRightNode(w); 
  break;
  case '6':
   Test.Del

上一个:C++和visual C++到底有什么区别?
下一个:高分求解C++编程问题

CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,