C++ 二叉树的基本操作

C++实现二叉树的基本操作

包括 添加节点、删除节点、前序遍历、中序遍历、后续遍历、层序遍历、最大值、最小值、二叉树的高度

//Tree.h 头文件

#include <stdio.h>
 
class Tree
{
 private :
  //节点元素类型为结构体
   struct LinkNode
   {
   int data;
   LinkNode *left;
   LinkNode *right;
   LinkNode(const int& dat,LinkNode *l,LinkNode *r):data(dat),left(l),right(r){}
   };
 
   LinkNode *head;//表头节点

   //添加节点
      void AddTreeNode(LinkNode *node,LinkNode *newNode);
   //显示中序排列
   void ShowCLR(LinkNode *root);
      //显示前序排列
   void ShowLCR(LinkNode *root);
      //显示右序排列
   void ShowLRC(LinkNode *root);
      //高度
   int  Height(LinkNode *root);

  public :
   //添加节点
   bool AddTreeNode(int  data);
   //显示中序排列
   bool ShowCLR();
   //显示前序排列
      bool ShowLCR();
      //显示右序排列
   bool ShowLRC();
   //前序排列
   bool Floor();
      //最小值
   bool Min(int** minValue);
   //最大值
   bool Max(int** maxValue);
   //是否是空树
   bool Empty();
   //高度
   void Height(int** height);

   ~Tree()
   {
      delete[] head;
   }

   Tree()
   {
      head=new LinkNode(-1,NULL,NULL);
   }
};

//实现文件Tree.cpp

#include "stdafx.h"
#include <stdio.h>
#include<iostream>
using namespace std ;
#include "Tree.h";
#include <queue>

//添加节点
void Tree::AddTreeNode(LinkNode *node,LinkNode *newNode)
{
 if(node->data>newNode->data)
 {
  if(node->left==NULL)
  {
   node->left=newNode;
  }else{
   AddTreeNode(node->left,newNode);
  }

 }else if(node->data<newNode->data)
 {
  if(node->right==NULL)
  {
   node->right=newNode;
  }else{
      AddTreeNode(node->right,newNode);
  }
 }

}

//添加节点
bool Tree::AddTreeNode(int data)
{
 LinkNode *node=new LinkNode(data,NULL,NULL);
    if(head->left==NULL)
 {
  head->left=node;
 }
 AddTreeNode(head->left,node);

 return true;
}

//中序遍历
void Tree::ShowCLR(LinkNode *root)
{
 if(root!=NULL){
  cout<<root->data<<"  ";
 }
    
 if(root->left!=NULL)
 {
  ShowCLR(root->left);
 }

 if(root->right!=NULL)
 {
  ShowCLR(root->right);
 }
}

//中序遍历
bool Tree::ShowCLR()
{
 if(Empty())
 {
   return false;
 }
 ShowCLR(head->left);
  
 return true;
}

//前序遍历
void Tree::ShowLCR(LinkNode *root)
{
 if(root->left!=NULL)
 {
  ShowLCR(root->left);
 }

 if(root!=NULL){
  cout<<root->data<<"  ";
 }
    
 if(root->right!=NULL)
 {
  ShowLCR(root->right);
 }
}

//前序遍历
bool Tree::ShowLCR()
{
 if(Empty())
 {
   return false;
 }
 ShowLCR(head->left);
  
 return true;
}

//后序遍历
void Tree::ShowLRC(LinkNode *root)
{
 if(root->left!=NULL)
 {
  ShowLRC(root->left);
 }

 if(root->right!=NULL)
 {
  ShowLRC(root->right);
 }

 if(root!=NULL){
  cout<<root->data<<"  ";
 }
}

//后序遍历
bool Tree::ShowLRC()
{
 if(Empty())
 {
   return false;
 }
 ShowLRC(head->left);
 
 return true;
}

//最小值
bool Tree::Min(int** minValue)
{
 if(Empty())
 {
   return false;
 }
 LinkNode *tmp=head->left;
 while(tmp!=NULL && tmp->left!=NULL)
 {
    tmp=tmp->left;
 }
    **minValue= tmp->data;

 return true;
}

//最大值
bool Tree::Max(int** maxValue)
{
 if(Empty())
 {
   return false;
 }
 LinkNode *tmp=head->left;
 while(tmp!=NULL && tmp->right!=NULL)
 {
    tmp=tmp->right;
 }
    **maxValue= tmp->data;

 return true;
}

//判断树是否为空
bool Tree::Empty()
{
 return head->left==NULL;
}

//用队列实现二叉树层序遍历
//1:添加根节点
//2:打印根节点的数据,添加根节点的子节点，弹出根节点
//3:循环第二步
bool Tree::Floor()
{
    queue<LinkNode*> q;
 LinkNode* cur=head->left;
 q.push(head->left);
 while(!q.empty())
 {
  cur=q.front();
  cout<<cur->data<<"  ";

  if(cur->left!=NULL){
   q.push(cur->left);
  }
  if(cur->right!=NULL)
  {
   q.push(cur->right);
  }
  q.pop();
 }
 return true;

}

//求两个数中较大的一个
int max(int a,int b)
{
 if(a>b)
 {
  return a;
 }else
 {
  return b;
 }
}

//递归求二叉树的高度
//二叉树的高度就是左子树和右子树中较大一颗二叉树的高度
int Tree::Height(LinkNode *root)
{
 if(root==NULL)
 {
  return 0;
 }
 return 1+max(Height(root->left),Height(root->right));
}

//用指向指针的指针接受二叉树的高度
void Tree::Height(int** height)
{
 **height=Height(head->left);
}

int main()
{
   TreeTest();
 int a=0;
 cin>>a;
    return 0;
}
 

 //指针类型调用属性和方法用“->” 对象类型用“.”
 //变量在不需要使用的时候就要释放掉它的内存 
void TreeTest()                   
{                                
   Tree  tree;
   int a[]={1,3,6,7,8,2,4,9,10,5};
   for(int i=0;i<10;i++){
    tree.AddTreeNode(a[i]);
   }
   cout<<"-----------原始数组----------"<<endl;
   for(int i=0;i<10;i++)
   {
  cout<<a[i]<<"  "; 
   }

   cout<<endl;
   cout<<endl;
   cout<<"-----------中序排列----------"<<endl;
   tree.ShowCLR();
   cout<<endl;cout<<endl;
   cout<<"-----------前序排列----------"<<endl;
   tree.ShowLCR();
   cout<<endl;cout<<endl;
   cout<<"-----------后序排列----------"<<endl;
   tree.ShowLRC();
   cout<<endl;
   cout<<endl;
   cout<<"-----------层序排列----------"<<endl;
   cout<<endl;
   tree.Floor();
   cout<<endl;
   int min=-1;
   int *pmin=&min;
   tree.Max(&pmin);
    cout<<endl;
   cout<<"最大值:"<<min<<endl;
   cout<<endl;
   tree.Min(&pmin);
   cout<<"最小值:"<<min<<endl;
  
   cout<<endl;
   int h=-1;
   int *height=&h;
   tree.Height(&height);
   cout<<"高度:"<<h<<endl;
}

本文转自啊汉博客园博客，原文链接：http://www.cnblogs.com/hlxs/archive/2011/04/02/2087980.html