二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
相关术语
- 一棵深度为k，且有2^k-1 个结点的二叉树，称为满二叉树；
- 在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树；
- 所有节点都只有左子树，称为左斜树；
- 所有节点都只有右子树，称为右斜树；
性质
- 在二叉树的第i层上最多有2^i-1 个结点
- 深度为K的二叉树最多有2^k -1 个结点(K>=1)
- 对于任何一颗二叉树T,如果其终端结点数为n0,度为2的结 点数为n2,则n0 = n2 + 1;
- 具有n个结点的完全二叉树的深度为[log2n] + 1
顺序结构
-
初始化
BOOL InitBiTree(SqBiTree T){ for (int i = 0; i < MAXSIZE;i++) { T[i] = Nil; } return true; } -
创建二叉树
BOOL createBiTree(SqBiTree T) { int i = 0; while (i < 10) { T[i] = i+1; printf("%d ",T[i]); //结点不为空,且无双亲结点 if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) { printf("出现无双亲的非根结点%d\n",T[i]); exit(0); } i++; } //将空赋值给T的后面的结点 while (i < MAXSIZE) { T[i] = Nil; i++; } return true; } -
是否空树
//是否空树 BOOL isEmpty(SqBiTree T){ return T[0] == Nil; } -
获取深度
int BiTreeDepth(SqBiTree T){ int j = -1; int i; for (i = MAXSIZE - 1; i >= 0; i--) { if (T[i] != Nil) { break; } } do{ j++; }while(pow(2,j) <= i); return j; } -
获取E点的值
//获取E点的结点值 CElemType getValue(SqBiTree T,Position e){ return T[pow(2,e.level - 1) + e.order - 2]; } //插入值至位置e BOOL Assign(SqBiTree T,Position e ,CElemType value){ int i = pow(2,e.level - 1) + e.order - 2; if (T[(i + 1) / 2 - 1] == Nil ){ return false; } T[i] = value; return true; } -
插入结点
//插入值至位置e BOOL Assign(SqBiTree T,Position e ,CElemType value){ int i = pow(2,e.level - 1) + e.order - 2; if (T[(i + 1) / 2 - 1] == Nil ){ return false; } T[i] = value; return true; } -
左子结点
int leftChild(SqBiTree T,Position e){ return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 1 ]; } -
右子结点
int rightChild(SqBiTree T,Position e){ return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 2 ]; } -
双亲结点
int fatherNode(SqBiTree T,Position e){ if (e.level != 1) { return T[(int)(pow(2, e.level-1)+e.order-2) / 2 - 1]; } return -1; } -
前序遍历（中左右）
void PreTraverse(SqBiTree T,int e){ //打印结点数据 printf("%d ",T[e]); //先序遍历左子树 if (T[2 * e + 1] != Nil) { PreTraverse(T, 2*e+1); } //最后先序遍历右子树 if (T[2 * e + 2] != Nil) { PreTraverse(T, 2*e+2); } } BOOL PreOrderTraverse(SqBiTree T){ //树不为空 if (!isEmpty(T)) { PreTraverse(T, 0); } printf("\n"); return true; } -
中序遍历（左中右）
void InTraverse(SqBiTree T, int e){ /* 左子树不空 */ if (T[2*e+1] != Nil) InTraverse(T, 2*e+1); printf("%d ",T[e]); /* 右子树不空 */ if (T[2*e+2] != Nil) InTraverse(T, 2*e+2); } BOOL InOrderTraverse(SqBiTree T){ /* 树不空 */ if (!isEmpty(T)) { InTraverse(T, 0); } printf("\n"); return true; } -
后序遍历
void PostTraverse(SqBiTree T,int e) { /* 左子树不空 */ if(T[2*e+1]!=Nil) PostTraverse(T,2*e+1); /* 右子树不空 */ if(T[2*e+2]!=Nil) PostTraverse(T,2*e+2); printf("%d ",T[e]); } BOOL PostOrderTraverse(SqBiTree T) { if(!isEmpty(T)) /* 树不空 */ PostTraverse(T,0); printf("\n"); return true; }
链式存储
-
结构
typedef char CElemType; CElemType Nil=' '; /* 字符型以空格符为空 */ typedef struct BiTNode /* 结点结构 */ { CElemType data; /* 结点数据 */ struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; -
初始化
BOOL InitBiTree(BiTree *T) { *T=NULL; return true; } -
销毁二叉树
void DestroyBiTree(BiTree *T) { if(*T) { /* 有左孩子 */ if((*T)->lchild) DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */ /* 有右孩子 */ if((*T)->rchild) DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */ free(*T); /* 释放根结点 */ *T=NULL; /* 空指针赋0 */ } } -
创建二叉树,#表示空树
void CreateBiTree(BiTree *T){ CElemType ch; //获取字符 ch = str[indexs++]; //判断当前字符是否为'#' if (ch == '#') { *T = NULL; }else { //创建新的结点 *T = (BiTree)malloc(sizeof(BiTNode)); //是否创建成功 if (!*T) { exit(OVERFLOW); } /* 生成根结点 */ (*T)->data = ch; /* 构造左子树 */ CreateBiTree(&(*T)->lchild); /* 构造右子树 */ CreateBiTree(&(*T)->rchild); } } -
判断二叉树是否为空
BOOL BiTreeEmpty(BiTree T) { if(T) return false; else return true; } -
二叉树的深度
int BiTreeDepth(BiTree T){ int i,j; if(!T) return 0; //计算左孩子的深度 if(T->lchild) i=BiTreeDepth(T->lchild); else i=0; //计算右孩子的深度 if(T->rchild) j=BiTreeDepth(T->rchild); else j=0; //比较i和j return i>j?i+1:j+1; } -
根结点
CElemType getRoot(BiTree T){ if (BiTreeEmpty(T)) return Nil; return T->data; } -
获取结点的值
CElemType getValue(BiTree p){ return p->data; } -
给结点赋值
void Assign(BiTree p,CElemType value) { p->data=value; } -
前序遍历
void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */ PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */ PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */ }
-
中序遍历
void InOrderTraverse(BiTree T) { if(T==NULL) return ; InOrderTraverse(T->lchild); /* 中序遍历左子树 */ printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */ InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */ }
-
后序遍历
void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */ PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */ printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */ }
网友评论