在电脑科学中，二元树是每个节点最多有两个子树的树结构。通常子树被称作「左子树」（left subtree）和「右子树」（right subtree）。二元树常被用於实现二元搜寻树和二叉堆。 二元树的每个结点至多只有二棵子树(不存在度大於2的结点)，二元树的子树有左右之分，次序不能颠倒。二元树的第i层至多有个结点；深度为k的二元树至多有个结点；对任何一棵二元树T，如果其终端结点数为，度为2的结点数为，则。 树和二元树的三个主要差别： 1.树的结点个数至少为1，而二元树的结点个数可以为0； 2.树中结点的最大度数没有限制，而二元树结点的最大度数为2； 3.树的结点无左、右之分，而二元树的结点有左、右之分。 <完全二元树和满二元树> 1.满二元树：一棵深度为k，且有个节点成为满二元树 2.完全二元树：深度为k，有n个节点的二元树，若且唯若其每一个节点都与深度为k的满二元树中序号为1至n的节点对应时，称之为完全二元树 目录 [隐藏] 1 图论中的定义 2 二元树(Binary Tree)的类型 3 存储二元树的方法 3.1 顺序存储表示 3.1.1 储存结构 3.1.2 基本操作 3.2 二叉链表存储表示 3.2.1 存储结构 3.2.2 基本操作 3.3 三叉链表存储表示 3.3.1 存储结构 3.3.2 基本操作 4 访问二元树的方法 4.1 前(先)序、中序、後序遍历 4.2 深度优先遍历 4.3 广度优先遍历 5 将n叉树转换为二元树 5.1 存储结构与基本操作 5.1.1 树的二叉链表存储表示 5.1.2 树的二叉链表存储的基本操作 6 线索二元树 (threaded binary tree) 6.1 二叉线索存储表示 6.1.1 存储结构 6.1.2 基本操作 [编辑] 图论中的定义二元树在图论中是这样定义的：二元树是一个连通的无环图，并且每一个顶点的度不大於3。有根二元树还要满足根结点的度不大於2。有了根结点之後，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的讯息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。 [编辑] 二元树(Binary Tree)的类型二元树是一个有根树，并且每个节点最多有2个子节点。非空的二元树，若树叶总数为 n0，分支度为2的总数为 n2，则 n0 = n2 + 1。 一棵深度为k，且有个节点的二元树，称为满二元树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。在一棵二元树中，除最後一层外，若其余层都是满的，并且最後一层或者是满的，或者是在右边缺少连续若干节点，则此二元树为完全二元树（Complete Binary Tree）。具有n个节点的完全二元树的深度为。深度为k的完全二元树，至少有个节点，至多有个节点。 Complete Binary Tree Full Binary Tree 总节点k < k < k = 树高h h = h = [编辑] 存储二元树的方法在编程语言中能用多种方法来构造二元树。 [编辑] 顺序存储表示二元树可以用数组或线性表来存储，而且如果这是完全二元树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor((i-1)/2)找到（假设根节点的索引为0）。这种方法更有利於紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二元树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这갊O顺序存储结构的一大缺点。 [编辑] 储存结构 /* 二叉?的?序存?表示 */ #define MAX_TREE_SIZE 100 /* 二叉?的最大??? */ typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0??元存?根?? */ typedef struct { int level,order; /* ??的?，本?序?(按?二叉??算) */ }position; [编辑] 基本操作显示▼隐藏▲基於C/C++的实作演算法 /* 二叉?的?序存?的基本操作(23?)*/ #define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */ #define DestroyBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */ void InitBiTree(SqBiTree T) －－－（SqBiTree & T） { /* 构造空二叉树T。因为T是数组名，故不需要& */ int i; for(i=0;i<MAX_TREE_SIZE;i++) T[i]=Nil; /* 初值为空(Nil在主程中定义) */ } void CreateBiTree(SqBiTree T) { /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */ int i=0; #if CHAR /* 结点类型为字符 */ int l; char s[MAX_TREE_SIZE]; InitBiTree(T); /* 构造空二叉树T */ printf("请按层序输入结点的值(字符)，空格表示空结点，结点数≦%d:\n",MAX_TREE_SIZE); gets(s); /* 输入字符串 */ l=strlen(s); /* 求字符串的长度 */ for(;i<l;i++) /* 将字符串赋值给T */ T[i]=s[i]; #else /* 结点类型为整型 */ InitBiTree(T); /* 构造空二叉树T */ printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≦%d:\n",MAX_TREE_SIZE); while(1) { scanf("%d",&T[i]); if(T[i]==999) { T[i]=Nil; break; } i++; } #endif for(i=1;i<MAX_TREE_SIZE;i++) if(T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此非根结点(不空)无双亲 */ { printf("出现无双亲的非根结点"form"\n",T[i]); exit(ERROR); } } Status BiTreeEmpty(SqBiTree T) { /* 初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE */ if(T[0]==Nil) /* 根结点为空，则树空 */ return TRUE; else return FALSE; } int BiTreeDepth(SqBiTree T) { /* 初始条件：二叉树T存在。操作结果：返回T的深度 */ int i,j=-1; for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最後一个结点 */ if(T[i]!=Nil) break; i++; /* 为了便於计算 */ do j++; while(i>=pow(2,j)); /*pow是原型为double pow( double x, double y ),计算x的y次方,h = log₂k + 1来计算二叉树的深度*/ return j; } Status Root(SqBiTree T,TElemType *e) { /* 初始条件：二叉树T存在。操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR，e无定义 */ if(BiTreeEmpty(T)) /* T空 */ return ERROR; else { *e=T[0]; return OK; } } TElemType Value(SqBiTree T,position e) { /* 初始条件：二叉树T存在，e是T中某个结点(的位置) */ /* 操作结果：返回处於位置e(层,本层序号)的结点的值 */ return T[(int)pow(2,e.level-1)+e.order-2]; } Status Assign(SqBiTree T,position e,TElemType value) { /* 初始条件：二叉树T存在，e是T中某个结点(的位置) */ /* 操作结果：给处於位置e(层,本层序号)的结点赋新值value */ int i=(int)pow(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */ if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */ return ERROR; else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 给双亲赋空值但有叶子(不空) */ return ERROR; T[i]=value; return OK; } TElemType Parent(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：若e是T的非根结点，则返回它的双亲，否则返回”空” */ int i; if(T[0]==Nil) /* 空树 */ return Nil; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */ return T[(i+1)/2-1]; return Nil; /* 没找到e */ } TElemType LeftChild(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子,则返回"空" */ int i; if(T[0]==Nil) /* 空树 */ return Nil; for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */ return T[i*2+1]; return Nil; /* 没找到e */ } TElemType RightChild(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回"空" */ int i; if(T[0]==Nil) /* 空树 */ return Nil; for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */ return T[i*2+2]; return Nil; /* 没找到e */ } TElemType LeftSibling(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回”空” */ int i; if(T[0]==Nil) /* 空树 */ return Nil; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */ return T[i-1]; return Nil; /* 没找到e */ } TElemType RightSibling(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回”空” */ int i; if(T[0]==Nil) /* 空树 */ return Nil; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */ return T[i+1]; return Nil; /* 没找到e */ } void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */ { /* 把从q的j结点开始的子树移为从T的i结点开始的子树 */ if(q[2*j+1]!=Nil) /* q的左子树不空 */ Move(q,(2*j+1),T,(2*i+1)); /* 把q的j结点的左子树移为T的i结点的左子树 */ if(q[2*j+2]!=Nil) /* q的右子树不空 */ Move(q,(2*j+2),T,(2*i+2)); /* 把q的j结点的右子树移为T的i结点的右子树 */ T[i]=q[j]; /* 把q的j结点移为T的i结点 */ q[j]=Nil; /* 把q的j结点置空 */ } void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c) { /* 初始条件：二叉树T存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空 */ /* 操作结果: 根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或右子树则成为c的右子树 */ int j,k,i=0; for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++) /* 查找p的序号 */ if(T[j]==p) /* j为p的序号 */ break; k=2*j+1+LR; /* k为p的左或右孩子的序号 */ if(T[k]!=Nil) /* p原来的左或右孩子不空 */ Move(T,k,T,2*k+2); /* 把从T的k结点开始的子树移为从k结点的右子树开始的子树 */ Mov/* InOrderTraverse()调用 */ if(T[2*e+1]!=Nil) /* 左子树不空 */ InTraverse(T,2*e+1); VisitFunc(T[e]); if(T[2*e+2]!=Nil) /* 右子树不空 */ InTraverse(T,2*e+2); } void InOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { /* 初始条件：二叉树存在，Visit是对结点操作的应用函数 */ /* 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次 */ VisitFunc=Visit; if(!BiTreeEmpty(T)) /* 树不空 */ InTraverse(T,0); printf("\n"); } void PostTraverse(SqBiTree T,int e) { /* PostOrderTraverse()调用 */ if(T[2*e+1]!=Nil) /* 左子树不空 */ PostTraverse(T,2*e+1); if(T[2*e+2]!=Nil) /* 右子树不空 */ PostTraverse(T,2*e+2); VisitFunc(T[e]); } void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 */ /* 操作结果：後序遍历T，对每个结点调用函数Visit一次且仅一次 */ VisitFunc=Visit; if(!BiTreeEmpty(T)) /* 树不空 */ PostTraverse(T,0); printf("\n"); } void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { /* 层序遍历二叉树 */ int i=MAX_TREE_SIZE-1,j; while(T[i]==Nil) i--; /* 找到最後一个非空结点的序号 */ for(j=0;j<=i;j++) /* 从根结点起，按层序遍历二叉树 */ if(T[j]!=Nil) Visit(T[j]); /* 只遍历非空的结点 */ printf("\n"); } void Print(SqBiTree T) { /* 逐层、按本层序号输出二叉树 */ int j,k; position p; TElemType e; for(j=1;j<=BiTreeDepth(T);j++) { printf("第%d层: ",j); for(k=1;k<=pow(2,j-1);k++) { p.level=j; p.order=k; e=Value(T,p); if(e!=Nil) printf("%d:"form" ",k,e); } printf("\n"); } } [编辑] 二叉链表存储表示 基於连结串列的二元树逻辑结构示意在使用记录或记忆体位址指标的编程语言中，二元树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小於2，一些子结点指针可能为空值，或者为特殊的哨兵结点。 使用连结串列能避免顺序储存浪费空间的问题，演算法和结构相对简单，但使用二叉连结串列，由於缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点位址。 [编辑] 存储结构/* 二叉树的二叉链表存储表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; [编辑] 基本操作显示▼隐藏▲基於C/C++的实作演算法 /* 二叉树的二叉链表存储的基本操作(22个) */ #define ClearBiTree DestroyBiTree /* 清空二叉树和销毁二叉树的操作一样 */ #include"func6-3.c" /* 包括InitBiTree()、DestroyBiTree()、PreOrderTraverse()和InOrderTraverse()4函数 */ void CreateBiTree(BiTree *T) { /* 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，*/ /* 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。有改动 */ TElemType ch; scanf(form,&ch); if(ch==Nil) /* 空 */ *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); /* 生成根结点 */ if(!*T) exit(OVERFLOW); (*T)->data=ch; CreateBiTree(&(*T)->lchild); /* 构造左子树 */ CreateBiTree(&(*T)->rchild); /* 构造右子树 */ } } Status BiTreeEmpty(BiTree T) { /* 初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE */ if(T) return FALSE; else return TRUE; } int BiTreeDepth(BiTree T) { /* 初始条件：二叉树T存在。操作结果：返回T的深度 */ int i,j; if(T==NULL) /*如果T=NULL,???便于理解，?然也可以?成if（!T）*/; return 0; /* 空树深度为0 */ if(T->lchild) i=BiTreeDepth(T->lchild); /* i为左子树的深度 */ else i=0; if(T->rchild) j=BiTreeDepth(T->rchild); /* j为右子树的深度 */ else j=0; return i>j?i+1:j+1; /* T的深度为其左右子树的深度中的大者+1 */ } TElemType Root(BiTree T) { /* 初始条件：二叉树T存在。操作结果：返回T的根 */ if(BiTreeEmpty(T)) return Nil; else return T->data; } TElemType Value(BiTree p) { /* 初始条件：二叉树T存在，p指向T中某个结点。操作结果：返回p所指结点的值 */ return p->data; } void Assign(BiTree p,TElemType value) { /* 给p所指结点赋值为value */ p->data=value; } typedef BiTree QElemType; /* 设队列元素为二叉树的指针类型 */ #include"c3-2.h" /* 链队列 */ #include"bo3-2.c" /* 链队列的基本操作 */ TElemType Parent(BiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：若e是T的非根结点，则返回它的双亲，否则返回”空”*/ LinkQueue q; QElemType a; if(T) /* 非空树 */ { InitQueue(&q); /* 初始化队列 */ EnQueue(&q,T); /* 树根指针入队 */ while(!QueueEmpty(q)) /* 队不空 */ { DeQueue(&q,&a); /* 出队，队列元素赋给a */ if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e) /* 找到e(是其左或右孩子) */ return a->data; /* 返回e的双亲的值 */ else /* 没找到e，则入队其左右孩子指针(如果非空) */ { if(a->lchild) EnQueue(&q,a->lchild); if(a->rchild) EnQueue(&q,a->rchild); } } } return Nil; /* 树空或没找到e */ } BiTree Point(BiTree T,TElemType s) { /* 返回二叉树T中指向元素值为s的结点的指针。另加 */ LinkQueue q; QElemType a; if(T) /* 非空树 */ { InitQueue(&q); /* 初始化队列 */ EnQueue(&q,T); /* 根指针入队 */ while(!QueueEmpty(q)) /* 队不空 */ { DeQueue(&q,&a); /* 出队，队列元素赋给a */ if(a->data==s) return a; if(a->lchild) /* 有左孩子 */ EnQueue(&q,a->lchild); /* 入队左孩子 */ if(a->rchild) /* 有右孩子 */ EnQueue(&q,a->rchild); /* 入队右孩子 */ } } return NULL; } TElemType LeftChild(BiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子,则返回"空" */ BiTree a; if(T) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a->lchild) /* T中存在结点e且e存在左孩子 */ return a->lchild->data; /* 返回e的左孩子的值 */ } return Nil; /* 其余情况返回空 */ } TElemType RightChild(BiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回"空" */ BiTree a; if(T) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a->rchild) /* T中存在结点e且e存在右孩子 */ return a->rchild->data; /* 返回e的右孩子的值 */ } return Nil; /* 其余情况返回空 */ } TElemType LeftSibling(BiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回”空”*/ TElemType a; BiTree p; if(T) /* 非空树 */ { a=Parent(T,e); /* a为e的双亲 */ if(a!=Nil) /* 找到e的双亲 */ { p=Point(T,a); /* p为指向结点a的指针 */ if(p->lchild&&p->rchild&&p->rchild->data==e) /* p存在左右孩子且右孩子是e */ return p->lchild->data; /* 返回p的左孩子(e的左兄弟) */ } } return Nil; /* 其余情况返回空 */ } TElemType RightSibling(BiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */ /* 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回”空”*/ TElemType a; BiTree p; if(T) /* 非空树 */ { a=Parent(T,e); /* a为e的双亲 */ if(a!=Nil) /* 找到e的双亲 */ { p=Point(T,a); /* p为指向结点a的指针 */ if(p->lchild&&p->rchild&&p->lchild->data==e) /* p存在左右孩子且左孩子是e */ return p->rchild->data; /* 返回p的右孩子(e的右兄弟) */ } } return Nil; /* 其余情况返回空 */ } Status InsertChild(BiTree p,int LR,BiTree c) /* 形参T无用 */ { /* 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空 */ /* 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的 */ /* 原有左或右子树则成为c的右子树 */ if(p) /* p不空 */ { if(LR==0) { c->rchild=p->lchild; p->lchild=c; } else /* LR==1 */ { c->rchild=p->rchild; p->rchild=c; } return OK; } return ERROR; /* p空 */ } Status DeleteChild(BiTree p,int LR) /* 形参T无用 */ { /* 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1 */ /* 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树 */ if(p) /* p不空 */ { if(LR==0) /* 删除左子树 */ ClearBiTree(&p->lchild); else /* 删除右子树 */ ClearBiTree(&p->rchild); return OK; } return ERROR; /* p空 */ } typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */ #include"c3-1.h" /* 顺序栈 */ #include"bo3-1.c" /* 顺序栈的基本操作 */ void InOrderTraverse1(BiTree T,void(*Visit)(TElemType)) { /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3，有改动 */ /* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */ SqStack S; InitStack(&S); while(T||!StackEmpty(S)) { if(T) { /* 根指针进栈，遍历左子树 */ Push(&S,T); T=T->lchild; } else { /* 根指针退栈，访问根结点，遍历右子树 */ Pop(&S,&T); Visit(T->data); T=T->rchild; } } printf("\n"); } void InOrderTraverse2(BiTree T,void(*Visit)(TElemType)) { /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2，有改动 */ /* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */ SqStack S; BiTree p; 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); Visit(p->data); Push(&S,p->rchild); } } printf("\n"); } void PostOrderTraverse(BiTree T,void(*Visit)(TElemType)) { /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 */ /* 操作结果：後序递归遍历T，对每个结点调用函数Visit一次且仅一次 */ if(T) /* T不空 */ { PostOrderTraverse(T->lchild,Visit); /* 先後序遍历左子树 */ PostOrderTraverse(T->rchild,Visit); /* 再後序遍历右子树 */ Visit(T->data); /* 最後访问根结点 */ } } void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType)) { /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 */ /* 操作结果：层序递归遍历T(利用队列)，对每个结点调用函数Visit一次且仅一次 */ LinkQueue q; QElemType a; if(T) { InitQueue(&q); /* 初始化队列q */ EnQueue(&q,T); /* 根指针入队 */ while(!QueueEmpty(q)) /* 队列不空 */ { DeQueue(&q,&a); /* 出队元素(指针),赋给a */ Visit(a->data); /* 访问a所指结点 */ if(a->lchild!=NULL) /* a有左孩子 */ EnQueue(&q,a->lchild); /* 入队a的左孩子 */ if(a->rchild!=NULL) /* a有右孩子 */ EnQueue(&q,a->rchild); /* 入队a的右孩子 */ } printf("\n"); } } [编辑] 三叉链表存储表示改进於二叉连结串列，增加父节点的指引，能更好地实作节点间的存取，不过演算法相对复杂。 [编辑] 存储结构 /* 二叉树的三叉链表存储表示 */ typedef struct BiTPNode { TElemType data; struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */ }BiTPNode,*BiPTree; [编辑] 基本操作显示▼隐藏▲基於C/C++的实作演算法 /* 二叉树的三叉链表存储的基本操作(21个) */ #define ClearBiTree DestroyBiTree /* 清空二叉树和销毁二叉树的操作一样 */ void InitBiTree(BiPTree *T) { /* 操作结果：构造空二叉树T */ *T=NULL; } void DestroyBiTree(BiPTree *T) { /* 初始条件：二叉树T存在。操作结果：销毁二叉树T */ if(*T) /* 非空树 */ { if((*T)->lchild) /* 有左孩子 */ DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */ if((*T)->rchild) /* 有右孩子 */ DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */ free(*T); /* 释放根结点 */ *T=NULL; /* 空指针赋0 */ } } void CreateBiTree(BiPTree *T) { /* 按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，*/ /* 构造三叉链表表示的二叉树T */ TElemType ch; scanf(form,&ch); if(ch==Nil) /* 空 */ *T=NULL; else { *T=(BiPTree)malloc(sizeof(BiTPNode)); /* 动态生成根结点 */ if(!*T) exit(OVERFLOW); (*T)->data=ch; /* 给根结点赋值 */ (*T)->parent=NULL; /* 根结点无双亲 */ 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; else return TRUE; } int BiTreeDepth(BiPTree T) { /* 初始条件：二叉树T存在。操作结果：返回T的深度 */ int i,j; if(!T) return 0; /* 空树深度为0 */ if(T->lchild) i=BiTreeDepth(T->lchild); /* i为左子树的深度 */ else i=0; if(T->rchild) j=BiTreeDepth(T->rchild); /* j为右子树的深度 */ else j=0; return i>j?i+1:j+1; /* T的深度为其左右子树的深度中的大者+1 */ } TElemType Root(BiPTree T) { /* 初始条件：二叉树T存在。操作结果：返回T的根 */ if(T) return T->data; else return Nil; } TElemType Value(BiPTree p) { /* 初始条件：二叉树T存在，p指向T中某个结点。操作结果：返回p所指结点的值 */ return p->data; } void Assign(BiPTree p,TElemType value) { /* 给p所指结点赋值为value */ p->data=value; } typedef BiPTree QElemType; /* 设队列元素为二叉树的指针类型 */ #include"c3-2.h" /* 链队列 */ #include"bo3-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->data==e) 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) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a!=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) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a->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) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a->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) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a!=T&&a->parent->lchild&&a->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) /* 非空树 */ { a=Point(T,e); /* a是结点e的指针 */ if(a&&a!=T&&a->parent->rchild&&a->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(LR==0) { c->rchild=p->lchild; if(c->rchild) /* c有右孩子(p原有左孩子) */ c->rchild->parent=c; p->lchild=c; c->parent=p; } else /* LR==1 */ { c->rchild=p->rchild; if(c->rchild) /* c有右孩子(p原有右孩子) */ c->rchild->parent=c; p->rchild=c; c->parent=p; } 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(LR==0) /* 删除左子树 */ 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); } } } [编辑] 访问二元树的方法主条目：树的遍历 我们经常希望访问树中的每一个结点并且检视它的值。有很多常见的顺序来访问所有的结点，而且每一种都有有用的性质。 [编辑] 前(先)序、中序、後序遍历遍历二元树：L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二元树的顺序是DLR，中(根)序遍历二元树的顺序是LDR，後(根)序遍历二元树的顺序是LRD。还有按层遍历二元树。这些方法的时间复杂度都是O(n)，n为结点个数。 如果T2是由有序树T转换而来的二元树，那麽T中结点的前序就是T2中结点的前序，T中结点的後序就是T2中结点的中序。任何一棵二元树的叶结点在先序、中序和後序遍历中的相对次序不发改变。设n,m为一棵二元树上的两个结点，在中序遍历时，n在m前的条件是n在m的左方。前序序列和中序序列相同的二元树为空树或任一结点均无左孩子的非空二元树；中序序列和後序序列相同的二元树为空树或任一结点均无右孩子的非空二元树；前序序列和後序序列相同的二元树为空树或仅有一个结点的二元树。 假设我们有一个包含值的value和指向两个子结点的left和right的树结点结构。我们可以写出这样的过程： visit(node) print node.value if node.left != null then visit(node.left) if node.right != null then visit(node.right) 这样会用中序列印出树中的值。在中序，每个结点在访问它的子结点之前访问。类似地，如果列印语句在最後，每个结点在访问他的子节点之後访问，树中的值会用後序来列印。在这两种情况中，左子树中的值比右子树中得值先列印。 visit(node) if node.left != null then visit(node.left) print node.value if node.right != null then visit(node.right) 最後，上面的中序遍历，每个结点在访问左子树和右子树之间访问。这在遍历二叉搜寻树时很常用，因为它能用递增的顺序来遍历所有的值。 为什麽呢？如果n是二叉搜寻树的结点，那麽n的左子树的所有结点的值都比n的值要小，而且n的右子树的所有节点的值都比n的值要大。因此，如果我们顺序遍历左子树，然後访问n，然後顺序遍历右子树。我们就已经顺序访问了整个树。 在这个二元树中， 前序遍历的结果：2, 7, 2, 6, 5, 11, 5, 9, 4 後序遍历的结果：2, 5, 11, 6, 7, 4, 9, 5, 2 中序遍历的结果：2, 7, 5, 6, 11, 2, 5, 4, 9 以上的递归演算法使用与树的高度成比例的栈空间。如果我们在每个结点中存储指向父结点的指针，那样可以使用迭代演算法，只使用常数空间实现所有这些遍历。然而，指向父结点的指针占用更多的空间。这只在需要指向父节点的指针或栈空间有限时才使用。例如， 这是一个中序遍历的迭代演算法： visit(root) prev := null current := root next := null while current != null if prev == current.parent prev := current next := current.left if next == null or prev == current.left print current.value prev := current next := current.right if next == null or prev == current.right prev := current next := current.parent current := next 用二元树表示下述表达式：a+b*(c-d)-e/f 先序遍历的序列是：-+a*b-cd/ef 中序遍历的序列是：a+b*c-d-e/f 後序遍历的序列是：abcd-*+ef/- [编辑] 深度优先遍历在深度优先顺序中，我们希望从根结点访问最远的结点。和图的深度优先搜寻不同的是，不需记住访问过的每一个结点，因为树中不会有环。前序，中序和後序遍历都是深度优先遍历的特例。参见深度优先搜寻。 [编辑] 广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。参见广度优先搜寻。 二元树的广度优先遍历又称按层次遍历。演算法藉助队列实现。 [编辑] 将n叉树转换为二元树一般有序树和二元树之间有一一对映关系，能进行相互转换。 n叉树转换为二元树的方法：二元树中结点x的左子结点为n叉树中结点x的左子结点；二元树中结点x的右子结点为n叉树中结点x的第一个右边的同级结点y。 例如，在左边的树中，A有6个子结点{B,C,D,E,F,G}。它能被转换成右边的二元树。 将一棵树转换为二元树的方法： 1.在兄弟之间加一连线； 2.对每个结点，除了其左孩子外，去除其与其余孩子之间的联系； 3.以树的根结点为轴心，将整树顺时针转45度。 [编辑] 存储结构与基本操作树的二叉链表表示法（孩子兄弟表示法）是树和二元树转换的媒介。 [编辑] 树的二叉链表存储表示 /* 树的二叉链表(孩子—兄弟)存储表示 */ typedef struct CSNode { TElemType data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; [编辑] 树的二叉链表存储的基本操作显示▼隐藏▲基於C/C++的演算法实作 /* 树的二叉链表(孩子—兄弟)存储的基本操作(17个) */ #define ClearTree DestroyTree /* 二者操作相同 */ #include"func6-2.c" /* 包括PreOrderTraverse() */ void InitTree(CSTree *T) { /* 操作结果：构造空树T */ *T=NULL; } void DestroyTree(CSTree *T) { /* 初始条件：树T存在。操作结果：销毁树T */ if(*T) { if((*T)->firstchild) /* T有长子 */ DestroyTree(&(*T)->firstchild); /* 销毁T的长子为根结点的子树 */ if((*T)->nextsibling) /* T有下一个兄弟 */ DestroyTree(&(*T)->nextsibling); /* 销毁T的下一个兄弟为根结点的子树 */ free(*T); /* 释放根结点 */ *T=NULL; } } typedef CSTree QElemType; /* 定义队列元素类型 */ #include"c3-2.h" /* 定义LinkQueue类型(链队列) */ #include"bo3-2.c" /* LinkQueue类型的基本操作 */ void CreateTree(CSTree *T) { /* 构造树T */ char c[20]; /* 临时存放孩子结点(设不超过20个)的值 */ CSTree p,p1; LinkQueue q; int i,l; InitQueue(&q); printf("请输入根结点(字符型,空格为空): "); scanf("%c%*c",&c[0]); if(c[0]!=Nil) /* 非空树 */ { *T=(CSTree)malloc(sizeof(CSNode)); /* 建立根结点 */ (*T)->data=c[0]; (*T)->nextsibling=NULL; EnQueue(&q,*T); /* 入队根结点的指针 */ while(!QueueEmpty(q)) /* 队不空 */ { DeQueue(&q,&p); /* 出队一个结点的指针 */ printf("请按长幼顺序输入结点%c的所有孩子: ",p->data); gets(c); l=strlen(c); if(l>0) /* 有孩子 */ { p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); /* 建立长子结点 */ p1->data=c[0]; for(i=1;i<l;i++) { p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); /* 建立下一个兄弟结点 */ EnQueue(&q,p1); /* 入队上一个结点 */ p1=p1->nextsibling; p1->data=c[i]; } p1->nextsibling=NULL; EnQueue(&q,p1); /* 入队最後一个结点 */ } else p->firstchild=NULL; /* 长子指针为空 */ } } else *T=NULL; /* 空树 */ } Status TreeEmpty(CSTree T) { /* 初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则返回FALSE */ if(T) /* T不空 */ return FALSE; else return TRUE; } int TreeDepth(CSTree T) { /* 初始条件：树T存在。操作结果：返回T的深度 */ CSTree p; int depth,max=0; if(!T) /* 树空 */ return 0; if(!T->firstchild) /* 树无长子 */ return 1; for(p=T->firstchild;p;p=p->nextsibling) { /* 求子树深度的最大值 */ depth=TreeDepth(p); if(depth>max) max=depth; } return max+1; /* 树的深度=子树深度最大值+1 */ } TElemType Value(CSTree p) { /* 返回p所指结点的值 */ return p->data; } TElemType Root(CSTree T) { /* 初始条件：树T存在。操作结果：返回T的根 */ if(T) return Value(T); else return Nil; } CSTree Point(CSTree T,TElemType s) { /* 返回二叉链表(孩子—兄弟)树T中指向元素值为s的结点的指针。另加 */ LinkQueue q; QElemType a; if(T) /* 非空树 */ { InitQueue(&q); /* 初始化队列 */ EnQueue(&q,T); /* 根结点入队 */ while(!QueueEmpty(q)) /* 队不空 */ { DeQueue(&q,&a); /* 出队,队列元素赋给a */ if(a->data==s) return a; if(a->firstchild) /* 有长子 */ EnQueue(&q,a->firstchild); /* 入队长子 */ if(a->nextsibling) /* 有下一个兄弟 */ EnQueue(&q,a->nextsibling); /* 入队下一个兄弟 */ } } return NULL; } Status Assign(CSTree *T,TElemType cur_e,TElemType value) { /* 初始条件：树T存在，cur_e是树T中结点的值。操作结果：改cur_e为value */ CSTree p; if(*T) /* 非空树 */ { p=Point(*T,cur_e); /* p为cur_e的指针 */ if(p) /* 找到cur_e */ { p->data=value; /* 赋新值 */ return OK; } } return ERROR; /* 树空或没找到 */ } TElemType Parent(CSTree T,TElemType cur_e) { /* 初始条件：树T存在，cur_e是T中某个结点 */ /* 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为”空”*/ CSTree p,t; LinkQueue q; InitQueue(&q); if(T) /* 树非空 */ { if(Value(T)==cur_e) /* 根结点值为cur_e */ return Nil; EnQueue(&q,T); /* 根结点入队 */ while(!QueueEmpty(q)) { DeQueue(&q,&p); if(p->firstchild) /* p有长子 */ { if(p->firstchild->data==cur_e) /* 长子为cur_e */ return Value(p); /* 返回双亲 */ t=p; /* 双亲指针赋给t */ p=p->firstchild; /* p指向长子 */ EnQueue(&q,p); /* 入队长子 */ while(p->nextsibling) /* 有下一个兄弟 */ { p=p->nextsibling; /* p指向下一个兄弟 */ if(Value(p)==cur_e) /* 下一个兄弟为cur_e */ return Value(t); /* 返回双亲 */ EnQueue(&q,p); /* 入队下一个兄弟 */ } } } } return Nil; /* 树空或没找到cur_e */ } TElemType LeftChild(CSTree T,TElemType cur_e) { /* 初始条件：树T存在，cur_e是T中某个结点 */ /* 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回”空”*/ CSTree f; f=Point(T,cur_e); /* f指向结点cur_e */ if(f&&f->firstchild) /* 找到结点cur_e且结点cur_e有长子 */ return f->firstchild->data; else return Nil; } TElemType RightSibling(CSTree T,TElemType cur_e) { /* 初始条件：树T存在，cur_e是T中某个结点 */ /* 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回”空”*/ CSTree f; f=Point(T,cur_e); /* f指向结点cur_e */ if(f&&f->nextsibling) /* 找到结点cur_e且结点cur_e有右兄弟 */ return f->nextsibling->data; else return Nil; /* 树空 */ } Status InsertChild(CSTree *T,CSTree p,int i,CSTree c) { /* 初始条件：树T存在，p指向T中某个结点，1≦i≦p所指结点的度+1，非空树c与T不相交 */ /* 操作结果：插入c为T中p结点的第i棵子树 */ /* 因为p所指结点的地址不会改变，故p不需是引用类型 */ int j; if(*T) /* T不空 */ { if(i==1) /* 插入c为p的长子 */ { c->nextsibling=p->firstchild; /* p的原长子现是c的下一个兄弟(c本无兄弟) */ p->firstchild=c; } else /* 找插入点 */ { p=p->firstchild; /* 指向p的长子 */ j=2; while(p&&i>j) { p=p->nextsibling; j++; } if(j==i) /* 找到插入位置 */ { c->nextsibling=p->nextsibling; p->nextsibling=c; } else /* p原有孩子数小於i-1 */ return ERROR; } return OK; } else /* T空 */ return ERROR; } Status DeleteChild(CSTree *T,CSTree p,int i) { /* 初始条件：树T存在，p指向T中某个结点，1≦i≦p所指结点的度 */ /* 操作结果：删除T中p所指结点的第i棵子树 */ /* 因为p所指结点的地址不会改变，故p不需是引用类型 */ CSTree b; int j; if(*T) /* T不空 */ { if(i==1) /* 删除长子 */ { b=p->firstchild; p->firstchild=b->nextsibling; /* p的原次子现是长子 */ b->nextsibling=NULL; DestroyTree(&b); } else /* 删除非长子 */ { p=p->firstchild; /* p指向长子 */ j=2; while(p&&i>j) { p=p->nextsibling; j++; } if(j==i) /* 找到第i棵子树 */ { b=p->nextsibling; p->nextsibling=b->nextsibling; b->nextsibling=NULL; DestroyTree(&b); } else /* p原有孩子数小於i */ return ERROR; } return OK; } else return ERROR; } void PostOrderTraverse(CSTree T,void(*Visit)(TElemType)) { /* 後根遍历孩子—兄弟二叉链表结构的树T */ CSTree p; if(T) { if(T->firstchild) /* 有长子 */ { PostOrderTraverse(T->firstchild,Visit); /* 後根遍历长子子树 */ p=T->firstchild->nextsibling; /* p指向长子的下一个兄弟 */ while(p) { PostOrderTraverse(p,Visit); /* 後根遍历下一个兄弟子树 */ p=p->nextsibling; /* p指向再下一个兄弟 */ } } Visit(Value(T)); /* 最後访问根结点 */ } } void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType)) { /* 层序遍历孩子—兄弟二叉链表结构的树T */ CSTree p; LinkQueue q; InitQueue(&q); if(T) { Visit(Value(T)); /* 先访问根结点 */ EnQueue(&q,T); /* 入队根结点的指针 */ while(!QueueEmpty(q)) /* 队不空 */ { DeQueue(&q,&p); /* 出队一个结点的指针 */ if(p->firstchild) /* 有长子 */ { p=p->firstchild; Visit(Value(p)); /* 访问长子结点 */ EnQueue(&q,p); /* 入队长子结点的指针 */ while(p->nextsibling) /* 有下一个兄弟 */ { p=p->nextsibling; Visit(Value(p)); /* 访问下一个兄弟 */ EnQueue(&q,p); /* 入队兄弟结点的指针 */ } } } } } [编辑] 线索二元树 (threaded binary tree)线索二元树(保留遍历时结点在任一序列的前驱和後继的讯息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其後继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的後继。以这种结点结构构成的二叉链表作为二元树的存储结构，叫做线索链表，其中指向结点前驱和後继的指针叫做线索，加上线索的二元树称为线索二元树ꄊC对二元树以某种次序遍历使其变为线索二元树的过程叫做线索化。若对二元树进行中序遍历，则所得的线索二元树称为中序线索二元树，线索链表称为为中序线索链表。线索二元树是一种物理结构。 在中序线索树找结点後继的规律是：若其右标志为1，则右链为线索，指示其後继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其後继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最後访问的一个结点（左子树中最右下的结点）为其前驱。 在後序线索树中找到结点的後继分三种情况： 1.若结点是二元树的根，则其後继为空； 2.若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其後继即为双亲结点； 3.若结点是其双亲的左孩子，且其双亲有右子树，则其後继为双亲右子树上按後序遍历列出的第一个结点。 [编辑] 二叉线索存储表示[编辑] 存储结构二元树的二叉线索存储表示：在线索链表上添加一个头结点，并令其lchild域的指针指向二元树的根结点，其rchild域的指针指向中序遍历时访问的最後一个结点。令二元树中序序列中的第一个结点的lchild域指针和最後一个结点的rchild域的指针均指向头结点，这样就建立了一个双向线索链表 /* 二叉树的二叉线索存储表示 */ typedef enum{Link,Thread}PointerTag; /* Link(0)：指针，Thread(1)：线索 */ typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指针 */ PointerTag LTag,RTag; /* 左右标志 */ }BiThrNode,*BiThrTree; [编辑] 基本操作显示▼隐藏▲基於C/C++的演算法实作 /* 二叉树的二叉线索存储的基本操作 */ void CreateBiThrTree(BiThrTree *T) { /* 按先序输入线索二叉树中结点的值，构造线索二叉树T。0(整型)/空格(字符型)表示空结点 */ TElemType ch; scanf(form,&ch); if(ch==Nil) *T=NULL; else { *T=(BiThrTree)malloc(sizeof(BiThrNode)); /* 生成根结点(先序) */ if(!*T) exit(OVERFLOW); (*T)->data=ch; /* 给根结点赋植 */ CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */ if((*T)->lchild) /* 有左孩子 */ (*T)->LTag=Link; /* 给左标志赋值(指针) */ CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */ if((*T)->rchild) /* 有右孩子 */ (*T)->RTag=Link; /* 给右标志赋值(指针) */ } } BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */ void InThreading(BiThrTree p) { /* 通过中序遍历进行中序线索化，线索化之後pre指向最後一个结点。算法6.7 */ if(p) /* 线索二叉树不空 */ { InThreading(p->lchild); /* 递归左子树线索化 */ if(!p->lchild) /* 没有左孩子 */ { p->LTag=Thread; /* 左标志为线索(前驱) */ p->lchild=pre; /* 左孩子指针指向前驱 */ } d; Visit(p->data); /* 访问此结点 */ while(p->RTag==Thread&&p->rchild!=T) /* p->rchild是线索(後继)，且不是遍历的最後一个结点 */ { p=p->rchild; Visit(p->data); /* 访问後继结点 */ } p=p->rchild; /* 若p->rchild不是线索(是右孩子)，p指向右孩子，返回循环，*/ } /* 找这棵子树中序遍历的第1个结点 */ } void PreThreading(BiThrTree p) { /* PreOrderThreading()调用的递归函数 */ if(!pre->rchild) /* p的前驱没有右孩子 */ { pre->rchild=p; /* p前驱的後继指向p */ pre->RTag=Thread; /* pre的右孩子为线索 */ } if(!p->lchild) /* p没有左孩子 */ { p->LTag=Thread; /* p的左孩子为线索 */ p->lchild=pre; /* p的左孩子指向前驱 */ } pre=p; /* 移动前驱 */ if(p->LTag==Link) /* p有左孩子 */ PreThreading(p->lchild); /* 对p的左孩子递归调用preThreading() */ if(p->RTag==Link) /* p有右孩子 */ PreThreading(p->rchild); /* 对p的右孩子递归调用preThreading() */ } void PreOrderThreading(BiThrTree *Thrt,BiThrTree T) { /* 先序线索化二叉树T，头结点的右指针指向先序遍历的最後1个结点 */ *Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); if(!*Thrt) /* 生成头结点 */ exit(OVERFLOW); (*Thrt)->LTag=Link; /* 头结点的左指针为孩子 */ (*Thrt)->RTag=Thread; /* 头结点的右指针为线索 */ (*Thrt)->rchild=*Thrt; /* 头结点的右指针指向自身 */ if(!T) /* 空树 */ (*Thrt)->lchild=*Thrt; /* 头结点的左指针也指向自身 */ else { /* 非空树 */ (*Thrt)->lchild=T; /* 头结点的左指针指向根结点 */ pre=*Thrt; /* 前驱为头结点 */ PreThreading(T); /* 从头结点开始先序递归线索化 */ pre->rchild=*Thrt; /* 最後一个结点的後继指向头结点 */ pre->RTag=Thread; (*Thrt)->rchild=pre; /* 头结点的後继指向最後一个结点 */ } } void PreOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType)) { /* 先序遍历线索二叉树T(头结点)的非递归算法 */ BiThrTree p=T->lchild; /* p指向根结点 */ while(p!=T) /* p没指向头结点(遍历的最後1个结点的後继指向头结点) */ { Visit(p->data); /* 访问根结点 */ if(p->LTag==Link) /* p有左孩子 */ p=p->lchild; /* p指向左孩子(後继) */ else /* p无左孩子 */ p=p->rchild; /* p指向右孩子或後继 */ } } void PostThreading(BiThrTree p) { /* PostOrderThreading()调用的递归函数 */ if(p) /* p不空 */ { PostThreading(p->lchild); /* 对p的左孩子递归调用PostThreading() */ PostThreading(p->rchild); /* 对p的右孩子递归调用PostThreading() */ if(!p->lchild) /* p没有左孩子 */ { p->LTag=Thread; /* p的左孩子为线索 */ p->lchild=pre; /* p的左孩子指向前驱 */ } if(!pre->rchild) /* p的前驱没有右孩子 */ { pre->RTag=Thread; /* p前驱的右孩子为线索 */ pre->rchild=p; /* p前驱的後继指向p */ } pre=p; /* 移动前驱 */ } } void PostOrderThreading(BiThrTree *Thrt,BiThrTree T) { /* 後序递归线索化二叉树 */ *Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); if(!*Thrt) /* 生成头结点 */ exit(OVERFLOW); (*Thrt)->LTag=Link; /* 头结点的左指针为孩子 */ (*Thrt)->RTag=Thread; /* 头结点的右指针为线索 */ if(!T) /* 空树 */ (*Thrt)->lchild=(*Thrt)->rchild=*Thrt; /* 头结点的左右指针指向自身 */ else { /* 非空树 */ (*Thrt)->lchild=(*Thrt)->rchild=T; /* 头结点的左右指针指向根结点(最後一个结点) */ pre=*Thrt; /* 前驱为头结点 */ PostThreading(T); /* 从头结点开始後序递归线索化 */ if(pre->RTag!=Link) /* 最後一个结点没有右孩子 */ { pre->rchild=*Thrt; /* 最後一个结点的後继指向头结点 */ pre->RTag=Thread; } } } void DestroyBiTree(BiThrTree *T) { /* DestroyBiThrTree调用的递归函数，T指向根结点 */ if(*T) /* 非空树 */ { if((*T)->LTag==0) /* 有左孩子 */ DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */ if((*T)->RTag==0) /* 有右孩子 */ DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */ free(*T); /* 释放根结点 */ T=NULL; /* 空指针赋0 */ } } void DestroyBiThrTree(BiThrTree *Thrt) { /* 初始条件：线索二叉树Thrt存在。操作结果：销毁线索二叉树Thrt */ if(*Thrt) /* 头结点存在 */ { if((*Thrt)->lchild) /* 根结点存在 */ DestroyBiTree(&(*Thrt)->lchild); /* 递归销毁头结点lchild所指二叉树 */ free(*Thrt); /* 释放头结点 */ *Thrt=NULL; /* 线索二叉树Thrt指针赋0 */ } } 显示▼隐藏▲检 论 编电脑科学中的树 二元树 二元树 二元搜寻树 (BST) 笛卡尔树 Top tree T树 自平衡二元搜寻树 AA树 AVL树 红黑树 伸展树 树堆 节点大小平衡树 B树 B树 B+树 B*树 Bx树 UB树 2-3树 2-3-4树 (a,b)-树 Dancing tree H树 Trie 字尾树 基数树 空间划分树 四叉树 八叉树 k-d树 vp-树 R树 R*树 R+树 X树 M树 线段树 希尔伯特R树 优先R树 非二元树 Exponential tree Fusion tree 区间树 PQ tree Range tree SPQR tree Van Emde Boas tree 其他型别 堆 杂凑树 Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree 树状阵列 取自「http://zh.wikipedia.org/w/index.php?title=二叉?&oldid=24229733」 查看本页评分给本文评分 给本文评分 本页评分 这是什麽？目前平均评分 可信度 客观性 完整性 可读性 我非常了解与本主题相关的知识（可选） 我有与其有关学院/大学学位这是我专业的一部分个人对此有深厚的兴趣此处未列出我的知识的来源 我想帮助改善维基百科，请给我发送一封电子邮件（可选） 我们将向您发送确认电子邮件。基於反馈隐私政策，我们不会与任何人分享您的地址。提交评分 保存成功你的评分尚未提交你的评分已过期请重新评估本页并重新评分。 发生了错误。请稍後再试。 谢谢！您的评分已保存。你想要创建帐户吗？帐户将帮助您跟踪您所做的编辑，参与讨论，并成为社区的一部分。创建帐户或者登入以後再说 谢谢！您的评分已保存。您知道您可以编辑此页吗？编辑本页以後再说 3个分类：资料结构树结构图论1个隐藏分类：自2007年10月缺少来源的条目 -- plurk http://www.plurk.com/dasea2010 face book http://www.facebook.com/dasea.chien google+ https://plus.google.com/u/0/ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.130.189.48