二叉链表存储二叉树的先序遍历算法,基于二叉链表的二叉树的遍历
1 .二叉树的定义和性质
二叉树是一种树结构，其特征是一个节点上最多只有两根子树。 另外，二叉树的部分树有左右的区别，不能自由调换其顺序。
二叉树具有以下重要性质。
性质 1 二叉树的第I层最多有2^(i-1 )个节点。
性质 2 深度为k的二叉树最多具有2^k-1个节点。
性质 3 对于任何二叉树t，如果末端节点数为n0，速度为2的节点数n2，则n0=n2 1。
2 .二叉树的记忆结构
二叉树的连锁记忆结构是使用链表表示一棵二叉树，通过连锁表示要素的逻辑关系。 链表中的每个节点通常由三个域组成。
数据字段、左指针字段、右指针字段和左指针分别用于提供该节点左孩子和右孩子所在链接点的存储地址。 其节点结构如下
在此，data域存储了某个节点的数据信息； lchild和rchild分别存储指向左孩子和右孩子的指针，如果不存在左孩子或右孩子，则对应的指针字段的值为空
(用符号或NULL表示。 使用这样的节点结构表示的二叉树的连锁存储结构称为二叉树连锁表，如下。
二叉树的链式存储结构是一种非常重要的数据结构，其定义格式如下。
//二叉树的链接存储结构typedef struct Bitnode{ char data； struct Bitnode *lchild； struct Bitnode *rchild； }Bitnode，*Bitree；
3 .遍历二叉树
遍历访问路径树中的所有节点，仅访问一次。 根据根节点的位置，分为前一个导线测量、中一个导线测量和后一个导线测量。
正向扫描：根节点-左子树-右子树
中顺序扫描：左子树-根节点-右子树
后续遍历：左侧子树-右侧子树-根节点
顺序扫描： abdefgc
中顺序扫描： debgfac
后遍历： edgfbca
4 .实现横移
//voidpreorder(bitreet ) if ) t==null ) return； else { printf('%c '，T-data； preorder(t-lchild )； preorder(t-rchild )； () /按中顺序voidinorder ) bitreet ) if ) t==null ) return； ELSE{inorder(t-lchild )； printf('%c '，T-data )； inorder(t-rchild )； }//voidpostorder(bitreet ) if ) t==null ) return； ELSE{postorder(t-lchild )； postorder(t-rchild )； printf('%c '，T-data )； (//水平导线voidlevelorder ) bitreet ) { Bitree p=T； queueBitree Q； q.push(p； while (！ Q.empty () { p=Q.front； Q.pop (； printf('%c '，p-data )； if(p-lchild！=NULL ) q.push(p-lchild )； if(p-Rchild！=NULL ) q.push(p-rchild )； }
5 .求树深
//求树深的inttreedeep(bitreet ) { int deep=0； if(t ) intleftdeep=treedeep ) t-lchild； intrightdeep=treedeep(t-rch
ild); deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1; } return deep;}
6.踏实的红牛的个数
//踏实的红牛的个数int Leafcount(Bitree T,int &num){ if(T) { if(T->lchild==NULL && T->rchild==NULL) num++; Leafcount(T->lchild,num); Leafcount(T->rchild,num); } return num;}
/*-----------------------完整代码-----------------------*/#include<stdio.h>#include<stdlib.h>#include<iostream>#include<queue>#include<stack>using namespace std;//二叉树的链式存储结构typedef struct Bitnode{ char data; struct Bitnode *lchild; struct Bitnode *rchild;}Bitnode,*Bitree;//按先序序列创建二叉树void creatBitree(Bitree &T){ char ch; scanf("%c",&ch); getchar(); if(ch ==' ') T = NULL; else { T=(Bitree)malloc(sizeof(Bitnode)); T->data=ch; printf("输入%c的左子树：",ch); creatBitree(T->lchild); printf("输入%c的右子树：",ch); creatBitree(T->rchild); }}//先序遍历void preOrder(Bitree T){ if(T==NULL) return ; else { printf("%c",T->data); preOrder(T->lchild); preOrder(T->rchild); }}//中序遍历void InOrder(Bitree T){ if(T==NULL) return; else{ InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); }}//后续遍历void PostOrder(Bitree T){ if(T==NULL) return ; else{ PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); }}//层次遍历void levelOrder(Bitree T){ Bitree p=T; queue<Bitree> Q; Q.push(p); while(!Q.empty()) { p=Q.front(); Q.pop(); printf("%c",p->data); if(p->lchild!=NULL) Q.push(p->lchild); if(p->rchild!=NULL) Q.push(p->rchild); }}//求树的深度int TreeDeep(Bitree T){ int deep=0; if(T) { int leftdeep=TreeDeep(T->lchild); int rightdeep=TreeDeep(T->rchild); deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1; } return deep;}//踏实的红牛的个数int Leafcount(Bitree T,int &num){ if(T) { if(T->lchild==NULL && T->rchild==NULL) num++; Leafcount(T->lchild,num); Leafcount(T->rchild,num); } return num;}int main(){ Bitree T; int num=0; printf("输入树根："); creatBitree(T); printf("先序遍历：\n"); preOrder(T); printf("\n"); printf("中序遍历：\n"); InOrder(T); printf("\n"); printf("后序遍历：\n"); PostOrder(T); printf("\n"); printf("层次遍历：\n"); levelOrder(T); printf("\n"); printf("求树的深度:\n"); printf("%d\n",TreeDeep(T)); printf("踏实的红牛的个数:\n"); printf("%d\n",Leafcount(T, num)); return 0;}算法截图