文档介绍：1
2
3
11
4
5
8
9
12
13
6
7
10
14
15
1
2
3
11
4
5
8
9
12
6
7
10
1
2
3
4
5
6
7
1
2
3
4
5
6
第1页/共17页
链式存储结构
二叉链表
struct NodeType
{ ElemType data;
NodeType *lch, *rch;
};
lch data rch
A
B
C
D
E
F
G
A
B
C
D
E
F
G
^
^
^
^
^
^
^
^
第2页/共17页
-
+
/
a
*
b
-
e
f
c
d
先序遍历：
中序遍历：
后序遍历：
层次遍历：
-
+
a
*
b
-
c
d
/
e
f
-
+
a
*
b
-
c
d
/
e
f
-
+
a
*
b
-
c
d
/
e
f
-
+
a
*
b
-
c
d
/
e
f
第3页/共17页
二叉树的二叉链表类
class BiTree // 二叉树类
{public:
BiTree(){root=NULL;}
~BiTree(){destroy(root) ;}
void creat();
void preorder() //先序遍历
{ preorder(root); }
void inorder() //中序遍历
{ inorder(root); }
void postorder() //后序遍历
{ postorder(root); }
//删除二叉树所有结点
private:
NodeType *root;
preorder(NodeType *p);
//先序遍历
inorder(NodeType *p);
//中序遍历
postorder(NodeType *p);
//后序遍历
void destroy(NodeType *p);
//删除二叉树所有结点
//…….
}；
第4页/共17页
二叉树的建立
void BiTree::creat()
{ NodeType *q, *s[20]; ElemType x;int i,j;
root=NULL;
cout<<"\n i,x="; cin>>i>>x;
while(i!=0 && x!=0)
{ q=new NodeType; // 产生一个结点
q->data=x; q->lch=NULL; q->rch=NULL;
s[i]=q;
if (i==1) root=q; // q为树根root结点
else { j=i/2; // j为双亲结点编号
if ((i%2)==0) s[j]->lch=q; else s[j]->rch=q;
}
cout<<"\n i,x="; cin>>i>>x;
}//while end
} // creat end
第5页/共17页
二叉树的遍历
void BiTree::preorder(NodeType *p)