P5树学习笔记-网站名

//二叉树顺序存储#define MaxSize 100struct TreeNode {ElemType value; //节点中数据元素bool isEmpty; //节点是否为空};TreeNode t [MaxSize];for (int i 0; i MaxSize; i) {t[i].isEmpty true;}//二叉树的链式存储struct ElemType {int value;};typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild; //左右孩子指针// struct BiTNode *parent; //三叉链表的父结点指针} BiNode, *BiTree;//定义一颗空树BiTree root NULL;//插入根节点root (BiTree)malloc(sizeof(BiTNode));root-data {1};root-lchild NULL;root-rchild NULL;//插入新节点BiTNode *p {BiTNode *} malloc(sizeof(BiTNode));p-data {2};p-lchild NULL;p-rchild NULL;root-lchild p;//5.3二叉树的遍历和线索二叉树typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild}BiTNode,*BiTree;//先序遍历void PreOrder(BiTree T){if(T!NULL){visit(T);PreOrder (T-lchild);PreOrder(T-rchild);}}//中序遍历void InOrder (BiTree T){if(T!NULL){InOrder(T-lchild);visit(T);InOrder(T-child);}}//后序遍历void PostOrder (BiTree T){if(T!NULL){PostOrder (T-lchild);PostOrder (T-rchild);visit(T);}}//层次遍历void LevelOrder(BiTree T){LinkQueue Q;InitQueue(Q);BiTree p;EnQueue(Q,T); //将根节点入队while (!isEmpty(Q)){DeQueue(Q,p); //队头节点出队visit(p);if(p-lchild!NULL)EnQueue(Q,p-child); //左孩子入队if(p-rchild!NULL) //右孩子入队EnQueue(Q,p-rchild) ;}}//二叉树节点链式存储typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode ,*BiTree;//链式队列节点typedef struct LinkNode{BiTNode *data;struct LinkNode *next;}LinkNode;typedef struct{LinkNode *front,*rear;}LinkQueue;//线索二叉树//二叉树的节点链式存储typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//线索二叉树结点typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtang; //左右线索标志//tag1表示指针指向孩子tag0时指针指向线索}ThreadNode,*ThreadTree;//中序线索化//线索二叉树树节点typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag;}ThreadNode,* ThreadTree;//中序遍历二叉树遍历线索化void InThread(ThreadTree T){if(T!NULL){InThread(T-lchild);visit(T);InThread(T-rchild);}}void visit (ThreadNode *q){if(q-lchildNULL){//左子树为空q-lchildpre;q-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildq;pre-rtag1;}preq;}//全局变量pre指向当前访存节点前驱ThreadNode *preNULL;//中序线索化二叉树Tvoid CreateInThread(ThreadTree T){preNULL;if(T!NULL){//非空才能线索化InThread(T);if(pre-rchildNULL)pre-rtag1;}}//双亲表示法#define MAX_TREE_SIZE 100typedef struct{ElemType data;int parent;}PTNode;typedef struct{PTNode nodes[MAX_TREE_SIZE];int n;}PTree;//孩子表示法struct CTNode{int child;struct CTNode *next;};typedef struct{ElemType data;struct CTNode *firstChild;}CTBox;typedef struct{CTBox nodes[MAX_TREE_SIZE];int n,r;}CTree;//孩子兄弟表示法森林根节点算兄弟typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling; //孩子指针和兄弟指针}CSNode,*CSTree;//先根遍历void PreOrder(TreeNode *R){if(R!NULL){visit(R);while(R有下有一个子树T)PreOrder(T);}}//后根遍历void PostOrder(TreeNode *R) {if(R!NULL){while(R还有下一个子树T)PostOrder(T);visit(R);}}//并查集#define SIZE 13int UFSets[Size]; //集合元素数组//初始化并查集void Initial (int S[]){for(int i0;iSIZE;I)S[i]-1;}//Fine查找集合返回根节点时间复杂度最坏为O(N)int Find(int S[],int x){while (S[x]0)xS[x];return x;}//Union 并操作将两个集合合并为一个时间复杂度O(1)void Union (int S[],int Root1,int Root2){//要求Root1和Root2是不同的集合if(Root1Root2) return;//将2链接到1下面S[Root2]Root1;}//Union 并操作的优化 ,小树合并到大树void Union(int S[],int Root1,Root2]) {if(Root1Root2) return;if(S[Root2]S[Root1]){S[Root1]S[Root2];S[Root2]Root1;}else{S[Root2]S[Root1];S[Root1]Root2;}}//Find 的优化压缩路径接到根节点上int Find(int S[],int x){int rootx;while(S[root]0) rootS[root]; //循环找到根while(x!root){ //压缩路径int tS[x]; //t指向x的父节点S[x]root; //x直接挂到根节点下xt;}return root;}

资讯详情

P5树学习笔记