数据结构-二叉树-二叉树左右孩子交换（递归）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-二叉树-二叉树左右孩子交换（递归）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

注：本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS，因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点；

队列用于存储此时应该递归的根节点；

格式：每一行尾不能有空格；

Description

根据输入利用二叉链表创建二叉树，并将所有结点的左右孩子交换，并输出。

说明：

输入的第一行为根结点;第二行以后每行的第二元为第一元的左孩子，第三元为第一元的右孩子, 0表示空。

输出时按结点层次顺序输出。

Sample Input

A B C

B 0 D

C 0 E

D 0 0

E 0 0

Sample Output

A C B

C E 0

B D 0

E 0 0

D 0 0

Hint

说明：输出有换行

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

typedef struct BiTnode{//二叉链表存储结构
   char data;
   BiTnode *lc;
   BiTnode *rc;
}BiTnode,*BiTree;

void initTree(BiTree &T,char data='*'){//初始化树
    T=new BiTnode;
    T->lc=NULL;
    T->rc=NULL;
    if(data=='*'){
        cin>>T->data;//先输入根节点
    }
    else{
        T->data=data;
    }
}

queue<BiTree>Q;
void creatTree(BiTree &T){//递归创建二叉树
    //不能是BFS和DFS 在递归前需要把当前结点勾链并输入左孩右孩
    //同时运用队列来实现按照层次依次访问每一个非叶子结点（也就是每次递归的根节点）
    if(Q.empty()) return;//递归的终止条件
    char ch;
    int cnt=1;//计数 1左 2右
    while(cin>>ch)//输入此时根节点的左孩、右孩
    { 
	    if(T->data==ch) continue;
	    BiTnode *p=NULL;
	    if(ch!='0'){
	        initTree(p,ch);
        }
	    if(cnt==1){
            T->lc=p;
        }
        else{
            T->rc=p;
        }
	    if(p){
            Q.push(p);
        }
	    if(cnt==2) break;
	    cnt++;
	}
	Q.pop();
    creatTree(Q.front());//递归
}  
void Levelorder(BiTree T){//层次遍历二叉树
    Q.push(T);
    while(!Q.empty())//队列不为空循环
	{
		cout<<Q.front()->data<<" "; 
		if(Q.front()->rc!=NULL){
            cout<<Q.front()->rc->data<<" "; 
            Q.push(Q.front()->rc);//右孩子进队
        } 
		else {
            cout<<"0"<<" ";
        }
		if(Q.front()->lc!=NULL){
            cout<<Q.front()->lc->data<<endl; 
            Q.push(Q.front()->lc);//左孩子进队
        } 
		else {
            cout<<"0"<<"\n";
        }
	    Q.pop();
	}
}

int main(){
	BiTree Tree;//二叉链表
    initTree(Tree);
    Q.push(Tree);//先把根节点进队需要满足判断
    creatTree(Tree);
    Levelorder(Tree);
    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-759359.html

到了这里，关于数据结构-二叉树-二叉树左右孩子交换（递归）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！