二叉树的建立以及遍历

利用递归的方式建立二叉树并以中序遍历的方式读取数据，根据遍历二叉树的三种方式，只需要在递归时修改访问结点的元素即可。

  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
	typedef struct Binode{
	    char data;
	    struct Binode *Rchild ,*Lchild;
	}BiTnode,*BiTree;

	void createBTree( BiTree *T)
	{
	    char c ;
	    scanf("%c",&c);
	    if(' '==c){
	        *T=NULL;
	    }
	    else{
	        *T=(BiTnode*)malloc(sizeof(BiTnode));
	        (*T)->data=c;
	        createBTree(&(*T)->Lchild);
	        createBTree(&(*T)->Rchild);
	    }
	}
	void visit(char c ,int level){
	    printf("%c   %d\n",c,level);
	}
	 void preOrderTraverse(BiTree T, int level)
	{
	    if(T)
	    {
	        preOrderTraverse(T->Lchild,level+1);
	        visit(T->data,level);
	        preOrderTraverse(T->Rchild,level+1);
	    }
	}
	int main()
	{
	    BiTree t ;
	    t=NULL;
	    printf("创建二叉树，以空格代表子结点为空:\n");
	    createBTree(&t);
	    preOrderTraverse(t,1);
	    return 0;
	}

注意：在此建立二叉树使用的是指针的指针，如果用的时是指针的话，作为形参传递给函数，当函数返回后，函数出栈，也就不能获得结点信息，而使用二重指针头节点本身为指针，在函数递归的过程中需要修改本身的值，就需要使用二重指针，这类似于利用函数交换值得思想。