大一下 数据结构 清华严蔚敏(C语言)版 学习记录——树和二叉树

基础知识点：

1、结点拥有的子树称为结点的度；

2、度为0的结点称为叶子或终端结点，度不为0的结点称为非终端结点或分支结点；

3、树的度是树内各结点的度的最大值；

4、同一个双亲的孩子之间互称兄弟；

5、结点的祖先是从根到该结点所经分支上的所有结点，子孙的定义反之；

6、结点的层次从根开始定义起，根为第一层，根的孩子为第二层；

7、其双亲在同一层的结点互为堂兄弟；

8、树中结点的最大层次称为树的深度或高度；

9、如果将树中结点的各子树看成从左至右是有次序的（即不能互换），

     则称该树为有序树，否则为无序树；

10、二叉树不是特殊的一种树！！！

11、n0 = n2+1；

12、完全二叉树和满二叉树是两种特殊形态的树；

13、二叉树的四个性质；

14、哈夫曼树的建立、求WPL值、求哈夫曼编码；

15、哈夫曼编码的长度不是唯一的；

按先序遍历的顺序建立二叉树，

然后输出每个结点和它在树中的深度

Sample Input：

        ABD##E##C##

Sample Output：

        A(1)B(2)D(3)E(3)C(2)

#include
#define MAX_TREE_SIZE 100//二叉树的最大结点数
#define OK 1
#define OVERFLOW -2
#define ERROR 0
//typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
//SqBiTree bt;
//typedef int TElemType;
typedef char TElemType;
typedef int Status;/* typedef struct BiTNode{//二叉树的结点TElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree; */typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild,*parent;int deep;//结点的深度
}BiTNode,*BiTree;typedef enum PointerTag{Link,Thread};//定义一个枚举类型typedef struct BiThrNode{//线索二叉树的结点TElemType data;struct BiThrNode *lchild,*rchild;//左右指针PointerTag LTag,RTag;//左右标志
}BiThrNode,*BiThrTree;typedef struct BPTNode{TElemType data;int parent;char LRTag;
}BPTNode;typedef struct BPTree{BPTNode nodes[MAX_TREE_SIZE];int num_node;int root;
}BPTree;Status PrintElement(TElemType e)
{   //最简单的Visit()函数//调用实例：PreOrderTraverse(T,PrintElement)printf("%d ",e);return OK;
}Status Visit(TElemType e)
{   printf("%c",e);return OK;
}Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;T->deep=d;CreatBiTree_depth(T->lchild,d+1);CreatBiTree_depth(T->rchild,d+1);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}Status BitreeDepth(BiTree T)//求二叉树的深度
{int depth,ldepth,rdepth;if(T==NULL) depth=0;else{ldepth=BitreeDepth(T->lchild);rdepth=BitreeDepth(T->rchild);depth=1+(ldepth>rdepth?ldepth:rdepth);}return depth;
}/* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
{   //Visit()是对结点操作的应用函数if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild.Visit))if(PreOrderTraverse(T->rchild.Visit)) return OK;return ERROR;}else return OK;
} *//* 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); }}return OK;
} *//* Status InOrderTraverse(BiTree T.Status(*Visit)(TElemType e))
{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;}}return OK;
} *//* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
{if(!T) return NULL;while(T->lchild){Push(S,T);T=T->lchild;}return T;
}  *//* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
{Stack *S;BiTree t,p;p=T->lchild;t=GoFarLeft(p,S);while(t){visit(t->data);if(t->rchild) t=GoFarLeft(t->rchild,S);else if(!StackEmpty(S)) t=Pop(S);else t=NULL;}
} */Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
{BiThrNode *p;p=T->lchild;//p指向根节点while(p!=T){while(p->LTag==Link) p=p->lchild;if(!Visit(p->data)) return ERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;}return OK;
}void InThreading(BiThrTree p)//二叉树先线索化函数
{BiThrNode *pre;if(p){InThreading(p->lchild);//左子树线索化if(!p->lchild)//前驱线索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//后继线索{pre->RTag=Thread;p->lchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}
}Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//遍历线索化链表
{BiThrNode *pre;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;if(!T) Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;pre->RTag=Thread;Thrt->rchild=pre;}return OK;
}Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
{if(T){printf("%c(%d)",T->data,T->deep);PreOrderTraversal(T->lchild);PreOrderTraversal(T->rchild);}return OK;
}Status InOrderTraversal(BiTree T)
{if(T){InOrderTraversal(T->lchild);Visit(T->data);InOrderTraversal(T->rchild);}return OK;
}Status PostOrderTraversal(BiTree T)
{if(T){PostOrderTraversal(T->lchild);PostOrderTraversal(T->rchild);Visit(T->data);}return OK;
}void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
{if(T){if((!T->lchild)&&(!T->rchild)) count++;CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}
}Status BitreeLeafCount(BiTree T)//统计叶子结点个数
{if(T==NULL) return 0;else{if(T->lchild==NULL&&T->rchild==NULL) return 1;else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);}
}Status BitreeCount(BiTree T)//求结点个数
{if(T==NULL) return 0;else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
}Status ChangeNode(BiTree bt)//交换左右子树
{BiTNode*temp;if(bt==NULL) return 0;ChangeNode(bt->lchild);ChangeNode(bt->rchild);temp=bt->lchild;bt->lchild=bt->rchild;bt->rchild=temp;
}int main(){BiTree T;CreatBiTree_depth(T,1);PreOrderTraversal(T);return 0;
}

由先序遍历和中序遍历序列建立二叉树，

然后输出该二叉树的后序序列

Sample Input：

        abdcef dbaecf

Hint：

        dbefca

#include
#define MAX_TREE_SIZE 100//二叉树的最大结点数
#define OK 1
#define OVERFLOW -2
#define ERROR 0
using namespace std;
//typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
//SqBiTree bt;
//typedef int TElemType;
typedef char TElemType;
typedef int Status;/* typedef struct BiTNode{//二叉树的结点TElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree; */typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild,*parent;int deep;//结点的深度
}BiTNode,*BiTree;typedef enum PointerTag{Link,Thread};//定义一个枚举类型typedef struct BiThrNode{//线索二叉树的结点TElemType data;struct BiThrNode *lchild,*rchild;//左右指针PointerTag LTag,RTag;//左右标志
}BiThrNode,*BiThrTree;typedef struct BPTNode{TElemType data;int parent;char LRTag;
}BPTNode;typedef struct BPTree{BPTNode nodes[MAX_TREE_SIZE];int num_node;int root;
}BPTree;Status PrintElement(TElemType e)
{   //最简单的Visit()函数//调用实例：PreOrderTraverse(T,PrintElement)printf("%d ",e);return OK;
}Status Visit(TElemType e)
{   printf("%c",e);return OK;
}Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;T->deep=d;CreatBiTree_depth(T->lchild,d+1);CreatBiTree_depth(T->rchild,d+1);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}void CreatBiTreeP_I(char *pre,char *in,int n)//由先序遍历和中序遍历序列建立二叉树
{if(n<=0) return ;int len=strchr(in,pre[0])-in;CreatBiTreeP_I(pre+1,in,len);CreatBiTreeP_I(pre+len+1,in+len+1,n-len-1);printf("%c",pre[0]);
}Status BitreeDepth(BiTree T)//求二叉树的深度
{int depth,ldepth,rdepth;if(T==NULL) depth=0;else{ldepth=BitreeDepth(T->lchild);rdepth=BitreeDepth(T->rchild);depth=1+(ldepth>rdepth?ldepth:rdepth);}return depth;
}/* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
{   //Visit()是对结点操作的应用函数if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild.Visit))if(PreOrderTraverse(T->rchild.Visit)) return OK;return ERROR;}else return OK;
} *//* 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); }}return OK;
} *//* Status InOrderTraverse(BiTree T.Status(*Visit)(TElemType e))
{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;}}return OK;
} *//* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
{if(!T) return NULL;while(T->lchild){Push(S,T);T=T->lchild;}return T;
}  *//* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
{Stack *S;BiTree t,p;p=T->lchild;t=GoFarLeft(p,S);while(t){visit(t->data);if(t->rchild) t=GoFarLeft(t->rchild,S);else if(!StackEmpty(S)) t=Pop(S);else t=NULL;}
} */Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
{BiThrNode *p;p=T->lchild;//p指向根节点while(p!=T){while(p->LTag==Link) p=p->lchild;if(!Visit(p->data)) return ERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;}return OK;
}void InThreading(BiThrTree p)//二叉树先线索化函数
{BiThrNode *pre;if(p){InThreading(p->lchild);//左子树线索化if(!p->lchild)//前驱线索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//后继线索{pre->RTag=Thread;p->lchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}
}Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//遍历线索化链表
{BiThrNode *pre;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;if(!T) Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;pre->RTag=Thread;Thrt->rchild=pre;}return OK;
}Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
{if(T){printf("%c(%d)",T->data,T->deep);PreOrderTraversal(T->lchild);PreOrderTraversal(T->rchild);}return OK;
}Status InOrderTraversal(BiTree T)
{if(T){InOrderTraversal(T->lchild);Visit(T->data);InOrderTraversal(T->rchild);}return OK;
}Status PostOrderTraversal(BiTree T)
{if(T){PostOrderTraversal(T->lchild);PostOrderTraversal(T->rchild);Visit(T->data);}return OK;
}void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
{if(T){if((!T->lchild)&&(!T->rchild)) count++;CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}
}Status BitreeLeafCount(BiTree T)//统计叶子结点个数
{if(T==NULL) return 0;else{if(T->lchild==NULL&&T->rchild==NULL) return 1;else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);}
}Status BitreeCount(BiTree T)//求结点个数
{if(T==NULL) return 0;else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
}Status ChangeNode(BiTree bt)//交换左右子树
{BiTNode*temp;if(bt==NULL) return 0;ChangeNode(bt->lchild);ChangeNode(bt->rchild);temp=bt->lchild;bt->lchild=bt->rchild;bt->rchild=temp;
}char a[100005],b[100005];
int main(){while(~scanf("%s%s",a,b)){CreatBiTreeP_I(a,b,strlen(a));printf("\n");}return 0;
}

建立中序线索二叉树

并按中序遍历该二叉树

Sample Input:

        ABD##E##C##

Sample Output:

        DBEAC

#include
#define MAX_TREE_SIZE 100//二叉树的最大结点数
#define OK 1
#define OVERFLOW -2
#define ERROR 0
using namespace std;
//typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
//SqBiTree bt;
//typedef int TElemType;
typedef char TElemType;
typedef int Status;/* typedef struct BiTNode{//二叉树的结点TElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree; */typedef struct BiTNode{//二叉树的结点TElemType data;struct BiTNode *lchild,*rchild,*parent;int deep;//结点的深度
}BiTNode,*BiTree;typedef enum PointerTag{Link,Thread};//定义一个枚举类型typedef struct BiThrNode{//线索二叉树的结点TElemType data;struct BiThrNode *lchild,*rchild;//左右指针PointerTag LTag,RTag;//左右标志
}BiThrNode,*BiThrTree;typedef struct BPTNode{TElemType data;int parent;char LRTag;
}BPTNode;typedef struct BPTree{BPTNode nodes[MAX_TREE_SIZE];int num_node;int root;
}BPTree;Status PrintElement(TElemType e)
{   //最简单的Visit()函数//调用实例：PreOrderTraverse(T,PrintElement)printf("%d ",e);return OK;
}Status Visit(TElemType e)
{   printf("%c",e);return OK;
}Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
{TElemType ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;T->deep=d;CreatBiTree_depth(T->lchild,d+1);CreatBiTree_depth(T->rchild,d+1);}/* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;//生成根据结点CreatBiTree(T->lchild);//构造左子树CreatBiTree(T->rchild);//构造右子树 */return OK;
}void CreatBiTreeP_I(char *pre,char *in,int n)//由先序遍历和中序遍历序列建立二叉树
{if(n<=0) return ;int len=strchr(in,pre[0])-in;CreatBiTreeP_I(pre+1,in,len);CreatBiTreeP_I(pre+len+1,in+len+1,n-len-1);printf("%c",pre[0]);
}void Creat_BiThrTree(BiThrNode* &T)//按照先序序列构造线索二叉树
{char ch;scanf("%c",&ch);if(ch=='#'||ch=='\n') T=NULL;else{T=(BiThrNode*)malloc(sizeof(BiThrNode));if(!T) exit(OVERFLOW);T->data=ch;//生成根结点Creat_BiThrTree(T->lchild);//递归构造左子树if(T->lchild) T->LTag=Link;//有左孩子Creat_BiThrTree(T->rchild);//递归构造右子树if(T->rchild) T->RTag=Link;//有右孩子}
}Status BitreeDepth(BiTree T)//求二叉树的深度
{int depth,ldepth,rdepth;if(T==NULL) depth=0;else{ldepth=BitreeDepth(T->lchild);rdepth=BitreeDepth(T->rchild);depth=1+(ldepth>rdepth?ldepth:rdepth);}return depth;
}/* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
{   //Visit()是对结点操作的应用函数if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild.Visit))if(PreOrderTraverse(T->rchild.Visit)) return OK;return ERROR;}else return OK;
} *//* 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); }}return OK;
} */void ThInOrder(BiThrNode*T)//中序遍历线索二叉树的非递归算法
{BiThrNode *p=T->lchild;//p指向根结点while(p!=T){while(p->LTag==Link){p=p->lchild;//找开始结点}printf("%c",p->data);//访问开始结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;printf("%c",p->data);}p=p->rchild;}
}/* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
{if(!T) return NULL;while(T->lchild){Push(S,T);T=T->lchild;}return T;
}  *//* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
{Stack *S;BiTree t,p;p=T->lchild;t=GoFarLeft(p,S);while(t){visit(t->data);if(t->rchild) t=GoFarLeft(t->rchild,S);else if(!StackEmpty(S)) t=Pop(S);else t=NULL;}
} */Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
{BiThrNode *p;p=T->lchild;//p指向根节点while(p!=T){while(p->LTag==Link) p=p->lchild;if(!Visit(p->data)) return ERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;}return OK;
}BiThrNode *pre;//全局变量，始终指向刚刚访问过的结点 
void InThreading(BiThrNode* &p)//中序遍历并进行中序线索化
{if(p!=NULL){InThreading(p->lchild);//左子树线索化if(p->lchild==NULL)//前驱线索{p->lchild=pre;p->LTag=Thread;}else p->LTag=Link;if(pre->rchild==NULL)//后继线索{pre->rchild=p;pre->RTag=Thread;}else pre->RTag=Link;pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}
}BiThrNode*Creat_BiThrTree_Thread(BiThrNode* &T)//中序遍历二叉树T，并将其中序线索化，root指向头结点
{BiThrNode*root;root=(BiThrNode*)malloc(sizeof(BiThrNode));if(!root) exit(OVERFLOW);root->LTag=Link;root->RTag=Thread;root->rchild=root;if(T==NULL) root->lchild=root;else{root->lchild=T;pre=root;InThreading(T);pre->rchild=root;pre->RTag=Thread;root->rchild=pre;}return root;
}Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//中序遍历线索化链表
{BiThrNode *pre;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;if(!T) Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;pre->RTag=Thread;Thrt->rchild=pre;}return OK;
}Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
{if(T){printf("%c(%d)",T->data,T->deep);PreOrderTraversal(T->lchild);PreOrderTraversal(T->rchild);}return OK;
}Status InOrderTraversal(BiTree T)
{if(T){InOrderTraversal(T->lchild);Visit(T->data);InOrderTraversal(T->rchild);}return OK;
}Status PostOrderTraversal(BiTree T)
{if(T){PostOrderTraversal(T->lchild);PostOrderTraversal(T->rchild);Visit(T->data);}return OK;
}void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
{if(T){if((!T->lchild)&&(!T->rchild)) count++;CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}
}Status BitreeLeafCount(BiTree T)//统计叶子结点个数
{if(T==NULL) return 0;else{if(T->lchild==NULL&&T->rchild==NULL) return 1;else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);}
}Status BitreeCount(BiTree T)//求结点个数
{if(T==NULL) return 0;else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
}Status ChangeNode(BiTree bt)//交换左右子树
{BiTNode*temp;if(bt==NULL) return 0;ChangeNode(bt->lchild);ChangeNode(bt->rchild);temp=bt->lchild;bt->lchild=bt->rchild;bt->rchild=temp;
}/* void AllPath(BiTree T,Stack &S)//输出二叉树上从根到所有叶子结点的路径
{if(T){Push(S,T->data);if(!T->lchild&&!T->rchild) PrintStack(S);else{AllPath(T->lchild,S);AllPath(T->rchild,S);}Pop(S);}
} *//* void OutPath(BiTree T,Stack&S)//输出树中所有从跟到叶的路径
{while(T){Push(S,T->data);if(!T->firstchild) Printstack(S);else OutPath(T->first,S);Pop(S);T=T->nextsibling;}
} */int main(){BiThrNode *root,*b;Creat_BiThrTree(b);root=Creat_BiThrTree_Thread(b);ThInOrder(root);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！