分享
 
 
 

模板的练习---二叉树

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

以下是对二叉树的基本操作的实现,如创建无序二叉树,二叉排序树,三种递归遍历和非递归遍历,查找,插入,删除,以及树叶的计算和树的深度的计算等。

#include "iostream.h"

#include "stdlib.h"

#include "stack.h"

#pragma once

template<class T>

class CBiTree

{

public:

CBiTree(void)

{

}

~CBiTree(void)

{

}

static struct _tagBiTNode

{

T data;

struct _tagBiTNode* lchild;

struct _tagBiTNode* rchild;

};

private:

typedef _tagBiTNode BiTNode,*BiTree;

public:

bool CreateBiTree(BiTree& t);

bool PreOrderTraverse(BiTree t,void (*visit)(T data));

bool PreOrderTraverseEx(BiTree t,void (*visit)(T data));

bool InOrderTraverse(BiTree t,void (*visit)(T data));

bool InOrderTraverseEx(BiTree t,void (*visit)(T data));

bool PostOrderTraverse(BiTree t,void (*visit)(T data));

bool PostOrderTraverseEx(BiTree t,void (*visit)(T data));

void CountLeaf(BiTree t,int& count);

int BiTreeDepth(BiTree t);

//二叉排序树的操作

void CreateSortBiTree(BiTree &root,T* a,int n);

void InsertNode(BiTree &root,T e);

bool DeleteNode(BiTree &t,T& e);

bool SearchNode(BiTree t,T key,BiTree f,BiTree& p);

private:

void deleteNode(BiTree& p);

};

//创建一个无序二叉树

template<typename T>

bool CBiTree<T>::CreateBiTree(BiTree& t)

{

int n;

cin>>n;

if(n==0) t=NULL;

else

{

if(!(t = new BiTNode)) return false;

t->data = n;

CreateBiTree(t->lchild);

CreateBiTree(t->rchild);

}

return true;

}

//先根遍历 递归表示

template<typename T>

bool CBiTree<T>::PreOrderTraverse(BiTree t,void (*visit)(T data))

{

if(t!=NULL)

{

visit(t->data);

PreOrderTraverse(t->lchild,visit);

PreOrderTraverse(t->rchild,visit);

}

return false;

}

//先根遍历,栈表示

template<typename T>

bool CBiTree<T>::PreOrderTraverseEx(BiTree t,void (*visit)(T data))

{

try

{

CStack<BiTree>::_tagStack s; //栈

CStack<BiTree> stack ;

//if(stack == NULL)

// return false;

BiTree p = new BiTNode;

if(p == NULL)

return false;

stack.InitStack(s);

p = t;

while(p||!stack.StackEmpty(s))

{

if(p)

{

visit(p->data);

stack.Push(s,p);

p = p->lchild;

}

else

{

stack.Pop(s,p);

p = p->rchild;

}

}

stack.DestroyStack(s);

return true;

}

catch(...)

{

visit(-1);

return false;

}

}

//中序遍历,递归算法

template<typename T>

bool CBiTree<T>::InOrderTraverse(BiTree t,void (*visit)(T data))

{

if(t != NULL)

{

InOrderTraverse(t->lchild,visit);

visit(t->data);

InOrderTraverse(t->rchild,visit);

}

return true;

}

//中序遍历,栈表示

template<typename T>

bool CBiTree<T>::InOrderTraverseEx(BiTree t,void (*visit)(T data))

{

try

{

CStack<BiTree>::_tagStack s;

CStack<BiTree> stack;

BiTree p = new BiTNode;

p = t;

stack.InitStack(s);

while(p||!stack.StackEmpty(s))

{

if(p)

{

stack.Push(s,p);

p = p->lchild;

}

else

{

stack.Pop(s,p);

visit(p->data);

p = p->rchild;

}

}

stack.DestroyStack(s);

return true;

}

catch(...)

{

visit(-1);

return false;

}

}

//后序遍历,递归算法

template<class T>

bool CBiTree<T>::PostOrderTraverse(BiTree t,void (*visit)(T data))

{

if(t != NULL)

{

PreOrderTraverse(t->lchild,visit);

PreOrderTraverse(t->rchild,visit);

visit(t->data);

}

return true;

}

//后序遍历,栈表示

template<class T>

bool CBiTree<T>::PostOrderTraverseEx(BiTree t,void (*visit)(T data))

{

try

{

CStack<BiTree>::_tagStack s;

CStack<BiTree> stack;

BiTree p = new BiTNode;

p = t;

stack.InitStack(s);

while(p||!stack.StackEmpty(s))

{

if(p)

{

stack.Push(s,p->lchild);

p = p ->lchild;

}

else

{

visit(p->data);

stack.Pop(s,p);

p = p->rchild;

visit(p->data);

}

}

return true;

}

catch(...)

{

visit(-1);

return false;

}

}

//计数树叶的个数

template<class T>

void CBiTree<T>::CountLeaf(BiTree t,int& count)

{

if(t != NULL)

{

CountLeaf(t->lchild,count);

CountLeaf(t->rchild,count);

//检查结点t是否为叶子结点,若是,则定量count++

if(t->lchild == NULL &&t->rchild ==NULL)

count++;

}

}

//树的深度

template<class T>

int CBiTree<T>::BiTreeDepth(BiTree t)

{

int dep;

int depleft;

int deprigth ;

if( t==NULL)

dep = -1;

if( t != NULL )

{

depleft = BiTreeDepth(t->lchild);

deprigth = BiTreeDepth(t->rchild);

dep = 1 + ( depleft>deprigth? depleft:deprigth);

}

return dep;

}

//

template<class T>

bool CBiTree<T>::SearchNode(BiTree t,T key,BiTree f,BiTree& p)

{

if(t == NULL)

{

p = f;

return false;

}

else if(key == t->data)

{

p = t;

return true;

}

else if(key < t->data)

{

SearchNode(t->lchild,key,t,p);

}

else

SearchNode(t->rchild,key,t,p);

}

template<class T>

void CBiTree<T>::InsertNode(BiTree &root,T e)

{

BiTree t = root;

BiTree p = NULL;

BiTree newNode = new BiTNode;

while(t)

{

p = t;

if(e <=t->data)

t = t->lchild;

else

t = t->rchild;

}

newNode->data = e;

newNode->lchild = newNode->rchild =NULL;

if(p==NULL)

root = newNode;

else

if(e <p->data)

p->lchild = newNode;

else

p->rchild = newNode;

}

//找到要删除的结点,删除结点

template<class T>

void CBiTree<T>::deleteNode(BiTree& p)

{

BiTree q;

BiTree s;

if(!p->lchild)

{

q = p;

p = p->rchild;

free(q);

}

else if(!p->rchild)

{

q = p;

p = p->lchild;

free(q);

}

else

{

q = p;

s = p->lchild;

while(s->rchild)

{

q = s;

s = s->rchild;

}

p->data = s->data;

if(q!=p)

q->rchild = s->lchild;

else

q->lchild = s->lchild;

}

}

//查找要删除的结点,并删除

template<class T>

bool CBiTree<T>::DeleteNode(BiTree &t,T& e)

{

if(!t)

return false;

else

{

if(e == t->data)

deleteNode(t);

else if(e < t->data)

DeleteNode(t->lchild,e);

else

DeleteNode(t->rchild,e);

return true;

}

}

// n 为数据的总长度 用n = sizeof(a) / sizeof(a[0]);

template<class T>

void CBiTree<T>::CreateSortBiTree(BiTree &root,T* a,int n)

{

for(int i=0;i<n;i++)

{

InsertNode(root,a[i]);

}

}

/*

*************************************************************

test

*************************************************************

*/

void print(int data)

{

if(data == -1)

cout<<"\nError"<<endl;

cout<<data<<"\t";

}

int _tmain(int argc, _TCHAR* argv[])

{

cout<<"\nBiTree:-----------------------\n";

CBiTree<int>::_tagBiTNode *p1= NULL;

CBiTree<int>* tree = new CBiTree<int>;

cout<<"\n树的深度为:"<<tree->BiTreeDepth(t)<<endl;

int n=0;

int a[]={8,6,9,10,23,2,3,0,4,0,5};

tree->CreateSortBiTree(p1,a,sizeof(a)/sizeof(a[0]));

cout<<"\n前序遍历\n";

tree->PreOrderTraverse(p1,&print);

cout<<"\n";

tree->PreOrderTraverseEx(p1,&print);

cout<<"\n中序遍历\n"<<endl;

tree->InOrderTraverse(p1,&print);

cout<<"\n";

tree->InOrderTraverseEx(p1,&print);

tree->CountLeaf(p1,n);

cout<<"\n树的深度为:"<<tree->BiTreeDepth(p1)<<endl;

cout<<"叶子:"<<n<<endl;

cout<<"查找"<<endl;

int k0=3;

if(tree->SearchNode(p1,3,NULL,t))

{

cout<<"找到了"<<endl;

tree->DeleteNode(p1,k0);

tree->InOrderTraverse(p1,&print);

}

else

cout<<"没找到"<<endl;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有