#pragma once
#include<iostream>
#include<queue>
#include<stack>
#include<assert.h>
using namespace std;
enum PointerTag{THREAD,LINK}; //二叉树线索化需要的
struct BinaryTreeNode
{
BinaryTreeNode(int data)
:_data(data)
,_left(NULL)
,_right(NULL)
,_parent(NULL)
,_leftTag(LINK)
,_rightTag(LINK)
{}
BinaryTreeNode* _left;
BinaryTreeNode* _right;
BinaryTreeNode* _parent;
PointerTag _leftTag; //线索化需要
PointerTag _rightTag; //线索化
int _data;
};
class BinaryTree
{
public:
typedef BinaryTreeNode Node;
BinaryTree()
:_root(NULL)
{}
BinaryTree(int* a,int len) //创建树
{
int index=0;
_root=_create(a,index,len);
}
BinaryTree(BinaryTree& t)//拷贝构造
{
_root=_copy(t._root);
}
//BinaryTree& operator=(BinaryTree& t) //赋值
//{
// if( this!= &t)
// {
// _delete(_root);
// _copy(t._root);
// }
// return *this;
//}
BinaryTree& operator=(BinaryTree t)
{
swap(_root,t._root);
return *this;
}
//~BinaryTree()
//{
// _delete(_root);
// _root=NULL;
//}
void Mirror()
{
_Mirror(_root);
}
void PreOrder() //前序遍历
{
_PreOrder(_root);
}
void InOrder() //中序遍历
{
_InOrder(_root);
}
void PostOrder() //后序遍历
{
_PostOrder(_root);
}
void PreOrder_NoR() //非递归前序遍历
{
if(_root==NULL)
{
return ;
}
Node* cur=_root;
stack<Node*> s;
s.push(cur);
while(!s.empty())
{
Node* root=s.top();
cout<<root->_data<<"->";
s.pop();
if(root->_right)
s.push(root->_right);
if(root->_left)
s.push(root->_left);
}
}
void InOrder_NoR()
{
if(_root==NULL)
{
return ;
}
Node* cur=_root;
stack<Node*> s;
while( cur||!s.empty())
{
while(cur) //一直压左节点
{
s.push(cur);
cur=cur->_left;
}
//取栈顶元素
//把右节点当做一个树，继续压入左节点
if(!s.empty())
{
Node * root=s.top();
cout<<root->_data<<"->";
s.pop();
cur=root->_right;
}
}
}
void PostOrder_NonR()
{
stack<Node*> s1;
Node* cur=_root;
Node* prev=NULL;
while(cur || !s1.empty())
{
while(cur)
{
s1.push(cur);
cur=cur->_left;
}
Node* root=s1.top();
if(root->_right==NULL || root->_right==prev) //右节点为空 或者已经访问过了
{
cout<<root->_data<<"->";
s1.pop();
prev=root;
}
else
{
cur=root->_right;
}
}
}
bool ExistBtree(BinaryTree t1)
{
return _Exist(_root,t1._root);
}
void LevelOrder() //非递归 利用队列 层次遍历
{
queue<Node*> q1;
q1.push(_root);
while(!q1.empty())
{
Node* root=q1.front();
cout<<root->_data<<"->";
q1.pop();
if(root->_left)
q1.push(root->_left);
if(root->_right)
q1.push(root->_right);
}
}
int Size() //总结点
{
int size=0;
_size(_root,size);
return size;
}
int Height() //求高度
{
return _height(_root);
}
int LeafNum() //叶子节点
{
return _leafnum(_root);
}
void PrevOrderThreading() //前序线索化
{
Node* prev=NULL;
_prevorderthreading(_root,prev);
}
void PreOrderThd() //前序线索化遍历
{
if(_root==NULL)
{
return;
}
Node* cur=_root;
while(cur)
{
cout<<cur->_data<<"->";
if(cur->_leftTag==LINK)
{
cur=cur->_left;
}
else
{
cur=cur->_right;
}
}
}
void InOrderThreading() //中序化线索
{
Node* prev=NULL;
_InOrderThreading(_root,prev);
}
void InOrderThd()
{
Node* cur=_root;
while(cur)
{
while(cur->_leftTag==LINK)
{
cur=cur->_left;
}
if(cur&&cur->_rightTag!=LINK)
{
cout<<cur->_data<<"->";
cur=cur->_right;
}
cout<<cur->_data<<"->";
cur=cur->_right;
}
}
private:
bool _Exist(BinaryTreeNode* root1,BinaryTreeNode* root2)
{
if(root2==NULL)
{
return true;
}
if(root1==NULL)
{
return false;
}
if(root1->_data==root2->_data)
{
return _Exist(root1->_left,root2->_left)&&_Exist(root1->_right,root2->_right);
}
if(root1->_data!=root2->_data)
{
if( _Exist(root1->_left,root2)==false)
{
return _Exist(root1->_right,root2);
}
return true;
}
}
void _InOrderThreading(Node* root,Node*& prev)
{
if(root==NULL)
{
return;
}
prev=root;
_InOrderThreading(root->_left,prev);
if(root->_left==NULL)
{
root->_leftTag=THREAD;
root->_left=prev;
}
if(prev&&prev->_right==NULL&&prev!=root)
{
prev->_rightTag=THREAD;
prev->_right=root;
}
_InOrderThreading(root->_right,prev);
}
void _prevorderthreading(Node* root,Node* &prev)
{
if(root==NULL)
{
return ;
}
if(root&&root->_left==NULL)
{
root->_leftTag=THREAD;
}
if(prev&&prev->_right==NULL)
{
prev->_right=root;
prev->_rightTag=THREAD;
}
prev=root;
if(root->_leftTag==LINK)
{
_prevorderthreading(root->_left,prev);
}
if(root->_rightTag==LINK)
{
_prevorderthreading(root->_right,prev);
}
}
int _leafnum(Node* root)
{
if(root==NULL)
{
return 0;
}
if(root->_left==NULL && root ->_right==NULL)
{
return 1;
}
return _leafnum(root->_left)+_leafnum(root->_right);
}
int _height(Node* root)
{
if(root==NULL)
{
return 0;
}
int left_height=_height(root->_left);
int right_height=_height(root->_right);
return left_height>right_height ?left_height+1 :right_height+1;
}
void _size(Node* root,int& size)
{
if(root==NULL)
{
return;
}
++size;
_size(root->_left,size);
_size(root->_right,size);
}
void _delete(Node* root)
{
if(root==NULL)
{
return;
}
_delete(root->_left);
_delete(root->_right);
root->_parent=NULL;
delete root;
}
Node* _copy(Node* root)
{
if(root==NULL)
{
return NULL;
}
Node* newRoot=NULL;
newRoot=new Node(root->_data);
newRoot->_left=_copy(root->_left);
if(newRoot->_left!=NULL)
{
newRoot->_left->_parent=newRoot;
}
newRoot->_right=_copy(root->_right);
if(newRoot->_right!=NULL)
{
newRoot->_right->_parent=newRoot;
}
return newRoot;
}
Node* _create(int* a,int& index,int len)
{
assert(a);
Node* root=NULL;
if(a[index]!='#' && index<len)
{
root=new Node(a[index]);
root->_left=_create(a,++index,len);
if(root->_left!=NULL)
{
root->_left->_parent=root;
}
root->_right=_create(a,++index,len);
if(root->_right!=NULL)
{
root->_right->_parent=root;
}
}
return root;
}
void _PreOrder(Node* root)
{
if(root==NULL)
{
return;
}
cout<<root->_data<<" ->";
_PreOrder(root->_left);
_PreOrder(root->_right);
}
void _InOrder(Node* root)
{
if(root==NULL)
{
return;
}
_InOrder(root->_left);
cout<<root->_data<<" ->";
_InOrder(root->_right);
}
void _PostOrder(Node* root)
{
if(root==NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<<root->_data<<" ->";
}
void _Mirror(Node* root) //二叉树的镜像
{
if(root==NULL)
{
return;
}
if(root->_right || root->_left)
{
Node* tmp=root->_left;
root->_left=root->_right;
root->_right=tmp;
}
if(root->_left)
_Mirror(root->_left);
if(root->_right)
_Mirror(root->_right);
}
private:
Node* _root;
};
BinaryTreeNode* Construct(int* prev,int* mid,int& index,int begin,int end) //根据前序遍历和中序遍历重建树
{
assert(prev);
assert(mid);
int final=0;
for(int i=begin;i<=end;i++)
{
if(mid[i]==prev[index])
{
final=i;
break;
}
}
BinaryTreeNode* root=new BinaryTreeNode(prev[index]);
if(final-1>=0 && begin <= (final-1))
root->_left=Construct(prev,mid,++index,begin,final-1);
if(final+1<=end)
root->_right=Construct(prev,mid,++index, final+1,end);
return root;
}
void Pre(BinaryTreeNode* root)
{
if(root==NULL)
{
return;
}
cout<<root->_data<<"->";
Pre(root->_left);
Pre(root->_right);
}
#include"BinaryTree.h"void test1(){ int a[]={1, 2, 3, '#', '#', 4, '#', '#', 5, 6}; int a1[]={6,2,'#',4,'#','#',}; BinaryTree t1(a,10); BinaryTree t2(a1,4); //cout<<t1.ExistBtree(t2); //int prev[]={1,2,4,7,3,5,6,8}; //int mid[]={4,7,2,1,5,3,8,6}; //int index=0; //BinaryTreeNode* root=Construct(prev,mid,index,0,7); //Pre(root); //t1.Mirror(); //t1.PreOrder(); //t1.PreOrder(); //t1.PreOrder_NoR(); //t1.InOrder(); //t1.InOrderThreading(); //t1.InOrderThd(); //t1.InOrder_NoR(); //t1.PostOrder(); //t1.PostOrder_NonR(); //t1.PrevOrderThreading(); //t1.PreOrderThd(); //t1.LevelOrder(); //cout<<t1.Size(); /*cout<<t1.Height(); cout<<t1.LeafNum();*/}int main(){ test1(); system("pause"); return 0;}
