二叉樹是程序應用得比較多的一種結構。它可以反映物體之間的層次結構，還能通過孩子和雙親反映兩物體之間某些特殊關系；排序二叉樹還能幫助我們進行排序，並因此而提供快速的查找；二叉樹基礎上的伸展樹能不斷地優化我們系統的結構。並查集能很好地讓我們進行分類；小根堆能幫助我們快速找到值最小的結點，它是優先隊列的雛形。所有的這些都是以二叉樹為基礎的。
我實現的二叉樹的基本功能包括前中後序的遞歸和非遞歸訪問，求結點個數和葉子結點個數，還有求樹高。這些是用C++類實現的。
BTree.h文件(類聲明文件)
#ifndef BTREE_H
#define BTREE_H
struct BTreeNode
{
int data;
BTreeNode *lChild,*rChild;
};
class BTree
{public:
void setRoot(BTreeNode* r){ root=r;}
BTreeNode* getRoot(){ return root;}
//中序遍歷(遞歸)
void inOrder();
//中序遍歷(非遞歸)
void NotReInOrder();
BTreeNode* createBTree();
//前序遍歷(遞歸)
void preOrder();
//前序遍歷(非遞歸)
void NotRePreOrder();
//後序遍歷(遞歸)
void postOrder();
//後序遍歷(非遞歸)
void NotRePostOrder();
//求結點個數
int BTreeSize();
//求葉子結點個數
int BTreeLeaves();
//求樹高
int BTreeHeight();
//層次法求樹高
int layerHeight();
protected:
//中序遍歷
void inOrder(BTreeNode*);
//前序遍歷
void preOrder(BTreeNode*);
//後序遍歷
void postOrder(BTreeNode*);
//結點個數
int BTreeSize(BTreeNode*);
//葉子結點
int BTreeLeaves(BTreeNode*);
//樹高
int BTreeHeight(BTreeNode*);
private:
BTreeNode* root;
};
#endif
BTree.cpp(類的實現文件)
#include <iostream>
#include <stack>
#include <queue>
#include "BTree.h"
using namespace std;
//建立二叉樹的算法
BTreeNode* BTree::createBTree()
{
BTreeNode* current=0;
int val=0;
cin>>val;
//-1的個數比數值的個數多1
if(val==-1)
return NULL;
else
{
current=new BTreeNode;
current->data=val;
current->lChild=createBTree();
current->rChild=createBTree();
return current;
}
}
//利用重載的方法
void BTree::inOrder()
{
inOrder(root);
cout<<endl;
}
//中序訪問二叉樹(遞歸)
void BTree::inOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
inOrder(r->lChild); //遞歸訪問
cout<<r->data<<" ";
inOrder(r->rChild); //遞歸訪問
}
}
//中序遍歷(非遞歸)
void BTree::NotReInOrder()
{
stack<BTreeNode*> s;
BTreeNode* r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
s.push(r);
r=r->lChild;
}
if(!s.empty())
{
r=s.top();
s.pop();
cout<<r->data<<" ";
r=r->rChild;
}
}
}
//重載形式
void BTree::preOrder()
{
preOrder(root);
cout<<endl;
}
//前序遞歸訪問二叉樹(遞歸)
void BTree::preOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
cout<<r->data<<" ";
preOrder(r->lChild); //遞歸訪問
preOrder(r->rChild); //遞歸訪問
}
}
//前序遍歷(非遞歸)
void BTree::NotRePreOrder()
{
stack<BTreeNode*> s;
BTreeNode* r=getRoot();
s.push(r);
while(!s.empty())
{
r=s.top();
s.pop();
cout<<r->data<<" ";
if(r->rChild!=0)
s.push(r->rChild);
if(r->lChild!=0)
s.push(r->lChild);
}
}
//重載形式
void BTree::postOrder()
{
postOrder(root);
cout<<endl;
}
//後序遍歷(遞歸)
void BTree::postOrder(BTreeNode* r)
{
if(r!=0) //是if，而不是while
{
postOrder(r->lChild); //遞歸訪問
postOrder(r->rChild); //遞歸訪問
cout<<r->data<<" ";
}
}
//後序非遞歸訪問要定義新的結構體類型
struct Node
{
BTreeNode* tp;
bool flag;
};
//後序遍歷(非遞歸)
void BTree::NotRePostOrder()
{
Node node; //定義Node結構體的一個結點
stack<Node> s;
BTreeNode* r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
node.tp=r;
node.flag=0;
s.push(node);
r=r->lChild;
}
if(!s.empty())
{
node=s.top();
s.pop();
r=node.tp; //將棧頂的BTreeNode*部分賦給r
if(node.flag==1)
{
cout<<r->data<<" ";
r=0; //表示已經訪問了該結點
}
else
{
node.flag=1;
s.push(node);
r=r->rChild;
}
}
}
}
//重載形式
int BTree::BTreeSize()
{
return BTreeSize(root);
}
//求二叉樹結點個數的函數
int BTree::BTreeSize(BTreeNode* r)
{
//二叉樹的結點個數為左右子樹的高度之和再+1
if(r==0) return 0;
else
return 1+BTreeSize(r->lChild)+BTreeSize(r->rChild);
}
//重載形式
int BTree::BTreeLeaves()
{
return BTreeLeaves(root);
}
//求二叉樹葉子結點個數的函數
int BTree::BTreeLeaves(BTreeNode* r)
{
//當為空時，返回0；當找到葉子時返回1
if(r==0) return 0;
else
if(r->lChild==0&&r->rChild==0)
return 1;
else
return BTreeLeaves(r->lChild)+BTreeLeaves(r->rChild);
}
//重載形式
int BTree::BTreeHeight()
{
return BTreeHeight(root);
}
//求二叉樹高度的函數
int BTree::BTreeHeight(BTreeNode* r)
{
if(r==0) return 0;
else
{
//二叉樹的高度為左右子樹的最大者+1
int lHei=BTreeHeight(r->lChild);
int rHei=BTreeHeight(r->rChild);
return (lHei>rHei) ? lHei+1:rHei+1;
}
}
//層次遍歷求樹高需要利用的新結構
struct LayerBTreeNode
{
BTreeNode* ptr;
int height;
};
//層次遍歷求高度
int BTree::layerHeight()
{
queue<LayerBTreeNode> que;
LayerBTreeNode temp,lTemp,rTemp; //犧牲空間來獲得算法的清晰度
BTreeNode* r=getRoot();
int hei=1;
temp.ptr=r;
temp.height=1;
que.push(temp); //先將根對應的LayerBTreeNode對象進隊
//不為空時
while(!que.empty())
{
//BTreeNode* btreePtr=0;
temp=que.front(); //取出隊首元素
que.pop();
r=temp.ptr;
//用當前的高度跟取出的隊首進行比較
if(hei<temp.height)
hei=temp.height;
if(r->lChild!=0||r->rChild!=0)
{
//如果它的左右子樹不為空，則進隊列
if(r->lChild!=0)
{
lTemp.ptr=r->lChild;
lTemp.height=temp.height+1; //在原來高度基礎上加1,再入隊列
que.push(lTemp);
}
if(r->rChild!=0)
{
rTemp.ptr=r->rChild;
rTemp.height=temp.height+1;
que.push(rTemp);
}
}
}
return hei;
}