树的遍历汇总

客官°小女子只卖身不卖艺 2023-02-23 08:12 2阅读 0赞

[算法笔记总目录][Link 1]

### 二叉树遍历 ###

#### 先序遍历 ####

//先序遍历的实现
    void preorder(node *root){ 
    	if(root == NULL){ 
    		return;//到达空树，递归边界 
    	}
    	//访问根结点root
    	printf("%d\n",root->data);
    	//访问左子树
    	preorder(root->lchild);
    	//访问右子树
    	preorder(root->rchild); 
    }

#### 中序遍历 ####

//中序遍历的实现
    void inorder(node *root){ 
    	if(root == NULL){ 
    		return;//到达空树 
    	}
    	inorder(root->lchild);
    	//访问根结点
    	printf("%d\n",root->data);
    	inorder(root->rchild); 
    }

#### 后序遍历 ####

//后序遍历的实现
    void postorder(node *root){ 
    	if(root == NULL){ 
    		return;//到达空树 
    	}
    	inorder(root->lchild);
    	inorder(root->rchild); 
    	//访问根结点
    	printf("%d\n",root->data);	
    }

#### 层序遍历 ####

//层序遍历的实现
    void Layerorder(node *root){ 
    	queue<node*> q;//注意队列里存地址
    	root->layer = 1;//根结点的层号为1 
    	q.push(root);//将根结点地址入队
    	while(!q.empty()){ 
    		node *now = q.front();//取出队首元素
    		q.pop();
    		printf("%d",now->data);//访问队首元素
    		if(now->lchild != NULL){ 
    			now->lchild->layer = now->layer + 1;//左孩子的层号为当前层号+1 
    			q.push(now->lchild);//左子树非空
    		}
    		if(now->rchild != NULL){ 
    			now->rchild->layer = now->layer + 1;//右孩子的层号为当前层号+1 
    			q.push(now->rchild);//右子树非空
    		}	 
    	} 
    }

### 树的遍历 ###

#### 树的静态写法 ####

//结构体 
    struct node{ 
    	typename data;//数据域
    /// int child[maxn];//指针域，maxn为结点上限个数 
    	vector<node> child;//数组长度可变 
    	int layer;//记录层号 
    }Node[maxn];//结点数组，maxn为结点上限个数 
    //静态实现
    int index = 0; 
    int newNode(int v){ 
    	Node[index].data = v;//数据域为v
    	Node[index].child.clear();//清空子结点
    	return index++;//返回结点下标，并令index自增 
    }

#### 树的先根遍历 ####

void PreOrder(int root){ 
    	printf("%d ",Node[root].data);//访问当前结点
    	for(int i = 0;i < Node[root].child.size();i++){ 
    		PreOrder(Node[root].child[i]);//递归访问结点root的所有子结点 
    	} 
    }

#### 树的层次遍历 ####

void LayerOrder(int root){ 
    	queue<int> Q;
    	Q.push(root);//将根结点入队
    	Node[root].layer = 0;//根结点的层数初始化为0 
    	while(!Q.empty()){ 
    		int front = Q.front();//取出队首元素
    		printf("%d ",Node[front].data);//访问当前结点的数据域
    		Q.pop();//队首元素出队
    		for(int i = 0;i < Node[front].child.size();i++){ 
    			int child = Node[front].child[i];//当前结点的第i个子结点的编号
    			Node[child].layer = Node[front].layer + 1;//子结点层数为根结点层数加一 
    			Q.push(Node[front].child[i]);//将当前结点的所有子结点入队 
    		} 
    	} 
    }

[Link 1]: https://blog.csdn.net/qq_21480607/article/details/106660085