二叉树的相关操作代码(继续补全中)

#ifndef BITREEOPERATION_H#define BITREEOPERATION_H#include<stdio.h>#include<stdlib.h>#include<stack>#include<queue>typedef char ElemType;typedef struct BiNode{ElemType data;struct BiNode *lchild,*rchild;}BiNode,*BiTree;//先序建立二叉树int PreOrderCreateBiTree(BiTree& Root){char ch;scanf("%c",&ch);if(ch==' ')Root=NULL;else{Root=(BiTree)malloc(sizeof(BiNode));Root->data=ch;//生成根节点PreOrderCreateBiTree(Root->lchild);//构造左子树PreOrderCreateBiTree(Root->rchild);//构造右子树}return 0;}//先序的递归遍历void PreOrderTraverse(BiTree Root){if(Root!=NULL){printf("%c",Root->data);//访问根节点PreOrderTraverse(Root->lchild);//先序遍历左子树PreOrderTraverse(Root->rchild);//先序遍历右子树}}//中序的递归遍历void InOrderTraverse(BiTree Root){if(Root!=NULL){PreOrderTraverse(Root->lchild);//中序遍历左子树printf("%c",Root->data);//访问根节点PreOrderTraverse(Root->rchild);//中序遍历右子树}}//后序的递归遍历void PostOrderTraverse(BiTree Root){if(Root!=NULL){PreOrderTraverse(Root->lchild);//后序遍历左子树PreOrderTraverse(Root->rchild);//后序遍历右子树printf("%c",Root->data);//访问根节点}}//先序的非递归遍历，使用到栈结构void PreOrderNonRecur(BiTree Root){std::stack<BiTree> cstack;BiTree p=Root;while(p||!cstack.empty()){if(p){//根指针进栈，访问根节点，遍历左子树cstack.push(p);printf("%c",p->data);p=p->lchild; }else{//根指针退栈，遍历右子树p=cstack.top();cstack.pop();p=p->rchild;}}}//中序的非递归遍历void InOrderNonRecur(BiTree Root){if(Root!=NULL){std::stack<BiTree> cstack;BiTree p=Root;while(p||!cstack.empty()){if(p){//根指针进栈，遍历左子树cstack.push(p);p=p->lchild;}else{//根指针退栈，访问根节点，遍历右子树p=cstack.top();cstack.pop();printf("%c",p->data);p=p->rchild;}}}}//后序的非递归遍历比较麻烦些，暂时不讨论//层序遍历,使用到队列结构void levelOrderTraverse(BiTree Root){if(Root!=NULL){std::queue<BiTree> cqueue;BiTree p=Root;cqueue.push(p);while(!cqueue.empty()){p=cqueue.front();cqueue.pop();//根节点出队列printf("%c",p->data);if(p->lchild!=NULL)cqueue.push(p->lchild);if(p->rchild!=NULL)cqueue.push(p->rchild);}}}//递归求树的高度int getBiTreeHeight(BiTree Root){if(Root==NULL)return 0; //空树返回0else{int lheight=getBiTreeHeight(Root->lchild);//递归求左子树高度int rheight=getBiTreeHeight(Root->rchild);//递归求右子树高度return lheight>rheight? lheight+1:rheight+1;//树的高度为左右子树的最大者}}//求特定节点的父节点BiTree PreOrderTraverse(BiTree Root,char target,BiTree parent){if(Root!=NULL){if(Root->data==target)return parent;BiTree lparent=PreOrderTraverse(Root->lchild,target,Root);//先序遍历左子树if(lparent)return lparent;BiTree rparent=PreOrderTraverse(Root->rchild,target,Root);//先序遍历右子树if(rparent)return rparent;}return NULL;//若返回Null，则代表该子树不存在目标字符}#endif

，去旅行不在于记忆，而在于当时的那份心情。