简单的学习记录 | 二叉树 孩子兄弟树的层次遍历

不知不觉已经12月了，感觉离胜利的日子已经不远了，啊啊啊。

---

 

下午回宿舍解决一下没怎么写过层次遍历和孩子兄弟树的问题。

先写了个二叉树的层次遍历试试（手动赋值实在是太麻烦了）

#include <stdio.h>


typedef struct BiTNode{
	char val;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;


// 递归中序遍历
// 前中后 英文 preorder/inorder/postorder traversal 
void InOrderTraversal(BiTree T){
	if(T != NULL){
		InOrderTraversal(T->lchild);
		printf("%c ", T->val);
		InOrderTraversal(T->rchild);
	}
}

// 层次遍历
// 使用队列
void LevelOrderTraversal(BiTree T){
	int BQueueLength = 100;
	BiTree BQueue[100];
	BiTree tmp;   // 临时二叉树指针 
	int rear, front;
	rear = 0;    // 队尾 
	front = 0;   // 队头 
	// 将第一个节点加入队列
	BQueue[rear] = T;
	rear ++;
	
	while(rear != front){   // 判断队空 
		// 取队头元素
		tmp = BQueue[front];
		front ++;
		// 将队头元素的子孙加入队列
		if (tmp->lchild != NULL){
			BQueue[rear] =  tmp->lchild;
			rear ++;
		}
		if (tmp->rchild != NULL){
			BQueue[rear] =  tmp->rchild;
			rear ++;
		}
		printf("%c ", tmp->val);		
	}
	
	 
} 

int main(){
	// 创建二叉树
	BiTree T = new BiTNode;
	T->val = 'A';
	T->lchild = new BiTNode;
	T->rchild = NULL;
	T->lchild->val = 'B';
	T->lchild->lchild = new BiTNode;
	T->lchild->lchild->val = 'C';
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	T->lchild->rchild = new BiTNode;
	T->lchild->rchild->val = 'D';
	T->lchild->rchild->lchild = new BiTNode;
	T->lchild->rchild->lchild->val = 'E';
	T->lchild->rchild->lchild->lchild = NULL;
	T->lchild->rchild->lchild->rchild = new BiTNode;
	T->lchild->rchild->lchild->rchild->val = 'G';
	T->lchild->rchild->lchild->rchild->rchild = NULL;
	T->lchild->rchild->lchild->rchild->lchild = NULL;
	T->lchild->rchild->rchild = new BiTNode;
	T->lchild->rchild->rchild->val = 'F';
	T->lchild->rchild->rchild->rchild = NULL;
	T->lchild->rchild->rchild->lchild = NULL;
	
	// 递归遍历测试
	InOrderTraversal(T); 
	printf("\n--------------------\n");
	
	// 层次遍历测试
	LevelOrderTraversal(T); 
	
	return 0;
}

---

之后再写个孩子兄弟树的层次遍历（毕竟考的次数很多）

跟二叉树的层次遍历有点区别，是每次直接把小孩全都入队【也就是把左子树的右子树全部整进去】，中间那块儿写的还是有点乱的，把逻辑理清楚就没问题了。

代码如下：

// 对应真题2021数据结构第一题 

#include <stdio.h>

typedef struct CSNode{
	int val;
	struct CSNode *firstchild, *nextsibling;  // firstchild本质上就是左子树 nextsibling本质上就是右子树 
	
	// 因为手动创建实在是太tm麻烦了所以当成class来用了
	CSNode(int val){
		this->val = val;
		this->firstchild = NULL;
		this->nextsibling = NULL;
	}
}CSNode, *CSTree;

void LevelOrderTraversal(CSTree T){
	CSTree tmp; // 临时变量
	CSTree tmp0; 
	// 初始化队列 
	const int queuelength = 100;
	CSTree CQueue[100];
	int rear = 0;
	int front = 0;
	// 将第一个节点入队
	CQueue[rear] = T;
	rear ++;
	
	while (rear != front){
		// 取队头节点
		tmp = CQueue[front];
		front = (front + 1) % queuelength;   // 循环队列，上一个代码没写mod
				
		// 将孩子+孩子的兄弟加入队列【这里和二叉树的层次遍历是不一样的需要注意】 
		if (tmp->firstchild != NULL){
			CQueue[rear] = tmp->firstchild;
			rear = (rear + 1)% queuelength;
			tmp0 = tmp->firstchild; 
			while (tmp0->nextsibling != NULL){
				CQueue[rear] = tmp0->nextsibling;
				rear = (rear + 1) % queuelength;
				tmp0 = tmp0->nextsibling;
			}
		} 
		// 输出
		printf("输出：%d \n", tmp->val); 
	} 
	
}

void LevelOrderTraversalAndFind(CSTree T, int val){
	CSTree tmp; // 临时变量
	CSTree tmp0; 
	CSTree parent;
	// 初始化队列 
	const int queuelength = 100;
	CSTree CQueue[100];
	int rear = 0;
	int front = 0;
	// 将第一个节点入队
	CQueue[rear] = T;
	rear ++;
	
	while (rear != front){
		// 取队头节点
		tmp = CQueue[front];
		parent = tmp;
		front = (front + 1) % queuelength;   // 循环队列，上一个代码没写mod
				
		// 将孩子+孩子的兄弟加入队列【这里和二叉树的层次遍历是不一样的需要注意】 
		if (tmp->firstchild != NULL){
			CQueue[rear] = tmp->firstchild;
			rear = (rear + 1)% queuelength;
			tmp0 = tmp->firstchild;
			// 看看刚入队的是不是要找的 
			if (tmp->firstchild->val == val){
				// 找到了
				printf("双亲：%d\n", parent->val);
				// 遍历兄弟
				tmp0 = parent->firstchild;
				while (tmp0->nextsibling != NULL){
					printf(" > 兄弟: %d \n", tmp0->nextsibling->val);
					tmp0 = tmp0->nextsibling;
				}
				return;
			}
			while (tmp0->nextsibling != NULL){
				CQueue[rear] = tmp0->nextsibling;
				rear = (rear + 1) % queuelength;
				// 判断是不是要找到的
				if (tmp0->nextsibling->val == val){
					printf("双亲：%d \n", parent->val);
					tmp0 = parent->firstchild;
					printf(" > 兄弟: %d \n", parent->firstchild->val);
					while(tmp0->nextsibling != NULL){
						printf(" > 兄弟: %d \n", tmp0->nextsibling->val);
						tmp0 = tmp0->nextsibling;
					}
					return;
				} 
				tmp0 = tmp0->nextsibling;
			}
		} 
		// 输出
		printf("输出：%d \n", tmp->val); 
	} 
	
}

int main(){
	CSTree T = new CSNode(1);
	T->firstchild = new CSNode(2);
	T->firstchild->nextsibling = new CSNode(4);
	T->firstchild->nextsibling->nextsibling = new CSNode(6);
	T->firstchild->firstchild = new CSNode(3);
	T->firstchild->firstchild->nextsibling = new CSNode(5);
	T->firstchild->nextsibling->nextsibling->firstchild = new CSNode(7);
	T->firstchild->nextsibling->nextsibling->firstchild->firstchild = new CSNode(8);
	T->firstchild->nextsibling->nextsibling->firstchild->firstchild->nextsibling = new CSNode(9);
	T->firstchild->nextsibling->nextsibling->firstchild->firstchild->nextsibling->nextsibling = new CSNode(10);
	
	// 层次遍历 
	LevelOrderTraversal(T); 
	printf("\n====================================\n");
	// 层次遍历找指定节点的双亲和兄弟
	int val = 8;
	LevelOrderTraversalAndFind(T, val); 
	
	return 0;
}

 

---

Share