空压机网站开发公司,wordpress口腔,做代金券的网站,网络营销推广目标三叉链表存储表示 改进于二叉链表#xff0c;增加指向父节点的指针#xff0c;能更好地实现结点间的访问。 存储结构 /* 二叉树的三叉链表存储表示 */typedef struct BiTPNode{TElemType data;struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */}BiTPNode,*…三叉链表存储表示 改进于二叉链表增加指向父节点的指针能更好地实现结点间的访问。 存储结构 /* 二叉树的三叉链表存储表示 */typedef struct BiTPNode{TElemType data;struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */}BiTPNode,*BiPTree; 基本操作基于C/C的实现算法 /* 二叉树的三叉链表存储的基本操作(21个) */#define ClearBiTree DestroyBiTree /* 清空二叉树和销毀二叉树的操作一样 */void InitBiTree(BiPTree *T){ /* 操作结果构造空二叉树T */*TNULL;}void DestroyBiTree(BiPTree *T){ /* 初始条件二叉树T存在。操作结果销毀二叉树T */if(*T) /* 非空树 */{if((*T)-lchild) /* 有左孩子 */DestroyBiTree((*T)-lchild); /* 销毀左孩子子树 */if((*T)-rchild) /* 有右孩子 */DestroyBiTree((*T)-rchild); /* 销毀右孩子子树 */free(*T); /* 释放根结点 */*TNULL; /* 空指针赋0 */}}void CreateBiTree(BiPTree *T){ /* 按先序次序输入二叉树中结点的值(可为字符型或整型在主程中定义)*//* 构造三叉链表表示的二叉树T */TElemType ch;scanf(form,ch);if(chNil) /* 空 */*TNULL;else{*T(BiPTree)malloc(sizeof(BiTPNode)); /* 动态生成根结点 */if(!*T)exit(OVERFLOW);(*T)-datach; /* 给根结点赋值 */(*T)-parentNULL; /* 根结点无双亲 */CreateBiTree((*T)-lchild); /* 构造左子树 */if((*T)-lchild) /* 有左孩子 */(*T)-lchild-parent*T; /* 给左孩子的双亲域赋值 */CreateBiTree((*T)-rchild); /* 构造右子树 */if((*T)-rchild) /* 有右孩子 */(*T)-rchild-parent*T; /* 给右孩子的双亲域赋值 */}}Status BiTreeEmpty(BiPTree T){ /* 初始条件二叉树T存在。操作结果若T为空二叉树则返回TRUE否则FALSE */if(T)return FALSE;elsereturn TRUE;}int BiTreeDepth(BiPTree T){ /* 初始条件二叉树T存在。操作结果返回T的深度 */int i,j;if(!T)return 0; /* 空树深度为0 */if(T-lchild)iBiTreeDepth(T-lchild); /* i为左子树的深度 */elsei0;if(T-rchild)jBiTreeDepth(T-rchild); /* j为右子树的深度 */elsej0;return ij?i1:j1; /* T的深度为其左右子树的深度中的大者1 */}TElemType Root(BiPTree T){ /* 初始条件二叉树T存在。操作结果返回T的根 */if(T)return T-data;elsereturn Nil;}TElemType Value(BiPTree p){ /* 初始条件二叉树T存在p指向T中某个结点。操作结果返回p所指结点的值 */return p-data;}void Assign(BiPTree p,TElemType value){ /* 给p所指结点赋值为value */p-datavalue;}typedef BiPTree QElemType; /* 设队列元素为二叉树的指针类型 */#includec3-2.h /* 链队列 */#includebo3-2.c /* 链队列的基本操作 */BiPTree Point(BiPTree T,TElemType e){ /* 返回二叉树T中指向元素值为e的结点的指针。按层序遍历搜索 */LinkQueue q;QElemType a;if(T) /* 非空树 */{InitQueue(q); /* 初始化队列 */EnQueue(q,T); /* 根结点入队 */while(!QueueEmpty(q)) /* 队不空 */{DeQueue(q,a); /* 出队队列元素赋给a */if(a-datae)return a;if(a-lchild) /* 有左孩子 */EnQueue(q,a-lchild); /* 入队左孩子 */if(a-rchild) /* 有右孩子 */EnQueue(q,a-rchild); /* 入队右孩子 */}}return NULL;}TElemType Parent(BiPTree T,TElemType e){ /* 初始条件二叉树T存在e是T中某个结点 *//* 操作结果若e是T的非根结点则返回它的双亲否则返回空*/BiPTree a;if(T) /* 非空树 */{aPoint(T,e); /* a是结点e的指针 */if(aa!T) /* T中存在结点e且e是非根结点 */return a-parent-data; /* 返回e的双亲的值 */}return Nil; /* 其余情況返回空 */}TElemType LeftChild(BiPTree T,TElemType e){ /* 初始条件二叉树T存在e是T中某个结点。操作结果返回e的左孩子。若e无左孩子,则返回空 */BiPTree a;if(T) /* 非空树 */{aPoint(T,e); /* a是结点e的指针 */if(aa-lchild) /* T中存在结点e且e存在左孩子 */return a-lchild-data; /* 返回e的左孩子的值 */}return Nil; /* 其余情況返回空 */}TElemType RightChild(BiPTree T,TElemType e){ /* 初始条件二叉树T存在e是T中某个结点。操作结果返回e的右孩子。若e无右孩子,则返回空 */BiPTree a;if(T) /* 非空树 */{aPoint(T,e); /* a是结点e的指针 */if(aa-rchild) /* T中存在结点e且e存在右孩子 */return a-rchild-data; /* 返回e的右孩子的值 */}return Nil; /* 其余情況返回空 */}TElemType LeftSibling(BiPTree T,TElemType e){ /* 初始条件二叉树T存在e是T中某个结点 *//* 操作结果返回e的左兄弟。若e是T的左孩子或无左兄弟则返回空*/BiPTree a;if(T) /* 非空树 */{aPoint(T,e); /* a是结点e的指针 */if(aa!Ta-parent-lchilda-parent-lchild!a) /* T中存在结点e且e存在左兄弟 */return a-parent-lchild-data; /* 返回e的左兄弟的值 */}return Nil; /* 其余情況返回空 */}TElemType RightSibling(BiPTree T,TElemType e){ /* 初始条件二叉树T存在e是T中某个结点 *//* 操作结果返回e的右兄弟。若e是T的右孩子或无右兄弟则返回空*/BiPTree a;if(T) /* 非空树 */{aPoint(T,e); /* a是结点e的指针 */if(aa!Ta-parent-rchilda-parent-rchild!a) /* T中存在结点e且e存在右兄弟 */return a-parent-rchild-data; /* 返回e的右兄弟的值 */}return Nil; /* 其余情況返回空 */}Status InsertChild(BiPTree p,int LR,BiPTree c) /* 形参T无用 */{ /* 初始条件二叉树T存在p指向T中某个结点LR为0或1非空二叉树c与T不相交且右子树为空 *//* 操作结果根据LR为0或1插入c为T中p所指结点的左或右子树。p所指结点 *//* 的原有左或右子树则成为c的右子树 */if(p) /* p不空 */{if(LR0){c-rchildp-lchild;if(c-rchild) /* c有右孩子(p原有左孩子) */c-rchild-parentc;p-lchildc;c-parentp;}else /* LR1 */{c-rchildp-rchild;if(c-rchild) /* c有右孩子(p原有右孩子) */c-rchild-parentc;p-rchildc;c-parentp;}return OK;}return ERROR; /* p空 */}Status DeleteChild(BiPTree p,int LR) /* 形参T无用 */{ /* 初始条件二叉树T存在p指向T中某个结点LR为0或1 *//* 操作结果根据LR为0或1刪除T中p所指结点的左或右子树 */if(p) /* p不空 */{if(LR0) /* 刪除左子树 */ClearBiTree(p-lchild);else /* 刪除右子树 */ClearBiTree(p-rchild);return OK;}return ERROR; /* p空 */}void PreOrderTraverse(BiPTree T,void(*Visit)(BiPTree)){ /* 先序递归遍历二叉树T */if(T){Visit(T); /* 先访问根结点 */PreOrderTraverse(T-lchild,Visit); /* 再先序遍历左子树 */PreOrderTraverse(T-rchild,Visit); /* 最后先序遍历右子树 */}}void InOrderTraverse(BiPTree T,void(*Visit)(BiPTree)){ /* 中序递归遍历二叉树T */if(T){InOrderTraverse(T-lchild,Visit); /* 中序遍历左子树 */Visit(T); /* 再访问根结点 */InOrderTraverse(T-rchild,Visit); /* 最后中序遍历右子树 */}}void PostOrderTraverse(BiPTree T,void(*Visit)(BiPTree)){ /* 后序递归遍历二叉树T */if(T){PostOrderTraverse(T-lchild,Visit); /* 后序遍历左子树 */PostOrderTraverse(T-rchild,Visit); /* 后序遍历右子树 */Visit(T); /* 最后访问根结点 */}}void LevelOrderTraverse(BiPTree T,void(*Visit)(BiPTree)){ /* 层序遍历二叉树T(利用队列) */LinkQueue q;QElemType a;if(T){InitQueue(q);EnQueue(q,T);while(!QueueEmpty(q)){DeQueue(q,a);Visit(a);if(a-lchild!NULL)EnQueue(q,a-lchild);if(a-rchild!NULL)EnQueue(q,a-rchild);}}} Reference: [1] wikipedia(二叉树)http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
