二叉树的结点定义 、遍历 ~

• 结点定义

typedef struct BTNode{
    
	char data;    //data 的类型因题目要求而异
	struct BTNode *lchild;
	struct BTNode *rchild;
}BTNode;

遍历

• 先序遍历

void preorder(BTNode *p){
    
	if(p!=NULL){
    
		visit(p);
		preorder(p->lchild);
		preorder(p->rchild);
	}
}

• 中序遍历

void inorder(BTNode *p){
    
	if(p!=NULL){
    
		inorder(p->lchild);
		visit(p);
		inorder(p->rchild);
	}
}

• 后序遍历

void postorder(BTNode *p){
    
	if(p!=NULL){
    
		postorder(p->lchild);
		postorder(p->rchild);
		visit(p);
	}
}

• 层次遍历

/* 思路： 1.创建一个空队列 2.判断二叉树是否为空，不为空则根节点入队 3.循环直到队列为空 { 头结点出队并访问，出队头结点的左右结点入队 } */

void levelorder(BTNode *p){
    

    //创建一个空队列
	BTNode *queue[maxmize];
	int front=0,rear=0;
	BTNode *q;
    
    //判断二叉树是否为空，不为空则根节点入队
	if(p!=NULL){
    
		queue[rear]=p;
		rear=(raer+1)%MaxSize;
		
		//循环直到队列为空 { 头结点出队并访问，出队头结点的左右结点入队 }
		while(front!=rear){
    
				
			q=queue[front];                      //头结点出队并访问
		    front=(front+1)%MaxSize;
		    Visit(q);
		    
			if(q->lchild!=NULL){
                     //出队头结点的左结点入队
				queue[rear]=q->lchild;
				rear=(rear+1)%MaxSize;
			}
						
			if(q->rchild!=NULL){
                     //出队头结点的右结点入队
				queue[rear]=q->rchild;
				rear=(rear+1)%MaxSize;
			}
		}
	}
	
}

注：层次遍历相对于前三种遍历而言稍微又一点点难度，还没理解的可以去抖音上看

4i:/ zoQ复制打开抖音，看看【有个花园的作品】Leetcode大神带你手把手搞定二叉树层序遍历 ЭRIb2Ucyf00dau8ÑÑ