二叉树的常见操作

时间:2022-06-02 00:22:56

数据结构中树这一块儿一直是个难点和考点,刚好前几天在面实习生,面试过程中问到了二叉树并让写出代码,就想自己再写一遍二叉树的常见操作,目的为了留着以后用起来方便,于是乎,拿起书本又看了一遍,写下这些代码,编译环境是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;
}