关于二叉树，基本操作都是在递归的基础上完成的，二叉树的层次遍历是队列实现。具体解释看代码
#include<iostream> #include<stack> #include<queue> #include<stdio.h> #include<stdlib.h> using namespace std; //二叉树结点 typedef struct BiTNode { //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; //重命名 将struct BiTNode命名为BiTNode，将struct BiTNode*命名为BiTree //按先序序列创建二叉树 int CreateBiTree(BiTree &T)//引用 { char data; //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 scanf("%c",&data); if(data == '#') { T = NULL; } else { T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点 T->data = data; //构造左子树 CreateBiTree(T->lchild); //构造右子树 CreateBiTree(T->rchild); } return 0; } //输出 void Visit(BiTree T) { if(T->data != '#') { printf("%c ",T->data); } } //先序遍历 void PreOrder(BiTree T) { if(T != NULL) { //访问根节点 Visit(T); //访问左子结点 PreOrder(T->lchild); //访问右子结点 PreOrder(T->rchild); } } //中序遍历 void InOrder(BiTree T) { if(T != NULL) { //访问左子结点 InOrder(T->lchild); //访问根节点 Visit(T); //访问右子结点 InOrder(T->rchild); } } //后序遍历 void PostOrder(BiTree T) { if(T != NULL) { //访问左子结点 PostOrder(T->lchild); //访问右子结点 PostOrder(T->rchild); //访问根节点 Visit(T); } } //层次遍历 void LevelOrder(BiTree T) { BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()) { //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL) { queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL) { queue.push(p->rchild); } } } //叶子节点个数 int TreeCount(BiTree T) { if(T == NULL) { return 0; } else if ((T->lchild==NULL) && (T->rchild==NULL)) { return 1;//如果此节点是叶子节点，返回1 即它本身是一个节点。 } else { return TreeCount(T->lchild)+TreeCount(T->rchild);//如果左右孩子不空，返回左孩子+右孩子节点数。 } } //求深度 int TreeDepth(BiTree T) { int rightdep=0; int leftdep=0; //如果是空树，返回-1 if(T==NULL) return -1; //如果左孩子不空，继续递归，如果为空，返回-1 if(T->lchild!=NULL) leftdep=TreeDepth(T->lchild); else leftdep=-1; //如果右孩子不空，继续递归，如果为空，返回-1 if(T->rchild!=NULL) rightdep=TreeDepth(T->rchild); else rightdep=-1; //左右孩子都递归完，返回左右孩子中较大的值 return (rightdep>leftdep) ? rightdep+1 : leftdep+1; } //交换左右孩子 void TreeExchange(BiTree T) { if(T!=NULL) { BiTree temp; if(T->lchild||T->rchild) { temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; TreeExchange(T->lchild); TreeExchange(T->rchild); } } } int main() { BiTree T; CreateBiTree(T); printf("先序遍历： "); PreOrder(T); printf(" "); printf("中序遍历： "); InOrder(T); printf(" "); printf("后序遍历： "); PostOrder(T); printf(" "); printf("层次遍历： "); LevelOrder(T); printf(" "); int deep=TreeDepth(T); printf("树的深度：%d ",deep+1); int number=TreeCount(T); printf("叶子节点个数：%d ",number); printf("交换左右孩子成功 "); TreeExchange(T); printf("层次遍历： "); LevelOrder(T); printf(" "); printf(" "); return 0; }
BiTree Q[20010];
void CreateBiTree(BiTree &T)//二叉树的层次建树 { int ch; scanf("%d",&ch); int front=1,rear=0; BiTree s; while(ch!=-1) { s=NULL; if(ch!=0) { s=(BiTree)malloc(sizeof(BiTNode)); s->data=ch; s->rchild=NULL; s->lchild=NULL; } rear++; Q[rear]=s; if(rear==1) T=s; else { if(s&&Q[front]) if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1) front++; } cin>>ch; } }