tree.h

C++应用教程原码,里面包含该书中有十三章内容的代码,详细具体

template <class Type>
class treeNode {
     public:
       Type data;  // 结点的值域
       treeNode(const Type& item, treeNode<Type> *lptr = NULL,treeNode<Type> *rptr = NULL)
		   : data(item), left(lptr), right(rptr) {}
       treeNode <Type> *& Left() { return left; };
       treeNode <Type> *& Right() { return right; };
     private:
       treeNode <Type> * left;
        treeNode <Type> * right;
};

template <class Type>
class Tree {
  public:
    Tree() : root(NULL) {}
    ~Tree();
    treeNode <Type> *root;
    void traversalPreOrder(treeNode<Type> *p );  // 先序遍历
    void traversalInOrder(treeNode<Type> *p);   // 中序遍历
    void traversalPostOrder(treeNode<Type> *p); // 后序遍历
    void makeTree(int i, int j, int L, int u,treeNode <Type> *&p);  // 利用二叉树的性质构造一棵二叉树
	void leafCount(treeNode<Type> *&p,int& number);
  private:
    treeNode <Type> * getTreeNode (const Type& item, treeNode<Type> *lptr = NULL,treeNode<Type> *rptr = NULL);
    void freeTreeNode (treeNode <Type> *p);

};

template <class Type>
Tree <Type> :: ~Tree()
{freeTreeNode(root);}

template <class Type>
treeNode <Type> * Tree <Type> :: getTreeNode (const Type& item, treeNode<Type> *lptr = NULL, treeNode<Type> *rptr = NULL)
{     treeNode < Type > *p;
      p = new treeNode<Type>(item, lptr, rptr);  // 左右指针域均为NULL
      if ( p == NULL)
        { cout << "无法创建新的树结点！"<<endl;
          exit(-1);
        }
      return p;
}

template <class Type>
void Tree <Type> :: freeTreeNode (treeNode <Type> *p)
{  if (p!=NULL)
     { freeTreeNode(p->Left());
       freeTreeNode(p->Right());	
       delete p;
	 }
}

template <class Type>
void Tree <Type> :: makeTree(int i, int j, int L, int u,treeNode <Type> *&p)
{  int m, k;
   bool find=false;
   if (i>j) 
      p = NULL;
   else
     { p = getTreeNode(A[i]);
       m = L; k = 0;
       while (m <= u)
        { if (B[m] == A[i])
           { k = m;
             m = u+1;
		     find = true;
			 break;
           }
          else m++;
		}
       if (find == false)
        { cout << "没有在中序序列中找到元素"<<A[i]<<endl;
	      exit(-1);
        }
       else
        { makeTree(i+1, i+k-L, L, k-1, p->Left());
          makeTree(i+k-L+1, j, k+1, u, p->Right());
        }
      
	 }
 }
template <class Type>
void Tree <Type> :: traversalPreOrder(treeNode<Type> *p)
{ 
  if (p != NULL)
  { cout << setw(5) << p->data;
    traversalPreOrder (p->Left());
    traversalPreOrder (p->Right());
   }
}
template <class Type>
void Tree <Type> :: traversalInOrder(treeNode<Type> *p)
{ 
  if (p != NULL)
  { 
    traversalInOrder (p->Left());
	cout << setw(5) << p->data;
    traversalInOrder (p->Right());
   }
}
template <class Type>
void Tree <Type> :: traversalPostOrder(treeNode<Type> *p)
{ 
  if (p != NULL)
  { 
    traversalPostOrder (p->Left());
    traversalPostOrder (p->Right());
	cout << setw(5) << p->data;
   }
}