首页 > 代码库 > 二叉树的常用操作

二叉树的常用操作

/*二叉树1、创建二叉树2、先序遍历3、中序遍历4、后序遍历5、二叉树的深度6、二叉树的镜像*/#include "stdafx.h"#include <iostream>#include <queue>#include <stdio.h>using namespace std;typedef struct BiNode  //声明二叉树{	char data;	struct BiNode *lchild, *rchild;}*BiTree,BiNode;//按先序序列建立二叉树的二叉链表BiTree CreateBiTree(BiTree &T) {  //引用传参(如果是指针就会报错)	char ch;	cin >> ch;	if (ch==‘#‘) {		T = NULL;	}	else {		T = (BiTree )malloc(sizeof(BiNode));//申请动态内存		T->data = http://www.mamicode.com/ch;" ";	if(T->lchild!=NULL)		PreOrder(T->lchild);	if(T->rchild!=NULL)		PreOrder(T->rchild);}//中序遍历void MidOrder(BiTree T){	if (T == NULL)		return ;	if (T->lchild != NULL)		MidOrder(T->lchild);	cout << T->data << " ";	if (T->rchild)		MidOrder(T->rchild);}//后序遍历void PostOrder(BiTree T){	if (T == NULL)		return;	if (T->lchild)		PostOrder(T->lchild);	if (T->rchild)		PostOrder(T->rchild);	cout << T->data <<" ";}//二叉树的深度int TreeDepth(BiTree T){	if (T == NULL)//如果根节点为空		return 0;	//如果T!=NULL至少深度为1	int left = 1;	int right = 1;	left += TreeDepth(T->lchild);//求左子树的深度	right += TreeDepth(T->rchild);//求右子树的深度	return left > right ? left : right;}//二叉树的宽度(有一定难度)//二叉树的镜像void MirrorTree(BiTree T){	if (T == NULL)  //根节点为空		return ;	if ((T->lchild == NULL) && (T->rchild == NULL))  //左右孩子都不为空(必须保证左右节点存在时交换左右孩子的指针)		return;	//交换根节点左右节点的的指针	BiNode *temp = T->lchild;	T->lchild = T->rchild;	T->rchild = temp;	if (T->lchild)		MirrorTree(T->lchild);	if (T->rchild)		MirrorTree(T->rchild);}int main(){	BiTree root=NULL;  	root=CreateBiTree(root);//返回根节点的地址	cout <<"先序遍历" << endl;	PreOrder(root);	cout <<endl<<"中序遍历"<<endl;	MidOrder(root);	cout <<endl<<"后序遍历" << endl;	PostOrder(root);	cout << endl;	int treeDepth = TreeDepth(root);	cout << "树的深度是:"<<treeDepth<<endl;	MirrorTree(root);//二叉树的镜像	PreOrder(root);//先序遍历    return 0;}

  

二叉树的常用操作