二叉树的算法与讲法

浏览数：22 / 时间：2015年06月08日

二叉树属于数据结构中层次性的数据关系，他又祖先——后代，上级——下属，整体——部分以及其他类似的关系，树结构在计算机领域中有着广泛的应用，例如在编译程序中庸语法树来表示元程序的语言结构，在数据挖掘中庸决策树来进行数据分类等等。在我的前一个博客中也有提到就是二叉树的相关知识重点。不清楚的同行可以参考我的文章。其中若有不妥之处，还请大家指点。

下面是我在学习二叉树的时候编写的二叉树的几个常见的功能的函数，以及他的一些构造函数等等。

#ifndef BITREE_H
#define BITREE_H
#include<iostream>
#include<iomanip>
using namespace std;
template <typename T>
struct BiNode
{
T data;
BiNode<T> *lchild, *rchild;          //利用递归的方法进行结点的构造
};
template<typename T>
class BiTree
{
template<typename T>
friend ostream & operator<<(ostream &os, BiTree<T> &bt);
public:
BiTree(T none);                     //构造一个空的二叉树
BiTree(T ary[], int num, T none);   //构造一个num个结点的二叉树
~BiTree();                          //析构函数
void Parent(T x);                //与pretected中的ParentIn对应
void print(ostream &os);            //遍历操作
void Count();                       //与protected中的CountIn对应
void PreOrderPrint();               //与protected中的PreOrderPrintIn对应
void Depth();                       //与protected中的DepthIn对应
void PostOrderN();                  //与protected中的PostOrderN对应
void Delete(T x);                   //与pretected中的DeleteIn对应
protected:
void CountIn(BiNode<T> *root);
void Creat(BiNode<T> * &root, T none);
BiNode<T> *Build(T ary[], int num, T none, int idx);
BiNode<T> *ParentIn(BiNode<T> * root, T x);               //查询某结点的双

亲
void Release(BiNode<T>* &root);
void printIn(ostream &os, BiNode<T> *root, int depth); //和上述的四个函数

具有对应的功能
void PreOrderPrintIn(BiNode<T> *root); //求二叉树的叶子节

点输出
int DepthIn(BiNode<T> *root); //求二叉树的深度
void PostOrderNIn(BiNode<T> *root); //求二叉树的逆后

序输出遍历的算法
void DeleteIn(BiNode<T> * root, T x); //求二叉树的删除

的算法

private:
BiNode<T> *p = NULL;
BiNode<T> *rootPtr;                //申请一个跟指针
int count = 0;                     //全局变量在Count函数中用
int highl = 0,highr=0;                      //全局变量在Depth函数中用
};
template<typename T>
void BiTree<T>::CountIn(BiNode<T> *root)
{
if (root != NULL)
{
  CountIn(root->lchild);
  count++;
  CountIn(root->rchild);
  /*在左右之间count++是在左子数递归结束之时才加
  在最后一个左子数结束的时候就是+*/
}
}
template<typename T>
void BiTree<T>::Creat(BiNode<T> * &root, T none)            //子数的创建
{
T x;
cout << "请输入（" << none << "表示空）:"; cin >> x;
if (x == none)
  root == NULL;                 //如果输入的是空的话，那么这个二叉树

就是空二叉树
else                              //下面准备实现元素的插入
{
  root = new BiNode<T>;         //首先让根指针变为根结点
  root->data = x;               //对结点进行赋值
  Creat(root->lchild, none);    //创建根结点的左子数，此时左子数为空
  Creat(root->rchild, none);    //创建根结点的右子数，此时右子数为空
}                                 //当前结点赋值成功，且其子数创建也成功
}                                     //次函数不是循环创建，只是在根结点进行赋值与

子数的创建，下面的操作靠其他
template<typename T>
BiNode<T> *BiTree<T>::Build(T ary[], int num, T none, int idx)
{
/*ary就表示数组，num表示数组长度，none表示空，idx表示结点的序号
在进行第一次操作的时候理所应当的赋值为1*/
BiNode<T> *p;                     //申请指针p
int left, right;                  //定义左右
if (idx - 1 < num&&ary[idx - 1] != none)//为什么此处是idx-1呢？？？？
{
  /*因为数组从0开始，又为了idx能够按倍数增长，所以idx从一开始
  则在判断的时候自然就要减去一了，方便后面的赋值*/
  p = new BiNode<T>;            //将指针p结点划
  p->data = ary[idx - 1];       //将该结点的数值部分赋值为数组中对应

的元素
  left = 2 * idx;
  right = 2 * idx + 1;          //确保了左右子数的左右性
  p->lchild = Build(ary, num, none, left);
  p->rchild = Build(ary, num, none, right);//开始进行赋值
  return p;
}
else
  return NULL;          //else表示数组已经赋值完了，没有值在来扩建了

所以就返回空
}
template<typename T>
void BiTree<T>::Release(BiNode<T> * & root)//有释放的意思
{
if (root != NULL)                      //首先从根结点开始
{
  Release(root->lchild);
  Release(root->rchild);
  delete root;                      //后续遍历性的释放
}
}
template<typename T>
void BiTree<T>::Count()
{
CountIn(rootPtr);
cout << "|" << setw(5) << "该树结点数为:" << count <<setw(5)<< "|" <<

endl;
}
template<typename T>
BiTree<T>::BiTree(T none)
{
Creat(rootPtr, none);
}
template <typename T>
BiTree<T>::BiTree(T ary[], int num, T none)
{
rootPtr = Build(ary, num, none, 1);   //none用来传递空
}
template <typename T>
BiTree<T>::~BiTree()
{
Release(rootPtr);
}
template <typename T>
void BiTree<T>::printIn(ostream &os, BiNode<T> *root, int depth)
{
if (root != NULL)
{
  printIn(os, root->rchild, depth + 1);
  for (int i = 0; i < 4 * (depth - 1); i++)
   os << " ";
  os << "*--" << root->data << endl;   //这句是函数共同所有
  printIn(os, root->lchild, depth+1);

}
}
template<typename T>
void BiTree<T>::PreOrderPrintIn(BiNode<T> *root)
{
if (root != NULL)
{
if (root->lchild==NULL&&root->rchild==NULL)
cout <<setw(3)<< root->data; //先输出根结点

数据
  PreOrderPrintIn(root->lchild);        //然后在开始进行左结点输出
  PreOrderPrintIn(root->rchild);        //然后右结点输出
}
}
template<typename T>
void BiTree<T>::PreOrderPrint()
{
PreOrderPrintIn(rootPtr);
}
template<typename T>
int BiTree<T>::DepthIn(BiNode<T> *root)
{
if (root == NULL)return 0;       //标志访问结束
else                             //标志继续向下访问
{
  highl = DepthIn(root->lchild);//为何在这一步就可以进行赋值？
  highr = DepthIn(root->rchild);
  if (highl > highr)
   return highl + 1;
  else
   return highr + 1;
}
}
template<typename T>
void BiTree<T>::Depth()
{
cout<<DepthIn(rootPtr);
}
template<typename T>
void BiTree<T>::PostOrderNIn(BiNode<T> * root)
{
if (root != NULL)
{
  cout << setw(3) << root->data;
  PostOrderNIn(root->rchild);
  PostOrderNIn(root->lchild);
}
}
template<typename T>
void BiTree<T>::PostOrderN()
{
PostOrderNIn(rootPtr);
}
template<typename T>
BiNode<T> *BiTree<T>::ParentIn(BiNode<T> *root, T x)
{
if (root != NULL)
{
  if (root->data == x)cout<<p->data;
  else
  {
   p = root;
   ParentIn(root->lchild, x);
   ParentIn(root->rchild, x);
  }
}
return 0;
}
template<typename T>
void BiTree<T>::Parent(T x)
{
ParentIn(rootPtr, x);
}
template<typename T>
void BiTree<T>::DeleteIn(BiNode<T> * root, T x)
{
if (root != NULL)
{
  if (root->data == x)
  {
   if (p == NULL)
    root = NULL;
   else
   if (p->lchild == root)
    p->lchild = NULL;
   else
    p->rchild = NULL;
  }
  else
  {
   p = root;
   DeleteIn(root->lchild, x);
   DeleteIn(root->rchild, x);
  }
}
}
template<typename T>
void BiTree<T>::Delete(T x)
{
DeleteIn(rootPtr, x);
}
template<typename T>
void BiTree<T>::print(ostream & os)
{
printIn(os, rootPtr, 1);
}
template<typename T>
ostream & operator<<(ostream & os, BiTree<T> &bt)
{
bt.print(os);
return os;
}
#endif
************************************************************************
#include"BiTree.h"
#include<iostream>
using namespace std;
void main()
{
char ary[] = { ‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘#‘,
                            ‘E‘, ‘F‘, ‘#‘, ‘G‘, ‘#‘,
          ‘#‘, ‘H‘, ‘I‘,

‘J‘, ‘K‘,
‘#‘, ‘#‘, ‘L‘ };
char zxh,gmy;
BiTree<char> myBTree(ary, 18, ‘#‘);
cout << myBTree << endl;
cout << "--------------------------------------------------" << endl;
//cout << "++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << "求二叉树结点个数(第一题算法)" << endl;
myBTree.Count();
//cout << "++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << "--------------------------------------------------" << endl;
//cout << "++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << "求二叉树叶子节点次序(第二题算法)"<<endl;
cout << "该树的叶子结点按前序次序de方式排列输出为:";
myBTree.PreOrderPrint();
cout << endl;
//cout << "++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << "--------------------------------------------------" << endl;
cout << "求二叉树深度(第三题揭发):" << endl;
cout << "这个二叉树的深度为:"<<endl;
myBTree.Depth();
cout << "--------------------------------------------------" << endl;
cout << "求二叉树后序逆遍历(第四道题解法):" << endl;
cout << "该二叉树的逆向后序遍历为:" << endl;
myBTree.PostOrderN();
cout << "--------------------------------------------------" << endl;
cout << "求二叉树某结点双亲(第五道题解法):" << endl;
cout << "请输入您想查询的结点(！注：区分大小写):";
cin >> zxh;
cout << "您查询的结点为:" << zxh << "他的双亲为:" << endl;
myBTree.Parent(zxh);
cout << endl;
cout << "--------------------------------------------------" << endl;
cout << "请输入您想删除的字符:";
cin >> gmy;
myBTree.Delete(gmy);
cout << "删除后的二叉树为:" << endl;
cout << myBTree;
}
*****************************************************************************
个人小结：
第一次接触到二叉树这个东西，我明显的感觉到了与前面学的顺序表单链表有所不同了，最大