二叉树交换左右子树递归以及非递归算法

递归方式基本思想:

公司主营业务:成都做网站、网站设计、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出武都免费做网站回馈大家。

  • 1、当待处理节点非空时,判断其左右孩子是否不同时为空:若是,转到2、否则分别递归调用左右子树进行操作。
  • 2、新建一个辅助结点,执行交换操作。
  • 3、递归调用非空的左右子树进行操作。
BiTree *exchangeChild(BiTree *&T){
	if(T==null) return null;//当结点为null直接return null
	if(T->lchild!=null||T->rchild!=null){//当待处理结点左右孩子不同时为空时交换
		BiTNode *temp=T->lchild;//辅助结点,用于交换
		T->lchild=T->rchild;
		T->rchild=temp;
	}
	//递归交换左右子树
	exchangeChild(T->lchild);
	exchangeChild(T->rchild);
	return T;
}

非递归方式基本思想:

需要利用队列进行操作:

  • 1、当待处理结点非空时入队。
  • 2、当队非空时,转到3、,否则代表操作完成,直接return 根结点。
  • 3、队头元素出队,判断其左右孩子是否不同时为空:若是,转到4、否则将非空的左右孩子依次入队,执行2、。
  • 4、新建一个辅助结点,执行交换操作。并将非空的左右孩子依次入队,执行2、。
BiTree *exchangeChild(BiTree *&T){
	BiTNode *temp;              //辅助结点,用于交换结点
	InitQueue(Q);               //利用队列实现,初始化队列
	if(T!=null) EnQueue(Q,T);   //当结点不为空时入队
	while(!IsEmpty(Q)){         //当队非空时
		DeQueue(Q,T);       //队首元素出队
		if(T->lchild!=null||T->rchild!=null){//当队首元素的左右孩子不同时为空时执行交换操作
			temp=T->lchild;
			T->lchild=T->rchild;
			T->rchild=temp;
		}
		//对非空的孩子结点入队,继续执行上述操作
		if(T->lchild!=null){
			EnQueue(Q,T->lchild);
		}
		if(T->rchild!=null){
			EnQueue(Q,T->rchild);
		}
	}
	return T;//返回根结点
}
                             若有错误,欢迎指正
                              我们一起进步!

文章标题:二叉树交换左右子树递归以及非递归算法
当前链接:http://scyanting.com/article/dscdcjd.html