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

二叉树是程序应用得比较多的一种结构。它可以反映物体之间的层次结构，还能通过孩子和双亲反映两物体之间某些特殊关系；排序二叉树还能帮助我们进行排序，并因此而提供快速的查找；二叉树基础上的伸展树能不断地优化我们系统的结构。并查集能很好地让进行分类；小根堆能帮助快速找到值最小的结点，它是优先队列的雏形。所有的这些都是以二叉树为基础的。

实现的二叉树的基本功能包括前中后序的递归和非递归访问，求结点个数和叶子结点个数，还有求树高。这些是用C++类实现的。

BTreeh文件(类声明文件)
[cpp] view plain copy
#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  
BTreecpp(类的实现文件)
[cpp] view plain copy
#include <iostream>  
#include <stack>  
#include <queue>  
#include "BTreeh"  
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(!sempty()||r!=0)  
    {  
        while(r!=0)  
        {  
            spush(r);  
            r=r->lChild;  
        }  
  
        if(!sempty())  
        {  
            r=stop();  
            spop();  
            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();  
    spush(r);  
  
    while(!sempty())  
    {  
        r=stop();  
        spop();  
  
        cout<<r->data<<" ";  
  
        if(r->rChild!=0)  
            spush(r->rChild);  
        if(r->lChild!=0)  
            spush(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(!sempty()||r!=0)  
    {  
        while(r!=0)  
        {  
            nodetp=r;  
            nodeflag=0;  
            spush(node);  
            r=r->lChild;  
        }  
  
        if(!sempty())  
        {  
            node=stop();  
            spop();  
            r=nodetp; //将栈顶的BTreeNode部分赋给r  
            if(nodeflag==1)  
            {  
                cout<<r->data<<" ";  
                r=0; //表示已经访问了该结点  
            }  
            else  
            {  
                nodeflag=1;  
                spush(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;  
    tempptr=r;  
    tempheight=1;  
    quepush(temp); //先将根对应的LayerBTreeNode对象进队  
      
    //不为空时  
    while(!queempty())  
    {  
        //BTreeNode btreePtr=0;  
  
        temp=quefront(); //取出队首元素  
        quepop();  
          
        r=tempptr;  
  
        //用当前的高度跟取出的队首进行比较  
        if(hei<tempheight)  
                hei=tempheight;  
  
        if(r->lChild!=0||r->rChild!=0)  
        {  
            //如果它的左右子树不为空，则进队列  
            if(r->lChild!=0)  
            {  
                lTempptr=r->lChild;  
                lTempheight=tempheight+1; //在原来高度基础上加1,再入队列  
                quepush(lTemp);  
            }  
            if(r->rChild!=0)  
            {  
                rTempptr=r->rChild;  
                rTempheight=tempheight+1;  
                quepush(rTemp);  
            }  
  
        }  
    }  
    return hei;  
}

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。
第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等 *** 作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加timeh里的几个函数，配合使用下就出来了。
#include <stdioh>
#include <stdlibh>
// binary search tree
typedef struct BST
{
int data;
struct BST lhs;
struct BST rhs;
}BST;
// 插入一个节点
BST BSTInsertNode(BST root, int elem)
{
BST node;
node = (BST)malloc(sizeof(BST));
node->data = elem;
node->lhs = node->rhs = 0;

if(!root)
return node;

while(1)
{
if(node->data < root->data)
{
if(root->lhs)
root = root->lhs;
else
{
root->lhs = node;
return root->lhs;
}
}
else
{
if(root->rhs)
root = root->rhs;
else
{
root->rhs = node;
return root->rhs;
}
}
}
}
// 获得父节点
BST BSTGetParentNode(BST root, BST node)
{
if(root == node)
return 0;

if(root->lhs && node->data < root->lhs->data)
return BSTGetParentNode(root->lhs, node);
else if(root->rhs && node->data > root->rhs->data)
return BSTGetParentNode(root->rhs, node);
else
return root;
}
// 删除一个节点
BST BSTDeleteNode(BST root, BST node)
{
BST parent;
BST whichNode;
BST temp;

if(root != node)
{

parent = BSTGetParentNode(root, node);
whichNode = parent->lhs == node &parent->lhs : &parent->rhs;
}
else
whichNode = &root;
if(!node->lhs && !node->rhs)
whichNode = 0;
else if(!((node->lhs 1 : 0) ^ (node->rhs 1 : 0)))
whichNode = node->lhs node->lhs : node->rhs;
else
{
temp = node->rhs;
while(temp->lhs)
temp = temp->lhs;
temp->lhs = node->lhs;
whichNode = node->rhs;
}
free(node);
return whichNode;
}
// 删除树
void BSTDeleteTree(BST node)
{
if(node)
{
BSTDeleteTree(node->lhs);
BSTDeleteTree(node->rhs);
free(node);
}
}
// 建造树，从数组构造
BST BSTBuildTree(int beg, int end)
{
BST root;

if(beg >= end)
return 0;

root = (BST)malloc(sizeof(BST));
root->data = beg++;
root->lhs = root->rhs = 0;

while(beg != end)
BSTInsertNode(root, beg++);

return root;
}
// 查找节点
BST BSTSearchNode(BST root, int elem)
{
if(root)
{
if(elem < root->data)
return BSTSearchNode(root->lhs, elem);
else if(elem > root->data)
return BSTSearchNode(root->rhs, elem);
else
return root;
}
else
return 0;
}
// 获得最小值
BST BSTGetMinimumNode(BST root)
{
while(root->lhs)
root = root->lhs;
return root;
}
// 获得最大值
BST BSTGetMaximumNode(BST root)
{
while(root->rhs)
root = root->rhs;
return root;
}
// 前序遍历
void BSTPreorderTraverse(BST node)
{
if(node)
{
printf("%d ", node->data);
BSTPreorderTraverse(node->lhs);
BSTPreorderTraverse(node->rhs);
}
}
// 中序遍历
void BSTInorderTraverse(BST node)
{
if(node)
{
BSTInorderTraverse(node->lhs);
printf("%d ", node->data);
BSTInorderTraverse(node->rhs);
}
}
// 后序遍历
void BSTPostorderTraverse(BST node)
{
if(node)
{
BSTPostorderTraverse(node->lhs);
BSTPostorderTraverse(node->rhs);
printf("%d ", node->data);
}
}
// 获得前继值
BST BSTGetPredecessor(BST root, BST node)
{
BST predecessor;
BST rightCld;

if(node->lhs)
return BSTGetMaximumNode(node->lhs);

predecessor = rightCld = node;
while((predecessor = BSTGetParentNode(root, predecessor)))
if(predecessor->rhs == rightCld)
return predecessor;
else
rightCld = predecessor;
return 0;
}
// 获得后继值
BST BSTGetSuccessor(BST root, BST node)
{
BST successor;
BST leftCld;

if(node->rhs)
return BSTGetMinimumNode(node->rhs);

successor = leftCld = node;
while((successor = BSTGetParentNode(root, successor)))
if(successor->lhs == leftCld)
return successor;
else
leftCld = successor;
return 0;
}
// 获得树高
int BSTGetTreeHeight(BST root)
{
int l;
int r;
if(root)
{
l = BSTGetTreeHeight(root->lhs);
r = BSTGetTreeHeight(root->rhs);
return 1 + (l > r l : r);
}
else
return -1;
}
// 计算子节点数
int BSTGetSubtreeNodeNum(BST node)
{
if(node)
return BSTGetSubtreeNodeNum(node->lhs)
+ BSTGetSubtreeNodeNum(node->rhs)
+ 1;
else
return 0;
}
// 用于打乱数组，交换
inline void Swap(int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
}
// 用于打乱数组，qsort的比较用过程
inline int CMP(const void lhs, const void rhs)
{
return (const int)lhs - (const int)rhs;
}
// 数组有序
int IsOrdered(int beg, int end)
{
int attri;
int cmpVal;
if(beg >= end)
return 0;
if(end - beg <= 2)
return 1;

if(beg < (beg + 1))
attri = 1;
else
attri = 0;

cmpVal = beg++;
while(++beg != end)
{
if(attri)
{
if(cmpVal > beg)
return 0;
}else
{
if(cmpVal < beg)
return 0;
}
}
return 1;
}
// 高层次打乱数组
void HighlyUnorderArray(int beg, int end)
{

int mid = beg + (end - beg)/2;
int folk;
if(!IsOrdered(beg, end))
qsort(beg, end - beg, sizeof(int), CMP);

if((mid - beg) & 1)
Swap(beg++, mid);
folk = beg + 2;
while(folk < mid)
{
Swap(beg++, folk++);
Swap(beg++, folk++);
}

folk = mid + 2;
while(folk < end)
{
Swap(folk, folk - 1);
folk += 2;
}
}
// 中序遍历结果输出到数组
void BSTInorderWalkToArray(BST root, int p)
{
if(root)
{
BSTInorderWalkToArray(root->lhs, p);
p = root->data;
(p)++;
BSTInorderWalkToArray(root->rhs, p);
}
}
// 平衡树，返回平衡好的新树
BST BSTBalanceTree(BST root)
{
int size = BSTGetSubtreeNodeNum(root);
int a = (int)malloc(sizeof(int) size);
int end = a;
BST balancedTree;

BSTInorderWalkToArray(root, &end);
HighlyUnorderArray(a, end);
balancedTree = BSTBuildTree(a, end);
free(a);
return balancedTree;
}
int main()
{
int a[] = {5,6,3,7,9,8,1,0,4,2};
int c[] = {50,17,76,9,23,54,14,19,72,12,67};
BST bstTree = BSTBuildTree(a, a + sizeof(a)/sizeof(a[0]));

BSTPreorderTraverse(bstTree);
putchar('\n');
BSTInorderTraverse(bstTree);
putchar('\n');
BSTPostorderTraverse(bstTree);
printf("\n\n");

BST balancedTree = BSTBalanceTree(bstTree);
printf("%d %d\n", BSTGetTreeHeight(bstTree), BSTGetTreeHeight(balancedTree));
BSTDeleteTree(bstTree);
BSTDeleteTree(balancedTree);
}

#include<iostreamh>
#include <stdioh>
#include <stdlibh>
typedef struct node {
char data;
struct node lchild,rchild;//
}BiTNode,BiTree;
void CreatBiTree(BiTree &T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode)malloc(sizeof(BiTNode));
T->data=ch;//生成根节点
CreatBiTree(T->lchild);//构造左子树
CreatBiTree(T->rchild);//构造右子树
}
}
void preorder(BiTree T)//前序遍历
{
if (T!=NULL){
printf ("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree T)//中序遍历
{
if (T!=NULL){
inorder(T->lchild);
printf ("%c",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T)//后序遍历
{
if (T!=NULL){
postorder(T->lchild);
postorder(T->rchild);
printf ("%c",T->data);
}
}
void main ()
{
cout<<"请输入要创建的二叉树包括空格:"<<endl ;
BiTree T;
CreatBiTree(T);//创建二叉树
cout<<"前序遍历的结果为:"<<endl;
preorder(T);
cout<<endl;
cout<<"中序遍历的结果为:"<<endl;
inorder(T);
cout<<endl;
cout<<"后序遍历的结果为:"<<endl;
postorder(T);
}

---