二叉树的存储及遍历

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int Max_N;
 4 
 5 //1.树的节点定义 
 6 struct node{
 7     char val;//结点值 
 8     int lch, rch;//左右儿子(指向结构体数组下标) 
 9 }; 
10 
11 //2.定义树，用结构体数组存储 
12 node tree[Max_N];
13 int id;//数组下标标记 
14 
15 //3.构建树
16 void build(int root)
17 {
18     char c;
19     cin>>c;
20     tree[root].val=c;
21     
22     tree[root].lch=++id;
23     build(tree[root].lch);//或者build(id); 递归进入左子树 
24     tree[root].rch=++id;
25     build(tree[root].rch);//或者build(id); 递归进入右子树 
26  } 
27  
28  //4.遍历
29  void xxbl(int root)//4.1 先序遍历
30 {
31     cout<<tree[root].val;//对根进行操作 
32     
33     if(tree[root].lch)//左子树非空时，递归进入左子树 
34         xxbl(tree[root].lch);
35         
36     if(tree[root].rch)//右子树非空时，递归进入右子树 
37         xxbl(tree[root].rch);
38 } 
39 void zxbl(int root)//4.2 中序遍历
40 { 
41     if(tree[root].lch)//左子树非空时，递归进入左子树 
42         zxbl(tree[root].lch);
43         
44     cout<<tree[root].val;//对根进行操作
45     
46     if(tree[root].rch)//右子树非空时，递归进入右子树 
47         zxbl(tree[root].rch);
48 } 
49 void hxbl(int root)//4.3 后序遍历
50 { 
51     if(tree[root].lch)//左子树非空时，递归进入左子树 
52         hxbl(tree[root].lch);
53 
54     if(tree[root].rch)//右子树非空时，递归进入右子树 
55         hxbl(tree[root].rch);
56         
57     cout<<tree[root].val;//对根进行操作
58 } 
59 int main()
60 {
61     build(1);//树根结点从1开始 
62     xxbl(1);
63     zxbl(1);
64     hxbl(1);
65      
66     return 0;
67  }