二叉树基本算法的实现（编写一个程序，实现二叉树的各种基本运算）

本文目录

• 编写一个程序，实现二叉树的各种基本运算
• 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现
• 二叉树排序算法实现（数据结构课程设计）
• 平衡二叉树的各种算法实现
• 二叉树c语言实现
• 二叉树排序算法实现 急！急！急！
• 二叉树算法是什么
• 求二叉树遍历算法C语言实现的
• 二叉树遍历的算法实现
• 急！~编写一个C++语言程序，对二叉树实现操作

编写一个程序，实现二叉树的各种基本运算

//文件名:exp7-1.cpp#include 《stdio.h》typedef char ElemType;typedef struct node{ ElemType data; //数据元素 struct node *lchild; //指向左孩子 struct node *rchild; //指向右孩子} BTNode;extern void CreateBTNode(BTNode *&b,char *str);extern BTNode *FindNode(BTNode *b,ElemType x);extern BTNode *LchildNode(BTNode *p);extern BTNode *RchildNode(BTNode *p);extern int BTNodeDepth(BTNode *b);extern void DispBTNode(BTNode *b);extern int BTWidth(BTNode *b);extern int Nodes(BTNode *b);extern int LeafNodes(BTNode *b);extern void DestroyBTNode(BTNode *&b);void main(){ BTNode *b,*p,*lp,*rp;; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树的基本运算如下:\n"); printf(" (1)输出二叉树:");DispBTNode(b);printf("\n"); printf(" (2)H节点:"); p=FindNode(b,’H’); if (p!=NULL) { lp=LchildNode(p); if (lp!=NULL) printf("左孩子为%c ",lp-》data); else printf("无左孩子 "); rp=RchildNode(p); if (rp!=NULL) printf("右孩子为%c",rp-》data); else printf("无右孩子 "); } printf("\n"); printf(" (3)二叉树b的深度:%d\n",BTNodeDepth(b)); printf(" (4)二叉树b的宽度:%d\n",BTWidth(b)); printf(" (5)二叉树b的节点个数:%d\n",Nodes(b)); printf(" (6)二叉树b的叶子节点个数:%d\n",LeafNodes(b)); printf(" (7)释放二叉树b\n"); DestroyBTNode(b);}

二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现

二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。 二叉树有两种存储结构：顺序存储和链式存储 顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用） view plaincopytypedef struct { ElemType data; int n; }SqBTree; 链式存储： view plaincopytypedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; 二叉树三种递归的遍历方法：先序遍历访问根节点→先序遍历左子树→先序遍历右子树中序遍历中序遍历左子树→访问根节点→中序遍历右子树后序遍历后序遍历左子树→后序遍历右子树→访问根节点二叉树遍历的递归算法： view plaincopyvoid preOrder(BTNode *b) //先序遍历递归算法 { if (b!=NULL) { visit(b); preOrder(b-》lchild); preOrder(b-》rchild); } } void InOrder(BTNode *b) //中序遍历递归算法 { if(b!=NULL) { InOrder(b-》lchild); visit(b); InOrder(b-》rchild); } } void PostOrder(BTNode *b) //后序遍历递归算法 { if(b!=NULL){ PostOrder(b-》lchild); PostOrder(b-》rchild); visit(b); } } 二叉树非递归遍历算法：有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法先序遍历： view plaincopyvoid PreOrder(BTNode *b) { Stack s; while(b!=NULL||!s.empty()) { if(b!=NULL){ visit(b); s.push(b); b=b-》left; } else{ b=s.pop(); b=b-》right; } } } 中序遍历： view plaincopyvoid InOrder(BTNode *b){ Stack s; while(b!=NULL||!s.empty()){ if (b!=NULL) { s.push(b); s=s-》left } if(!s.empty()){ b=s.pop(); visit(b); b=b-》right; } } } 后序遍历： view plaincopyvoid PostOrder(BTNode *b){ Stack s; while(b!=NULL){ s.push(b); } while(!s.empty()){ BTNode* node=s.pop(); if(node-》bPushed){ visit(node); } else{ s.push(node); if(node-》right!=NULL){ node-》right-》bPushed=false; s.push(node-》right); } if(node-》left!=NULL){ node-》left-》bpushed=false; s.push(node-》left); } node-》bPushed=true; //如果标识位为true,则表示入栈 } } } 层次遍历算法：（用队列的方法） view plaincopyvoid levelOrder(BTNode *b){ Queue Q; Q.push(b); while(!Q.empty()){ node=Q.front(); visit(node); if(NULL!=node-》left){ Q.push(node-》left); } if(NULL!=right){ Q.push(node-》right); } } }《span style=""》《/span》 已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序） view plaincopyint find(char c,char A,int s,int e) /* 找出中序中根的位置。 */ { int i; for(i=s;i《=e;i++) if(A==c) return i; } /* 其中pre表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */ /* 其中in表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */ /* pronum()求出pre构成的后序序列。 */ void pronum(char pre,int in_s,int in_e) { char c; int k; if(in_s》in_e) return ; /* 非法子树，完成。 */ if(in_s==in_e){printf("%c",in); /* 子树子仅为一个节点时直接输出并完成。 */ return ; } c=pre; /* c储存根节点。 */ k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */ pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */ pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */ printf("%c",c); /* 根节点输出。 */ } main() { char pre="abdc"; char in="bdac"; printf("The result:"); pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1); getch(); }

二叉树排序算法实现（数据结构课程设计）

#include 《malloc.h》 #include《stdio.h》#define NUM 7 //宏定义int i; //变量类型定义typedef struct Node{ int data ; //数据域 struct Node *next; //指针域}Node,*LNode; //用结构体构造结点及相应的指针typedef struct Tree{ int data ; struct Tree *left ; struct Tree *right ; }Tree,*LTree ; //用结构体构造树及相应的指针 CreateList( LNode Head ) //创建单链表 { for(int i=1 ; i 《=NUM ; i++) //创建循环，依次输入NUM个数据{ LNode temp ; //中间结点temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配 temp-》 next = NULL; //中间结点初始化scanf("%2d",&temp-》 data); //输入赋值到结点temp数据域 temp-》 next = Head-》 next ; Head-》 next = temp ; //将temp结点插入链表} return 1 ;//返回1} InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定{ if(!root) //root为NULL时执行{ root = (LTree)malloc(sizeof(Tree)); //动态存储分配 root-》 left =NULL; root-》 right=NULL; //初始化root-》 data = temp-》 data ; //赋值插入return 1 ; //函数正常执行，返回1} else { if(root-》 data》= temp-》 data) return InsertSqTree( root-》 left , temp ) ; //比较插入左子树else if(root-》 data 《temp-》 data) return InsertSqTree( root-》 right , temp ); //比较插入右子树} return 1 ; //如果满足，就不做处理，返回1} void BianLiTree(LTree root) //采用中序遍历，实现将所有数字按从左向右递增的顺序排序{ if(root) //root不为空执行{BianLiTree(root-》 left); //左递归处理至叶子结点，当root-》 left为NULL时不执行printf("%4d ",root-》 data); //输出BianLiTree(root-》 right); //处理右结点}} int main() { LNode Head = NULL; LTree root = NULL ; //初始化Head = (LNode) malloc(sizeof(Node)); //动态存储分配Head-》 next = NULL ; //初始化printf("please input numbers:\n");//输入提示语句if(!CreateList( Head )) //建单链表成功返回1不执行下一语句return 0; //结束函数，返回0LNode temp = Head-》 next ; //将头指针的指针域赋值予中间结点while( temp ) //temp为NULL时停止执行{ if(!InsertSqTree( root ,temp )) //排序正常执行，返回1不执行下一语句return 0 ; //结束函数，返回0Head-》 next = temp-》 next ; //将中间指针的指针域赋值予头结点指针域free(temp); //释放空间temp = Head-》 next ; //将头指针的指针域赋值予中间结点，以上三句实现了temp指针后移} printf("the result is:\n");//输出提示语句BianLiTree(root); //采用中序遍历，输出并观察树结点 return 1; //函数正常结，返回1}

平衡二叉树的各种算法实现

平衡二叉树（AVL）

那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：

图 2 可以看到以下特性：

1. 所有左子树的节点都小于其对应的父节点（4，5，6）《（7）；（4）《（5）；（8）《 （9）；

2. 所有右子树上的节点都大于其对应的父节点（8，9，10）》（7）；（6）》（5）；（10）》（9）；

3. 每个节点的平衡因子差值绝对值 《=1；

4. 每个节点都符合以上三个特征。

满足这样条件的树叫平衡二叉树（AVL）树。

问：那再次查找节点 5，需要遍历多少次呢？

由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)

如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：

图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。

二叉树c语言实现

#include《iostream.h》#include 《stdio.h》#include 《stdlib.h》typedef struct node { char data; struct node *lchild,*rchild;// }BiTNode,*BiTree;void CreatBiTree(BiTree &T){ char ch; ch=getchar(); if (ch == ’ ’) T = 0; else { T=(BiTNode*)malloc(sizeof(BiTNode)); T-》data=ch;//生成根节点 CreatBiTree(T-》lchild);//构造左子树 CreatBiTree(T-》rchild);//构造右子树 } }void preorder(BiTree T)//前序遍历{ if (T!=NULL){ printf ("%c",T-》data); preorder(T-》lchild); preorder(T-》rchild); }}void inorder(BiTree T)//中序遍历{ if (T!=NULL){ inorder(T-》lchild); printf ("%c",T-》data); inorder(T-》rchild); }}void postorder(BiTree T)//后序遍历{ if (T!=NULL){ postorder(T-》lchild); postorder(T-》rchild); printf ("%c",T-》data); }}void main (){cout《《"请输入要创建的二叉树包括空格:"《《endl ; BiTree T; CreatBiTree(T);//创建二叉树cout《《"前序遍历的结果为:"《《endl; preorder(T);cout《《endl; cout《《"中序遍历的结果为:"《《endl; inorder(T); cout《《endl; cout《《"后序遍历的结果为:"《《endl; postorder(T);}

二叉树排序算法实现 急！急！急！

//二叉排序树（升序），平均性能O(nlogn)//从根节点开始，小于节点的数放在左子树，大于等于节点的数放在右子树#include 《iostream》#include 《cmath》#include 《cstring》using namespace std;int a;//定义两个数字，a是乱序的，b是排序的结果int bshu=0;struct Node{ Node *father,*left,*right; //三个指针，父亲，左儿子，右儿子 int value; //每个节点都有一个值};Node *root; //定义二叉排序树的根结点，通常是第一个数字void add(int value,Node *p) //通过递归对树进行深度优先搜索，确认指定的数字的位置{ if(p-》left==NULL && value《p-》value) //如果值比p节点小且p节点没有左儿子 { Node *x=new Node; //定义一个新节点 x-》father=p;x-》left=NULL;x-》right=NULL; //这个新节点的父亲是p节点 x-》value=value; p-》left=x; //p节点的左儿子为这个新节点 return; //递归上升，该数字的位置已确认 } if(p-》right==NULL && value》=p-》value) //如果数字大于等于p节点且p节点没有右儿子 { Node *x=new Node; //定义一个新节点 x-》father=p;x-》left=NULL;x-》right=NULL; //这个新节点的父亲是p节点 x-》value=value; p-》right=x; //p节点的右儿子为这个新节点 return; //递归上升，该数字的位置已确认 } //如果p节点不能最终确定该数字的位置 if(value《p-》value) //如果该数字小于p节点 { add(value,p-》left); //在p节点的左子树中寻找位置，查询p节点的左儿子（递归） return; //最终总会确定该数字的位置，该数字不可能出现在p节点的右子树，直接递归上升 } if(value》=p-》value) //如果该数字大于等于p节点 { add(value,p-》right); //在p节点的右子树中寻找位置，查询p节点的右儿子（递归） return; //和上一个retrun相同的作用，此处也可省略return }}void print(Node *p) //通过递归对树进行中序遍历，左、根、右的顺序{ if(p-》left!=NULL) //如果p的左子树不为空 print(p-》left); //访问左儿子（递归） b=p-》value; //访问完毕后把p节点加入结果数组 bshu++; //数组的元素个数加1 if(p-》right!=NULL) //如果p的右子树不为空 print(p-》right); //访问右儿子（递归） //对该节点所引出的树的遍历结束，递归上升至p的父节点。}int main(){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); bshu=0; //初始化 for(int i=0;i《20;i++) { a=rand()%100; cout《《a《《" "; //生成随机数并打印原始无序序列 } cout《《endl; system("pause"); root=new Node; //为根节点分配内存 root-》father=NULL;root-》left=NULL;root-》right=NULL; //根节点没有父亲，左儿子和右儿子暂 //时为空 root-》value=a; //根节点的值是第一个数 for(int i=1;i《20;i++) //把数字一个个加入二叉排序树 add(a,root); print(root); //在对二叉排序树中的数字进行中序遍历，完成排序 for(int i=0;i《bshu;i++) cout《《b《《" "; //打印排序后的升序数列 cout《《endl; system("pause"); return 0; //main函数结束}//与快速排序一样，二叉排序树对有序序列的排序性能较差，为O(n2)，因为有序的数列无法构//成理想平衡树，导致一边走到底的现象

二叉树算法是什么

二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

性质

1、在二叉树中，第i层的结点总数不超过2^(i-1)。

2、深度为h的二叉树最多有2^h-1个结点（h》=1)，最少有h个结点。

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。

求二叉树遍历算法C语言实现的

StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，先序遍历二叉树T的递归算法。if(T){//若T不为空if(Visit(T-》data))//调用函数Visitif(PreOrderTraverse(T-》lchild,Visit))//递归调用左子树if(PreOrderTraverse(T-》rchild,Visit))returnOK;//递归调用右子树returnERROR;}elsereturnOK;}//PreOrderTraverse

二叉树遍历的算法实现

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。 根据访问结点操作发生位置命名：① NLR：前序遍历(PreorderTraversal亦称（先序遍历））——访问根结点的操作发生在遍历其左右子树之前。② LNR：中序遍历(InorderTraversal)——访问根结点的操作发生在遍历其左右子树之中（间）。③ LRN：后序遍历(PostorderTraversal)——访问根结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 1．先（根）序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴ 访问根结点；⑵ 遍历左子树；⑶ 遍历右子树。2．中（根）序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵访问根结点；⑶遍历右子树。3．后（根）序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵遍历右子树；⑶访问根结点。 用二叉链表做为存储结构，中序遍历算法可描述为：void InOrder(BinTree T){ //算法里①~⑥是为了说明执行过程加入的标号① if(T) { // 如果二叉树非空② InOrder(T-》lchild）；③ printf(%c，T-》data）； // 访问结点④ InOrder(T-》rchild);⑤ }⑥ } // InOrder 计算中序遍历拥有比较简单直观的投影法，如图 ⑴在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次（或第三次）经过结点时进行的，则是中序遍历（或后序遍历）。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。⑵上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前驱结点和一个后继结点。为了区别于树形结构中前驱（即双亲）结点和后继（即孩子）结点的概念，对上述三种线性序列，要在某结点的前驱和后继之前冠以其遍历次序名称。【例】上图所示的二叉树中结点C，其前序前驱结点是D，前序后继结点是E；中序前驱结点是E，中序后继结点是F；后序前驱结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前驱结点是A，后继结点是E和F。二叉链表基本思想基于先序遍历的构造，即以二叉树的先序序列为输入构造。注意：先序序列中必须加入虚结点以示空指针的位置。【例】建立上图所示二叉树，其输入的先序序列是：ABD∮∮∮CE∮∮F∮∮。构造算法假设虚结点输入时以空格字符表示，相应的构造算法为：void CreateBinTree (BinTree **T){ //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参（根指针）本身 char ch； if((ch=getchar())==’’) *T=NULL； //读入空格，将相应指针置空 else{ //读人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode））； //生成结点 （*T)-》data=ch； CreateBinTree(&(*T)-》lchild）； //构造左子树 CreateBinTree(&(*T)-》rchild）； //构造右子树 }}注意：调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。示例设root是一根指针（即它的类型是BinTree），则调用CreateBinTree(&root）后root就指向了已构造好的二叉链表的根结点。二叉树建立过程见下面是关于二叉树的遍历、查找、删除、更新数据的代码（递归算法）： #include《iostream》#include《cstdio》#include《cmath》#include《iomanip》#include《cstdlib》#include《ctime》#include《algorithm》#include《cstring》#include《string》#include《vector》#include《list》#include《stack》#include《queue》#include《map》#include《set》using namespace std;typedef int T;class bst{    struct Node    {        T data;        Node* L;        Node* R;        Node(const T& d,Node* lp=NULL,Node* rp=NULL):data(d),L(lp),R(rp) {}    };    Node* root;    int num;public:    bst():root(NULL),num(0) {}    void clear(Node* t)    {        if(t==NULL) return;        clear(t-》L);        clear(t-》R);        delete t;    } ~bst()    {        clear(root);    } void clear()    {        clear(root);        num = 0;        root = NULL;    } bool empty()    {        return root==NULL;    } int size()    {        return num;    } T getRoot()    {        if(empty()) throw empty tree;        return root-》data;    } void travel(Node* tree)    {        if(tree==NULL) return;        travel(tree-》L);        cout 《《 tree-》data 《《 ’ ’;        travel(tree-》R);    } void travel()    {        travel(root);        cout 《《 endl;    } int height(Node* tree)    {        if(tree==NULL) return 0;        int lh = height(tree-》L);        int rh = height(tree-》R);        return 1+(lh》rh?lh:rh);    } int height()    {        return height(root);    } void insert(Node*& tree,const T& d)    {        if(tree==NULL)  tree = new Node(d);        else if(ddata)  insert(tree-》L,d);        else  insert(tree-》R,d);    } void insert(const T& d)    {        insert(root,d);        num++;    } Node*& find(Node*& tree,const T& d)    {        if(tree==NULL) return tree;        if(tree-》data==d) return tree;        if(ddata)  return find(tree-》L,d);        else  return find(tree-》R,d);    } bool find(const T& d)    {        return find(root,d)!=NULL;    } bool erase(const T& d)    {        Node*& pt = find(root,d);        if(pt==NULL) return false;        combine(pt-》L,pt-》R);        Node* p = pt;        pt = pt-》R;        delete p;        num--;        return true;    } void combine(Node* lc,Node*& rc)    {        if(lc==NULL) return;        if(rc==NULL) rc = lc;        else combine(lc,rc-》L);    } bool update(const T& od,const T& nd)    {        Node* p = find(root,od);        if(p==NULL) return false;        erase(od);        insert(nd);        return true;    }};int main(){    bst b;    cout 《《 input some integers:;    for(;;)    {        int n;        cin 》》 n;        b.insert(n);        if(cin.peek()==’\n’) break;    }for(;;)    {        cout 《《 input data pair:;        int od,nd;        cin 》》 od 》》 nd;        if(od==-1&&nd==-1） break;  b.update(od,nd);    }}

急！~编写一个C++语言程序，对二叉树实现操作

二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。【数据描述】 //- - - - - - 二叉树的二叉链表存储表示 - - - - - - -typedef struct BiTNode{ TElemType data; Struct BiTNode * lchild, * rchild; //左右孩子指针}BiTNode, * BiTree;【算法描述】1. 建立一棵二叉树Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树，//构造二叉链表表示的二叉树T。scanf(&ch);if (ch==’＃’) T=NULL;else { if (!(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit (OVERFLOW); T-》data = ch; //生成根结点 CreateBiTree(T-》lchild); //生成左子树 CreateBiTree(T-》rchild); //生成右子树}return OK;}//CreateBiTree2. 先序遍历二叉树递归算法Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦visit()失败，则操作失败。if (T){ if (Visit(T-》data))if (PreOrderTraverse(T-》rchild，Visit)) return OK;return ERROR;}else return OK;}// PreOrderTraverse3. 中序遍历的递归算法Status InOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){if (T){ if (Visit(T-》data))if (InOrderTraverse(T-》rchild，Visit)) return OK;return ERROR;}else return OK;}// InOrderTraverse4. 后序遍历递归算法Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){if (T){ if (Visit(T-》data))if (PreOrderTraverse(T-》rchild，Visit)) return OK;return ERROR;}else return OK;}// PreOrderTraverse5. 中序遍历非递归算法之一Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) { InitStack(S); Push(S,T); //根指针进栈 While (!StackEmpty(S)) {While (GetTop(S,p) && p) Push(S,p-》lchild); //向左走到尽头Pop(S,p); //空指针退栈If (!StackEmpty(S)) { //访问结点，向右一步 Pop(S,p); If (!Visit(p-》data)) return ERROR; Push(S,p-》rchild);}//if}//whilereturn OK; }//InOrderTraverse6. 中序遍历非递归算法之二Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) { //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S); p=T; While (p‖!StackEmpty(S)) {if (p) {Push(S,p); p=p-》lchild;} //根指针进栈，遍历左子树else { //根指针退栈，访问根结点，遍历右子树Pop(S,p); if (!Visit(p-》data)) return ERROR; p=p-》rchild);}//else}//whilereturn OK; }//InOrderTraverse7． 层次遍历二叉树的非递归算法Status LevelOrder(BiTree T){ //按层次遍历二叉树T， Q为队列 InitQueue(Q); If (T!=NULL){// 若树非空 EnQueue(Q,T);//根结点入队列 While (!QueueEmpty(Q)){ DeQueue(Q,b); //队首元素出队列 Visit(b-》data); //访问结点 If (b-》lchild!=NULL) EnQueue(Q,b-》lchild);//左子树非空，则入队列 If (b-》rchold!=Null) EnQueue(Q,b-》rchild);//右子树非空，则入队列 }//while }//if}LevelOrder8． 求二叉树的深度int depth(BiTree T){//若T为空树，则深度为0，否则其深度等于左子树或右子树的最大深度加1 if (T==NULL) return 0; else {dep1=depth(T-》lchild); dep2=depth(T-》rchild); return dep1》dep2?dep1+1:dep2+1;} }【C源程序】#include 《stdio.h》#include 《stdlib.h》#define MAX 20#define NULL 0typedef char TElemType;typedef int Status;typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;Status CreateBiTree(BiTree *T){ char ch; ch=getchar(); if (ch==’#’) (*T)=NULL; /* #代表空指针*/ else { (*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点 */ (*T)-》data=ch; /*生成根结点 */ CreateBiTree(&(*T)-》lchild) ; /*构造左子树 */ CreateBiTree(&(*T)-》rchild) ; /*构造右子树 */ } return 1;}void PreOrder(BiTree T){ if (T) { printf("%2c",T-》data); /*访问根结点，此处简化为输出根结点的数据值*/ PreOrder(T-》lchild); /*先序遍历左子树*/ PreOrder(T-》rchild); /*先序遍历右子树*/ }}void LevleOrder(BiTree T){/*层次遍历二叉树T，从第一层开始，每层从左到右*/BiTree Queue,b; /*用一维数组表示队列，front和rear分别表示队首和队尾指针*/ int front,rear; front=rear=0; if (T) /*若树非空*/ {Queue=T; /*根结点入队列*/ while (front!=rear){ /*当队列非空*/b=Queue; /*队首元素出队列，并访问这个结点*/ printf("%2c",b-》data); if (b-》lchild!=NULL) Queue=b-》lchild; /*左子树非空，则入队列*/ if (b-》rchild!=NULL) Queue=b-》rchild; /*右子树非空，则入队列*/ } }}//LevelOrderint depth(BiTree T){ /*求二叉树的深度*/int dep1,dep2;if (T==NULL) return 0; else {dep1=depth(T-》lchild); dep2=depth(T-》rchild); return dep1》dep2?dep1+1:dep2+1;}}//depthmain(){ BiTree T=NULL; printf("\nCreate a Binary Tree\n"); CreateBiTree(&T); /*建立一棵二叉树T*/ printf("\nThe preorder is:\n"); PreOrder(T); /*先序遍历二叉树*/ printf("\nThe level order is:\n"); LevleOrder(T); /*层次遍历二叉树*/printf("\nThe depth is:%d\n",depth(T));}【测试数据】1. 输入：#↙，建立一棵空树， 先序遍历和层次遍历没有输出，树的深度输出为0；2. 输入：A↙先序和层次遍历输出均为A；深度输出为：13. 输入：ABC##DE#G##F###↙，先序输出为： A B C D E G F层次遍历输出为：A B C D E F G深度输出为： 5 【说明】1. 按先序次序输入二叉树中结点的值，用’#’表示空树，对每一个结点应当确定其左右子树的值（为空时必须用特定的空字符占位），故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定，若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列；2. 为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然后通过函数指针进行函数的调用。读者若有兴趣，可自行编写。