数据结构中树这一块儿一直是个难点和考点，刚好前几天在面实习生，面试过程中问到了二叉树并让写出代码，就想自己再写一遍二叉树的常见操作，目的为了留着以后用起来方便，于是乎，拿起书本又看了一遍，写下这些代码，编译环境是VS2012。
在Btree.h中的有下列声明和定义：
typedef struct BtNode//二叉树的数据结构
{
char data;
struct BtNode*lchild,*rchild;
}BtNode,*BTree;
void CreateBTree(BTree& Bt);//二叉树的创建
void PreOrder(BTree &Bt);//二叉树前序遍历
void PreOrderNon(BTree &Bt);//二叉树前序非递归遍历
void MidOrder(BTree &Bt);//二叉树中序遍历
void MidOrderNon(BTree &Bt);//二叉树非递归中序遍历
void LastOrder(BTree &Bt);//二叉树后序遍历
void LastOrderNon(BTree &Bt);//二叉树非递归后序遍历
void LevelOrder(BTree &Bt);//二叉树层次遍历
BtNode * CommonParent1(BtNode *root,BtNode *bt1,BtNode *bt2);//求最近公共父节点
int Depth(BTree &Bt);//二叉树的深度
int leafCount(BTree &Bt);//二叉树叶子节点的个数
void Exchagechild(BTree &Bt);//交换二叉树的左右孩子
bool IsBalanceTree(BTree &Bt);//是否为平衡二叉树
void DestroyTree(BtNode *Bt);//二叉树的销毁
在BTree.cpp中有一下函数实现：
#include<iostream>
#include"Btree.h"
#include<stack>
#include<queue>
using namespace std;
//先序创建二叉树
void CreateBTree(BTree &Bt)
{
char ch;
cin>>ch;
if(ch == '#') Bt=NULL;
else
{
Bt = new BtNode;
Bt->data = ch;
CreateBTree(Bt->lchild);//递归创建左子树
CreateBTree(Bt->rchild);//递归创建右子树
}
}
//递归先序遍历
void PreOrder(BTree &Bt)
{
if(Bt == NULL) return ;
cout<<Bt->data<<" ";
PreOrder(Bt->lchild);
PreOrder(Bt->rchild);
}
//非递归先序遍历
void PreOrderNon(BTree &Bt)
{
if (Bt == NULL) return ;
stack<BTree> s;
BTree p = Bt;
while(!s.empty() || p != NULL)
{
if( p != NULL)
{
cout<<p->data<<" ";
s.push(p);
p = p->lchild;
}
if(!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}
//递归中序遍历
void MidOrder(BTree &Bt)
{
if (Bt == NULL) return ;
MidOrder(Bt->lchild);
cout<<Bt->data<<" ";
MidOrder(Bt->rchild);
}
//非递归中序遍历
void MidOrderNon(BTree &Bt)
{
if(Bt == NULL) return ;
BTree p = Bt;
stack<BTree> s;
while( p != NULL || !s.empty() )
{
while( p != NULL)
{
s.push(p);
p = p->lchild;
}
if(!s.empty())
{
p = s.top();
s.pop();
cout<<p->data<<" ";
p = p->rchild;
}
}
}
//递归后序遍历
void LastOrder(BTree &Bt)
{
if(Bt== NULL) return ;
LastOrder(Bt->lchild);
LastOrder(Bt->rchild);
cout<<Bt->data<<" ";
}
//非递归后序遍历
void LastOrderNon(BTree &Bt)
{
if(Bt == NULL) return ;
stack<BTree> s;
BTree p = Bt;
BTree visted = NULL;
while(p != NULL || !s.empty())
{
while(p != NULL)
{
s.push(p);
p = p->lchild;
}
p = s.top();
if(p->rchild == NULL || p->rchild == visted)
{
cout<<p->data<<" ";
visted = p;
s.pop();
p = NULL;
}
else
{
p = p->rchild;
}
}
}
//层次遍历
void LevelOrder(BTree &Bt)
{
queue<BTree> q;
BTree temp = NULL;
if(Bt != NULL) q.push(Bt);
while(!q.empty())
{
temp = q.front();
q.pop();
cout<<temp->data<< " ";
if(temp->lchild != NULL)
{
q.push(temp->lchild);
}
if(temp->rchild != NULL)
{
q.push(temp->rchild);
}
}
}
//求公共父节点,已知两个子节点
BtNode * CommonParent(BtNode *root,BtNode *bt1,BtNode *bt2)
{
if(root == NULL)
return NULL;
if(bt1 == root || bt2 == root)
return root;
BtNode *left = CommonParent(root->lchild,bt1,bt2);
BtNode*right = CommonParent(root->rchild,bt1,bt2);
if(left && right )
return root;
return left ?left:right;
}
//二叉树深度
int Depth(BTree &Bt)
{
if(Bt == NULL ) return 0;
int len1 = Depth(Bt->lchild);
int len2 = Depth(Bt->rchild);
return len1>len2?len1+1:len2+1;
}
//叶子节点总数
int leafCount(BTree &Bt)
{
if(Bt == NULL) return 0;
if(Bt->lchild== NULL && Bt->rchild == NULL)
{
return 1;
}
return leafCount(Bt->lchild)+leafCount(Bt->rchild);
}
//交换左右孩子
void Exchagechild(BTree &Bt)
{
if(Bt == NULL) return ;
BTree temp = NULL;
if(Bt->lchild || Bt->rchild)
{
temp = Bt->lchild;
Bt->lchild = Bt->rchild;
Bt->rchild = temp;
Exchagechild(Bt->lchild);
Exchagechild(Bt->rchild);
}
}
//是否是平衡二叉树
bool IsBalanceTree(BTree &Bt)
{
if(Bt == NULL)
return true;
int ldepth = Depth(Bt->lchild);
int rdepth = Depth(Bt->rchild);
int dis = ldepth-rdepth;
if(dis >1 || dis <-1)
return false;
return IsBalanceTree(Bt->lchild) && IsBalanceTree(Bt->rchild);
}
//销毁树
void DestroyTree(BtNode *Bt)
{
if(Bt == NULL)
return ;
DestroyTree(Bt->lchild);
DestroyTree(Bt->rchild);
delete Bt;
}
int main()
{
BTree T;
CreateBTree(T);
cout<<"PreOrder:";
PreOrder(T);
cout<<endl;
cout<<"MidOrder:";
MidOrder(T);
cout<<endl;
cout<<"LastOrder:";
LastOrder(T);
cout<<endl;
cout<<"PreOrderNon:";
PreOrderNon(T);
cout<<endl;
cout<<"LevelOrder:";
LevelOrder(T);
cout<<endl;
cout<<"leafCount:";
cout<<leafCount(T)<<endl;
cout<<"Depth:";
cout<<Depth(T)<<endl;
cout<<"Exchangechild:";
Exchagechild(T);
PreOrder(T);
cout<<endl;
cout<<"MidOrderNon:";
MidOrderNon(T);
cout<<endl;
cout<<"LastOrderNon:";
LastOrderNon(T);
cout<<endl;
cout<<"IsBalanceTree:";
if(IsBalanceTree(T))
cout<<"IsBanlanceTree"<<endl;
else
cout<<"IsNotBanlanceTree"<<endl;
cout<<"CommonParent:";
cout<<(CommonParent(T,T->lchild->lchild,T->rchild->rchild))->data;
cout<<endl;
return 0;
}