首页 > 代码库 > 二叉树的常用操作
二叉树的常用操作
/*二叉树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;}
二叉树的常用操作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。