10 二叉树-链式存储-递归遍历

终于进入非线性数据结构的第一站了！

先从简单的开始回忆起来吧！

1、二叉树的链式存储

用一个链表来存储一颗二叉树，每一个结点用链表的一个链结点来存储。

通常地，一个二叉链表至少包含3个域：数据域data、左指针域lchild、右指针域rchild。

现实应用的过程中，可以按照自己的需求添加其他指针域。

1 typedef struct BitNode{
2 int data;
3 struct BitNode *lchild,*rchild;
4 }BitNode,*BiTree;

2、遍历

二叉树的遍历的定义：

按某个搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次。

递归式访问二叉树：

(1)、基本的三种：先序（中左右）、中序（左中右）、后序（左右中）。

(2)、三种遍历算法的递归遍历左子树、右子树的顺序都是固定的。只是访问根节点的顺序不同。

(3)、递归遍历中递归工作栈恰好为树的深度，在最坏的情况下，二叉树是有n个结点而且深度为n的单支树，此时遍历算法的空间复杂度为O(n)。

【注】这三种遍历方式的算法描述简单易懂，应能作为模板记忆。

3、具体代码实现

 1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<cstdio>
 4 using namespace std;
 5 #define TRUE 1
 6 #define FALSE 0
 7 #define OK 1
 8 #define ERROR 0
 9 #define OVERFLOW -2
10 typedef int Status;
11 typedef int ElemType;
12 
13 /*存储结构描述*/
14 typedef struct BitNode{
15 int data;
16 struct BitNode *lchild,*rchild;
17 }BitNode,*BiTree;
18 /*建立树*/
19 void initTree(BiTree &T)
20 {
21     int x;
22     cin>>x;
23     if(x==0)
24     {
25         T=NULL;
26     }
27     else {//按照先序遍历建树
28         T=(BitNode*)malloc(sizeof(BitNode));
29         T->data=x;
30         initTree(T->lchild);
31         initTree(T->rchild);
32     }
33 }
34 
35 void visit(BiTree T)
36 {
37     cout<<T->data<<' ';
38 }
39 /*递归方式访问树*/
40 /*先序遍历*/
41 void preOrder(BiTree T)
42 {
43     if(T!=NULL){
44         visit(T);
45         preOrder(T->lchild);
46         preOrder(T->rchild);
47     }
48 }
49 void inOrder(BiTree T)
50 {
51     if(T!=NULL)
52     {
53         inOrder(T->lchild);
54         visit(T);
55         inOrder(T->rchild);
56     }
57 }
58 void postOrder(BiTree T)
59 {
60     if(T!=NULL)
61     {
62         postOrder(T->lchild);
63         postOrder(T->rchild);
64         visit(T);
65     }
66 }
67 int main()
68 {
69     BiTree tree;
70     cout<<"Create tree in preOrder.:"<<endl;
71     initTree(tree);
72     cout<<"--- show the preorder sequence: ---"<<endl;
73     preOrder(tree);
74     cout<<endl;
75     cout<<"--- show the inorder sequence: ---"<<endl;
76     inOrder(tree);
77     cout<<endl;
78     cout<<"--- show the postorder sequence: ---"<<endl;
79     postOrder(tree);
80     return 0;
81 }

4、实现截图