做外贸在那些网站找业务,莱芜手机网站建设电话,熊撑号怎么做网站推广,永久免费vps服务器树作为一种逻辑结构#xff0c;同时也是一种分层结构#xff0c;具有以下两个特点#xff1a;
1#xff09;树的根结点没有前驱#xff0c;除根结点外的所有结点有 且只有一个前驱。
2#xff09;树中所有结点可以有零个或多个后继。
树结点数据结构 满二叉树和完全二… 树作为一种逻辑结构同时也是一种分层结构具有以下两个特点
1树的根结点没有前驱除根结点外的所有结点有 且只有一个前驱。
2树中所有结点可以有零个或多个后继。
树结点数据结构 满二叉树和完全二叉树 注意 完全二叉树从左到右依次排没有缺漏 二叉树的顺序存储 二叉树的层次遍历实战
项目结构 function.h文件
#ifndef LEARN_FUNCTION_H
#define LEARN_FUNCTION_H
#include stdio.h
#include stdlib.h
typedef char BiElemType;
typedef struct BiNode{BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
}BiNode, *BiTree;
//tag结构体是辅助队列使用的
typedef struct tag{BiTree p;//树的某一个结点的地址值struct tag *pnext;
}tag_t, *ptag_t;
#endif //LEARN_FUNCTION_H
main.cpp文件 calloc 申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,头文件#include stdlib.h #include function.hint main(){BiTree pnew;char c;BiTree tree NULL;ptag_t phead NULL,ptail NULL,listpnew NULL,pcur;while(scanf(%c,c)){if(c \n){break;//读到换行就结束}//calloc申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,头文件#include stdlib.hpnew (BiTree)calloc(1, sizeof(BiNode));pnew - c c;listpnew (ptag_t) calloc(1,sizeof(tag_t));//给队列结点申请空间if(NULL tree){tree pnew;//tree指向树的根结点phead listpnew;//第一个结点即是队列头,也是队列尾ptail listpnew;//pcur listpnew;//pcur要指向要进入树的父亲元素}else{//让元素先入队列ptail - pnext listpnew;ptail listpnew;//接下来把b结点放入树中if(NULL pcur - p - lchild){pcur - p - lchild pnew;//pcur - p左孩子为空,就放入左孩子}else if(NULL pcur - p - rchild){pcur - p - rchild pnew;//pcur - p右孩子为空,就放入右孩子pcur pcur - pnext;//当前结点左右孩子都有了,pcur就指向下一个}}}return 0;
}
二叉树的前序中序后序遍历 代码
main.cpp文件
#include function.h//前序遍历,也叫先序遍历,也是深度优先遍历
void PreOrder(BiTree p){ifp ! NULL{printf(%c,p - c);PreOrder(p - lchild);//打印左子树PreOrder(p - rchild);//打印右子树}
}//中序遍历
void InOrder(BiTree p){ifp ! NULL{InOrder(p - lchild);//打印左子树printf(%c,p - c);InOrder(p - rchild);//打印右子树}
}//后序遍历
void PostOrder(BiTree p){ifp ! NULL{PostOrder(p - lchild);//打印左子树v(p - rchild);//打印右子树printf(%c,p - c);}
}int main(){BiTree pnew;char c;BiTree tree NULL;ptag_t phead NULL,ptail NULL,listpnew NULL,pcur;while(scanf(%c,c)){if(c \n){break;//读到换行就结束}//calloc申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,头文件#include stdlib.hpnew (BiTree)calloc(1, sizeof(BiNode));pnew - c c;listpnew (ptag_t) calloc(1,sizeof(tag_t));//给队列结点申请空间if(NULL tree){tree pnew;//tree指向树的根结点phead listpnew;//第一个结点即是队列头,也是队列尾ptail listpnew;//pcur listpnew;//pcur要指向要进入树的父亲元素}else{//让元素先入队列ptail - pnext listpnew;ptail listpnew;//接下来把b结点放入树中if(NULL pcur - p - lchild){pcur - p - lchild pnew;//pcur - p左孩子为空,就放入左孩子}else if(NULL pcur - p - rchild){pcur - p - rchild pnew;//pcur - p右孩子为空,就放入右孩子pcur pcur - pnext;//当前结点左右孩子都有了,pcur就指向下一个}}}printf(--------PreOrder--------\n);PreOrder(tree);printf(--------InOrder--------\n);InOrder(tree);printf(--------PostOrder--------\n);PostOrder(tree);return 0;
} 二叉树的层序遍历 注意 层序遍历又称广度优先遍历而层次遍历中的前序遍历又称深度优先遍历。 项目结构 function.h文件
#ifndef LEARN_FUNCTION_H
#define LEARN_FUNCTION_H
#include stdio.h
#include stdlib.h
typedef char BiElemType;
typedef struct BiNode{BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
}BiNode, *BiTree;//tag结构体是辅助队列使用的
typedef struct tag{BiTree p;//树的某一个结点的地址值struct tag *pnext;
}tag_t, *ptag_t;//队列的结构体
typedef int ElenType;
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode;
typedef struct{LinkNode *front,*rear;//链表头,链表尾,也可以称为对头,队尾
}LinkQueue;//先进先出void InitQueue(LinkQueue Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkNode Q,ElemType x);
bool DeQueue(LinkNode Q,E;emType x);#endif //LEARN_FUNCTION_H
CMakeList.txt文件
里面的内容自动生成
queue.cpp文件
#include function.h//初始化队列
void InitQueue(LinkQueue Q){Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode));//头和尾指向同一个结点Q.front - next NULL;//头结点的next指针为NULL
}//判断队列是否为空
bool IsEmpty(LinkNode Q){return Q.rear Q.front;
}//入队
void EnQueue(LinkQueue Q,ElemType x){LinkNode *pnew (LinkNode*) malloc(sizeof(LinkNode));pnew - data x;pnew - next NULL;//要让next为NULL;Q.rear - next pnew;//尾指针的next指向pnew,因为从尾部入队Q.rear pnew;//rear要指向新的尾部
}bool DeQueue(LinkQueue Q,ElemType x){if(Q.rear Q.front){//队列为空return false;}LinkNode* q Q.front - next;//拿到第一个结点,存入qx q - data;//获取要出对的元素值Q.front - next q-next;//让第一个结点断链if(Q.rear q){//链表只剩余一个结点时,被删除后,要改变rearQ.rear Q.front;}free(q);return true;
}
main.cpp文件
#include function.h//层次遍历,层序遍历广度优先遍历
void LevelOrder(BiTree T){LinkQueue Q;//辅助队列InitQueue(Q);//初始化队列BiTree p;EnQueue(Q,T);//树根入队while(!IsEmpty(Q)){DeQueue(Q,p);//出队当前结点并打印putchar(p-c);if(p-lchild!NULL){//入队左孩子EnQueue(Q,p-lchild);}if(p-rchild!NULL){ //入队右孩子EnQueue(Q,p-rchild);}}
}//层次建树
int main(){BiTree pnew;//用来指向新申请的树结点char c;BiTree treeNULL;//树根//phead 就是队列头ptail 就是队列尾ptag_t pheadNULL,ptailNULL,listpnewNULL,pcurNULL;//输入内容为 abcdefghijwhile(scanf(%c,c)){if(c\n){break;}pnew(BiTree)calloc(1,sizeof(BiTNode));//calloc 申请空间并对空间进行初始化赋值为 0pnew-cc;//数据放进去listpnew(ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间listpnew-ppnew;if(NULLtree){treepnew;//树的根pheadlistpnew;//队列头ptaillistpnew;//队列尾pcurlistpnew;continue;}else{ptail-pnextlistpnew;//新结点放入链表通过尾插法ptaillistpnew;//ptail 指向队列尾部}//pcur 始终指向要插入的结点的位置if(NULLpcur-p-lchild)//如何把新结点放入树{pcur-p-lchildpnew;//把新结点放到要插入结点的左边}else if(NULLpcur-p-rchild){pcur-p-rchildpnew;//把新结点放到要插入结点的右边pcurpcur-pnext;//左右都放了结点后pcur 指向队列的下一个}}PostOrder(tree);printf(\n--------层次遍历-----------\n);LevelOrder(tree);printf(\n);return 0;
}
