#include "Common.h"
#include "DCirList.h"
#pragma once
#pragma region
//二叉树类
//测试日期 2010-3-13
#ifndef BINTREENODE_H
#define BINTREENODE_H
template<class T>
class BinTreeNode
{
public:
BinTreeNode<T>* leftchild;
BinTreeNode<T>* rightchild;
T data;
BinTreeNode(){leftchild=rightchild=NULL;} //默认构造函数
BinTreeNode(T item,BinTreeNode<T>* pl=NULL,BinTreeNode<T>* pr=NULL) //重载构造函数
{data=item;leftchild=pl;rightchild=pr;}
};
#endif
#ifndef BINTREE_H
#define BINTREE_H
template<class T>
void _visit(BinTreeNode<T>* x){}
template<class T>
class BinTree
{
protected:
BinTreeNode<T>* root; //二叉树根结点指针
BinTreeNode<T>* current; //二叉树当前结点指针
DCirList<BinTreeNode<T>*> L; //遍历链表
//[3个函数]
BinTreeNode<T>* Copy(BinTreeNode<T>* t); //复制二叉树
BinTreeNode<T>* CreateBinTree(T *VLR,T *LVR,int n); //由VLR,LVR序列创建二叉树
BinTreeNode<T>* SearchParent(BinTreeNode<T>* t,BinTreeNode<T>* s); //在二叉树t中回溯查找s的父结点
public:
BinTree(){root=current=NULL;} //构造函数
~BinTree(){ClearTree();} //析构函数
void ClearList(){L.ClearList();} //清空遍历表
//[4个函数]
BinTree<T>& CreateBinTree(DCirList<T> vlr, DCirList<T> lvr); //由VLR,LVR序列创建二叉树
void ClearTree(){DeleteSubTree(root);} //清空二叉树
int TreeSize(BinTreeNode<T>* t); //返回以t为根结点的二叉树的结点个数
int TreeSize(){return TreeSize(root);} //二叉树的结点数
//获取结点指针[6个函数]
BinTreeNode<T>* GetRoot(){return root;} //返回根结点指针
BinTreeNode<T>* GetCurrent(){return current;} //返回当前结点指针
BinTreeNode<T>* GetParent(){return SearchParent(root,current);} //返回当前结点的父结点指针
BinTreeNode<T>* GetLeftChild(); //返回当前结点的左孩子结点指针
BinTreeNode<T>* GetRightChild(); //返回当前结点的右孩子结点指针
BinTreeNode<T>* GetSibling(); //返回当前结点的兄弟结点指针
//四种遍历[8个函数]
void PreOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x)); //前序遍历以t为根结点的数据域
DCirList<BinTreeNode<T>*> GetPreList(BinTreeNode<T>* t);
void InOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x)); //中序遍历以t为根结点的数据域
DCirList<BinTreeNode<T>*> GetInList(BinTreeNode<T>* t);
void PosOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x)); //后序遍历以t为根结点的数据域
DCirList<BinTreeNode<T>*> GetPosList(BinTreeNode<T>* t);
void LevelOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x)); //层序遍历以t为根结点的数据域
DCirList<BinTreeNode<T>*> GetLevelList(BinTreeNode<T>* t);
//设置当前结点并返回当前结点指针[7个函数]
BinTreeNode<T>* SetRoot(){return current=root;} //把根结点设置为当前结点
BinTreeNode<T>* SetCurrent(BinTreeNode<T>* t){return current=t;} //把t所指向的结点设置为当前结点
BinTreeNode<T>* SetCurrent(char* p); //设置当前节点,如p='lrlrlr';l代表左,r代表右
BinTreeNode<T>* SetParent(){return current=GetParent();} //把当前结点的父结点设置为当前结点
BinTreeNode<T>* SetLeftChild(){return current=GetLeftChild();} //把当前结点的左孩子结点设置为当前结点
BinTreeNode<T>* SetRightChild(){return current=GetRightChild();} //把当前结点的右孩子结点设置为当前结点
BinTreeNode<T>* SetSibling(){return current=GetSibling();} //把当前结点的兄弟结点设置为当前结点
//插入删除操作[7个函数]
void InsertLeftChild(T x); //把x插入为当前结点的左孩子结点
void InsertRightChild(T x); //把x插入为当前结点的右孩子结点
void InsertLeftTree(BinTree<T> &tree); //把tree插入为当前结点的左孩子树[原孩子树被替换]
void InsertRightTree(BinTree<T> &tree); //把tree插入为当前结点的右孩子树[原孩子树被替换]
void DeleteLeftChild(); //删除当前结点的左孩子结点
void DeleteRightChild(); //删除当前结点的右孩子结点
void DeleteSubTree(BinTreeNode<T>* &t); //删除以t为根结点的子树
//其他4个函数
bool IsLeaf(); //判断当前结点是否为叶子结点
int Depth(BinTreeNode<T>* t); //返回以t为根结点的二叉树的深度
int LeafCount(BinTreeNode<T>* t); //返回以t为根节点的二叉树的叶子的个数
BinTree<T>& operator=(BinTree<T>& t);
};
#endif
template<class T>
BinTreeNode<T>* BinTree<T>::Copy(BinTreeNode<T> *t)
{
if(t==NULL)
return NULL;
BinTreeNode<T>* p=new BinTreeNode<T>;
p->data=t->data;
if(t->leftchild!=NULL)
p->leftchild=Copy(t->leftchild);
if(t->rightchild!=NULL)
p->rightchild=Copy(t->rightchild);
return p;
}
template<class T>
BinTreeNode<T>* BinTree<T>::CreateBinTree(T *VLR, T *LVR, int n)
{
if(n==0)
return NULL;
int k=0;
while(k<n&&VLR[0]!=LVR[k])
k++;
BinTreeNode<T> *t=new BinTreeNode<T>(VLR[0]);
t->leftchild=CreateBinTree(VLR+1,LVR,k);
t->rightchild=CreateBinTree(VLR+k+1,LVR+k+1,n-k-1);
return t;
}
template<class T>
BinTreeNode<T>* BinTree<T>::SearchParent(BinTreeNode<T> *t, BinTreeNode<T> *s)
{
if(t==NULL||s==NULL||s==root)
return NULL;
if(t->leftchild==s||t->rightchild==s)
return t;
BinTreeNode<T> *p;
if((p=SearchParent(t->leftchild,s))!=NULL)
return p;
if((p=SearchParent(t->rightchild,s))!=NULL)
return p;
}
template<class T>
BinTree<T>& BinTree<T>::CreateBinTree(DCirList<T> vlr, DCirList<T> lvr)
{
int n=vlr.Size();
if(n!=lvr.Size()){root=NULL;return *this;}
T* VLR=new T[n];
T* LVR=new T[n];
for(int i=0;i<n;i++)
{
VLR[i]=vlr.GetData(i);
LVR[i]=lvr.GetData(i);
}
current=root=CreateBinTree(VLR,LVR,n);
delete VLR;
delete LVR;
return *this;
}
template<class T>
int BinTree<T>::TreeSize(BinTreeNode<T>* t)
{
if(t==NULL)
return 0;
else
return 1+TreeSize(t->leftchild)+TreeSize(t->rightchild);
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetLeftChild()
{
return current==NULL?NULL:current->leftchild;
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetRightChild()
{
return current==NULL?NULL:current->rightchild;
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetSibling()
{
if(current=root||current==NULL)
return NULL;
BinTreeNode<T> *p;
p=GetParent();
if(p1->leftchild==current)
return p->rightchild;
else
return p->leftchild;
}
template<class T>
void BinTree<T>::PreOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
if(t==NULL)
return;
visit(t); L.PushBack(t);
if(t->leftchild!=NULL)
PreOrderTree(t->leftchild,visit);
if(t->rightchild!=NULL)
PreOrderTree(t->rightchild,visit);
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetPreList(BinTreeNode<T> *t)
{
ClearList();
PreOrderTree(t,_visit);
return L;
}
template<class T>
void BinTree<T>::InOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
if(t==NULL)
return;
if(t->leftchild!=NULL)
InOrderTree(t->leftchild,visit);
visit(t); L.PushBack(t);
if(t->rightchild!=NULL)
InOrderTree(t->rightchild,visit);
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetInList(BinTreeNode<T> *t)
{
ClearList();
InOrderTree(t,_visit);
return L;
}
template<class T>
void BinTree<T>::PosOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
if(t==NULL)
return;
if(t->leftchild!=NULL)
PosOrderTree(t->leftchild,visit);
if(t->rightchild!=NULL)
PosOrderTree(t->rightchild,visit);
visit(t); L.PushBack(t);
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetPosList(BinTreeNode<T> *t)
{
ClearList();
PosOrderTree(t,_visit);
return L;
}
template<class T>
void BinTree<T>::LevelOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
if(t==NULL)
return;
DCirList<BinTreeNode<T>* >q;
BinTreeNode<T> *p;
q.PushBack(t);
while(!q.IsEmpty())
{
p=q.PopFront();
visit(p); L.PushBack(p);
if(p->leftchild!=NULL) q.EnterQueue(p->leftchild);
if(p->rightchild!=NULL) q.EnterQueue(p->rightchild);
}
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetLevelList(BinTreeNode<T> *t)
{
ClearList();
LevelOrderTree(t,_visit);
return L;
}
template<class T>
BinTreeNode<T>* BinTree<T>::SetCurrent(char *p)
{
current=root;
int n=strlen(p);
for(int i=0;i<n;i++)
{
if(p[i]=='l')
SetLeftChild();
if(p[i]=='r')
SetRightChild();
}
return current;
}
template<class T>
void BinTree<T>::InsertLeftChild(T x)
{
BinTreeNode<T> *newnode=new BinTreeNode<T>(x);
if(root==NULL){root=current=newnode;return;}
if(current==NULL)return;
newnode->leftchild=current->leftchild;
current->leftchild=newnode;
}
template<class T>
void BinTree<T>::InsertRightChild(T x)
{
BinTreeNode<T> *newnode=new BinTreeNode<T>(x);
if(root==NULL){root=current=newnode;return;}
if(current==NULL)return;
newnode->rightchild=current->rightchild;
current->rightchild=newnode;
}
template<class T>
void BinTree<T>::InsertLeftTree(BinTree<T> &tree)
{
BinTreeNode<T>* p=Copy(tree.root);
DeleteLeftChild();
current->leftchild=p;
}
template<class T>
void BinTree<T>::InsertRightTree(BinTree<T> &tree)
{
BinTreeNode<T>* p=Copy(tree.root);
DeleteRightChild();
current->rightchild=p;
}
template<class T>
void BinTree<T>::DeleteLeftChild()
{
DeleteSubTree(current->leftchild);
}
template<class T>
void BinTree<T>::DeleteRightChild()
{
DeleteSubTree(current->rightchild);
}
template<class T>
void BinTree<T>::DeleteSubTree(BinTreeNode<T> *&t)
{
if(t==NULL) return;
if(t->leftchild!=NULL)
DeleteSubTree(t->leftchild);
if(t->rightchild!=NULL)
DeleteSubTree(t->rightchild);
BinTreeNode<T> *p=SearchParent(root,t);
if(p!=NULL)
{
if(p->leftchild==t)
p->leftchild=NULL;
if(p->rightchild==t)
p->rightchild=NULL;
}
delete t;
t=NULL;
}
template<class T>
bool BinTree<T>::IsLeaf()
{
if(current==NULL)
return false;
return (current->leftchild==NULL&¤t->rightchild==NULL);
}
template<class T>
int BinTree<T>::Depth(BinTreeNode<T>* t)
{
if(t==NULL)
return 0;
int ldep=Depth(t->leftchild);
int rdep=Depth(t->rightchild);
return ldep>rdep?ldep+1:rdep+1;
}
template<class T>
int BinTree<T>::LeafCount(BinTreeNode<T>* t)
{
int count=0;
if(t!=NULL)
{
count+=CountLeaf(t->leftchild);
count+=CountLeaf(t->rightchild);
if(t->leftchild==NULL&&t->rightchild==NULL)
count++;
}
return count;
}
template<class T>
BinTree<T>& BinTree<T>::operator =(BinTree<T> &t)
{
current=root=Copy(t.root);
return *this;
}
分享到:
相关推荐
数据结构--二叉树--思维导图.pdf
任意给出一棵二叉树,试设计一个程序,在计算机中构造该二叉树,并对它进行先序、 中序、后序遍历。
数据结构课设--哈夫曼二叉树.doc
用于数据结构二叉树学习,体会递归思想的妙用。
这份资料里面讲解的很清楚详细,易懂,对正在学习编程的同学特别是对正在找工作的同学非常有帮助。
数据结构-二叉树.doc
数据结构课程设计--二叉树的遍历.docx
数据结构-二叉树的实现.docx
数据结构-二叉树的建立与遍历.doc
数据结构C语言版-二叉树的三叉链表存储表示.doc
栈(Stack):具有后进先出(LIFO)特性的数据结构,只允许在栈顶进行插入和删除操作。可以使用数组或链表实现。 队列(Queue):具有先进先出(FIFO)特性的数据结构,允许在队尾插入元素,在队头删除元素。可以...
数据结构实验三-二叉树的实现2017.doc
线索二叉树 数据结构学习笔记——线索二叉树
数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx
数据结构课程设计报告-二叉树.doc
数据结构-平衡二叉树的操作演示.docx
数据结构C语言版-平衡二叉树.doc
这是一份我上课的课件,有详细的二叉树教学,对学习数据结构的人帮助很大
二叉树的创建 二叉树的层次遍历 二叉树的非递归遍历 线索二叉树的实现 ...内容学习于 https://www.bilibili.com/video/BV1W64y1z7jh?p=19&spm_id_from=pageDriver&vd_source=4d33bf4ac4499f2c0370694554a02fa5
数据结构二叉树学习,从认知到遍历进本包含了数据结构的所有东西,大一学习数据结构时讲二叉树,看这个基本上是OK的了。