#include<iostream>
#include<queue>
#include<stack>
#include"BinaryTree.h"
#define NULL 0
using namespace std;
BinaryTree::BinaryTree(){//构造函数
root=NULL;
}
bool BinaryTree::InitBiTree(){//构造空二叉树
if(!root) return true;
else
return false;
}
bool BinaryTree::DestroyBiTree(BiTree& p){//销毁二叉树T
if(p){
DestroyBiTree(p->lchild);
DestroyBiTree(p->rchild);
delete p;
if(p==root) p=NULL;
}
return true;
}
bool BinaryTree::CreateBiTree(BiTree& p){//先序创建二叉树T
char c;
cin>>c;
if(c=='$') p=NULL;
else{
p=new BiTNode;
if(!p) return false;
p->data=c;
CreateBiTree(p->lchild);
CreateBiTree(p->rchild);
}
return true;
}
bool BinaryTree::ClearBiTree(BiTree& p){//清空二叉树
if(p){
ClearBiTree(p->lchild);
p->data='*'; //给节点赋值*表示该节点被清空
ClearBiTree(p->rchild);
}
return true;
}
bool BinaryTree::BiTreeEmpty(){//判断二叉树是否为空树
if(!root) return true;
else return false;
}
int BinaryTree::BiTreeDepth(BiTree& p){//求二叉树的深度
if(!p) return 0;
int a=BiTreeDepth(p->lchild);
int b=BiTreeDepth(p->rchild);
return a>b? a+1:b+1;
}
BiTree& BinaryTree::Root(){//返回二叉树的根节点
return root;
}
BiTree BinaryTree::Value(char e,BiTree& p){//返回二叉树中节点e的值(不需要实现)
BiTree x=Search(e,p);
if(x&&x->data==e) return x;
else return NULL;
}
bool BinaryTree::Assign(char e,char value,BiTree& p){//将二叉树中节点e赋值为value
BiTree x=Search(e,p);
x->data=value;
return true;
}
BiTree BinaryTree::Parent(char e,BiTree& p){//返回节点e的双亲节点
if(!p) return NULL;
else if(p){
if(p->lchild&&p->lchild->data==e) return p; //要不要判断左孩子是否存在？
else if(p->rchild&&p->rchild->data==e) return p;
BiTree a=Parent(e,p->lchild);
BiTree b=Parent(e,p->rchild);
if(!a&&!b) return a;
else if(a) return a;
else return b;
}
//ERROR
}
BiTree BinaryTree::LeftChild(char e,BiTree& p){//返回节点e的左孩子
BiTree x=Search(e,p);
if(x&&x->lchild) return x->lchild; //若节点e存在且其左孩子也存在则返回其左孩子
else return NULL;
//ERROR
}
BiTree BinaryTree::RightChild(char e,BiTree& p){//返回节点e的右孩子
BiTree x=Search(e,p);
if(x->rchild) return x->rchild;//若节点e存在且其右孩子也存在则返回其右孩子
else return NULL;
//ERROR
}
BiTree BinaryTree::LeftSibling(char e,BiTree& p){//返回节点e的左兄弟
BiTree x=Parent(e,p);
BiTree y=Search(e,p);
if(x->lchild==y) return NULL; //若节点e为左孩子则无左兄弟
else return x->lchild;
}
BiTree BinaryTree::RightSibling(char e,BiTree& p){//返回节点e的右兄弟
BiTree x=Parent(e,p);
BiTree y=Search(e,p);
if(x->rchild==y) return NULL;//若节点e为右孩子则无右兄弟
else return x->rchild;
}
void BinaryTree::PreOrderTraverse(BiTree& p){//先序遍历二叉树
if(p){
Visit(p);
PreOrderTraverse(p->lchild);
PreOrderTraverse(p->rchild);
}
}
void BinaryTree::InOrderTraverse(BiTree& p){//中序遍历二叉树
if(p){
InOrderTraverse(p->lchild);
Visit(p);
InOrderTraverse(p->rchild);
}
}
void BinaryTree::PostOrderTraverse(BiTree& p){//后序遍历二叉树
if(p){
PostOrderTraverse(p->lchild);
PostOrderTraverse(p->rchild);
Visit(p);
}
}
void BinaryTree::LevelTraverse(BiTree& p){//层序遍历二叉树
queue<BiTree> Q;
Q.push(p);
while(!Q.empty()){
Visit(Q.front());
if(Q.front()->lchild)
Q.push(Q.front()->lchild);
if(Q.front()->rchild)
Q.push(Q.front()->rchild);
Q.pop();
}
}
void BinaryTree::Visit(BiTree& p){
cout<<p->data;
}
BiTree BinaryTree::Search(char e,BiTree& p){ //找到二叉树中值为e的节点(本函数较难做)
if(!p) return NULL;
else if(p){
if(p->data==e) return p;
BiTree a=Search(e,p->lchild);
BiTree b=Search(e,p->rchild);
if(!a&&!b) return a;//相当于return NULL
else if(a) return a;
else return b;
}
}
bool BinaryTree::Non_RecursionInOrderTraverse(BiTree& p){//用非递归算法中序遍历二叉树
stack<BiTree> S;
S.push(p);
while(!S.empty()){
while(S.top()) S.push(S.top()->lchild);
S.pop();
if(!S.empty()){
BiTree temp=S.top();
S.pop();
Visit(temp);
S.push(temp->rchild);
}
}
return true;
}
bool BinaryTree::Non_RecursionInOrderTraverse2(BiTree& p){//用非递归算法中序遍历二叉树
stack<BiTree> S;
BiTree q=p;//注意此处设置q是为了保存跟指针的位置不变,为后续操作提供可能
while(q||!S.empty()){
if(q){S.push(q);q=q->lchild;}
else{
q=S.top();
S.pop();
Visit(q);
q=q->rchild;
}
}
return true;
}
