[C语言]二叉树的二叉链表存储表示

参考严蔚敏/吴伟民版《数据结构-C语言版》

1. 顺序存储表示的话其实就是数组表示，只有完全二叉树能充分利用到存储空间

2. 链式存储结构

// 二叉树节点的表示
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild , *rchild; //左右孩子指针
｝BiTNode, *BiTree;

3. 先序遍历二叉树算法

// 根->左->右
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e){
	// Visit是对数据元素操作的应用函数
	if(T){
		if(Visit(T->data)){
			if(PreOrderTraverse(T->lchild, Visit)){
				if(PreOrderTraverse(T-rchild, Visit))
					return OK;
				}
				return ERROR;
			}
		}else{
			return OK;
		}
}

4. 中序遍历

Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)){
	// 非递归
	InitStack(S);Push(S, T); //根指针进栈
	while(!StackEmpty(S)){
		while(GetTop(S,p) && p) Push(S, p->lchild);
		Pop(S,p);
		if(!StackEmpty(S)){
			Pop(S, p);
			if(!Visit(p->data)) return ERROR;
			Push(S, p->rchild);
		}
	}
	return OK;
}

5. 按先序遍历构建二叉树

Status CreateBiTree(BiTree &T){
	scanf(&ch);
	if(ch==' ‘） T=NULL;
	else{
		if(!(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit(OVERFLOW);
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}