二叉树——辅助队列实现层次遍历（递归）

二叉树——辅助队列实现层次遍历（递归）

目录

一、二叉树的特点二、如何将元素放入二叉树中三、代码实现

结构体1.前序遍历2.中序遍历3.后序遍历完整代码

一、二叉树的特点

二、如何将元素放入二叉树中

在往树添加元素的过程中，树根添加后，按从左往右的顺序，每个元素只有两个孩子，即左孩子和右孩子。只要左孩子为空，就放入左孩子中，满了才能放右孩子里。
在这里我们使用辅助队列来实现这一 *** 作，辅助队列里有三个主要元素，队列的每个元素的结构都是树的结构，即它也有左右孩子。每次读取元素从队列尾端插入。队列中有三个指针，head，tail，cur，其中顾名思义，头尾指针始终指向辅助队列的头尾，而cur动态指针会根据往树种插入位置的变化发生改变而移动，当树的该结点的左右孩子都满了，cur指针指向下一个。

三、代码实现 结构体

树

// 定义结构体
typedef char BiElemType;
typedef struct BiNode {
	BiElemType data; // 存放数据
	struct BiNode* lchild; // 左孩子
	struct BiNode* rchild; // 右孩子
}BiNode,*BiTree;

辅助队列

typedef struct tag_t {
	BiTree p; // 树结构的data域
	struct tag_t* pnext; // 指针域
}tag_t,*ptag_t;

1.前序遍历

// 递归实现前序遍历(中左右)
void preOrder(BiTree p) {
	if (p != NULL) {
		putchar(p->data);
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}

2.中序遍历

// 递归实现中序遍历(左中右)
void inOrder(BiTree p) {
	if (p != NULL) {
		inOrder(p->lchild);
		putchar(p->data);
		inOrder(p->rchild);
	}
}

3.后序遍历

// 递归实现后序遍历(左右中)
void postOrder(BiTree p) {
	if (p != NULL) {
		postOrder(p->lchild);
		postOrder(p->rchild);
		putchar(p->data);
	}
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include
#include

// 定义结构体
typedef char BiElemType;
typedef struct BiNode {
	BiElemType data; // 存放数据
	struct BiNode* lchild; // 左孩子
	struct BiNode* rchild; // 右孩子
}BiNode,*BiTree;

typedef struct tag {
	BiTree p; // data域
	struct tag* pnext; // 指针域
}tag_t,*ptag_t;

// 递归实现前序遍历(中左右)
void preOrder(BiTree p) {
	if (p != NULL) {
		putchar(p->data);
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}

// 递归实现中序遍历(左中右)
void inOrder(BiTree p) {
	if (p != NULL) {
		inOrder(p->lchild);
		putchar(p->data);
		inOrder(p->rchild);
	}
}

// 递归实现后序遍历(左右中)
void postOrder(BiTree p) {
	if (p != NULL) {
		postOrder(p->lchild);
		postOrder(p->rchild);
		putchar(p->data);
	}
}

int main()
{
	BiTree pnew; // 定义新结点
	BiTree tree = NULL; // 树根
	ptag_t phead = NULL, ptail = NULL, listpnew, pcur=NULL;
	char c;
	while (scanf("%c", &c) != EOF) {
		if (c == 'n') {
			break;
		}
		// 给新节点申请空间
		pnew = (BiTree)calloc(1, sizeof(BiNode));
		pnew->data = c;// 将读取的值赋给pnew中的data域
		// 辅助队列帮助层次遍历
		listpnew = (ptag_t)calloc(1, sizeof(tag_t));
		listpnew->p=pnew;
		if (NULL == tree) {
			// 当一开始tree中没有结点时
			tree = pnew; // 树的根
			phead = listpnew; // 辅助队列的队列头
			ptail = listpnew; // 辅助队列的队列尾
			pcur = listpnew; // 指向具体位置的指针
			continue;
		}
		else {
			// 尾插法往辅助队列后头加
			ptail->pnext = listpnew;
			ptail = listpnew;
		}
		// 若左孩子为空，就插入左孩子
		if (NULL == pcur->p->lchild) {
			pcur->p->lchild = pnew;
		}
		// 左孩子不为空就往右孩子插
		else if (pcur->p->rchild==NULL) {
			pcur->p->rchild = pnew;
			// 辅助队列的头往后移一位
			pcur = pcur->pnext;
		}
	}
	printf("-----前序遍历-----n");
	preOrder(tree);
	printf("n");
	printf("-----中序遍历-----n");
	inOrder(tree);
	printf("n");
	printf("-----后序遍历-----n");
	postOrder(tree);

	return 0;
}

出bug了Orz，还没解决，看了好几遍感觉没写错，夜晚不宜动太多脑子，明天再看看吧（）
哦问题解决了 好耶