SEMAN
曾经沧海难为水、除却巫山不是云
C++博客
首页
新随笔
联系
聚合
管理
9 Posts :: 3 Stories :: 24 Comments :: 0 Trackbacks
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔分类
COM/COM+
MFC
Other(3)
STL(2)
随笔档案
2005年11月 (7)
2005年10月 (2)
文章分类
C/C++ BASIC(2)
Code(1)
文章档案
2005年11月 (3)
收藏夹
Cpp资料
C/C++
k_eckel
MasterLee
STL.Boost
搜索
最新评论
1. re: Good C++ Interview Questions
what's the answer?
--Mingyu
2. re: 嵌入式开发.C语言面试题[未登录]
评论内容较长,点击标题查看
--初学者
3. re: 嵌入式开发.C语言面试题
哈哈,很棒~
--btw616
4. re: GCC 参数详解
哈哈。。。 .pig 。。。。哈哈
--btw616
5. re: 嵌入式开发.C语言面试题
写的真是不错,可惜的是我等级太低,还未能追上你的思想,你就飘走了!!!
--jince
阅读排行榜
1. GCC 参数详解(75148)
2. 嵌入式开发.C语言面试题(9762)
3. 比饶口令还饶口的复杂声明(2334)
4. My Onepage English Resume(1647)
5. Window+GCC+CDT用Eclipse开发C、C++(1482)
评论排行榜
1. 比饶口令还饶口的复杂声明(9)
2. MS的笔试题目(5)
3. 嵌入式开发.C语言面试题(3)
4. GCC 参数详解(3)
5. 二叉树的模板实现(1)
二叉树的模板实现
#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;
}
posted on 2005-10-24 11:06
味全每日C++
阅读(1445)
评论(1)
编辑
收藏
引用
所属分类:
STL
Feedback
#
re: 二叉树的模板实现
2007-06-13 23:58
hello
有没有stack.h的头文件亚?
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
比饶口令还饶口的复杂声明
二叉树的模板实现
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 味全每日C++