-
树的定义
- 树是n个结点的有限集，它或为空树，或为非空树，对于非空树
- 有且仅有一个称之为根的结点
- 除根结点以外的其余结点可分为m个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。
- 树是n个结点的有限集，它或为空树，或为非空树，对于非空树
-
基本术语
- 根：即根结点（没有前驱）
- 叶子：终端结点（没有后继）
- 森林：指m棵不想交的树的集合
- 有序树：结点各子树从左到右有序，不能互换
- 无序树：结点各子树可互换位置
- 双亲：即上层的那个结点
- 孩子：即下层结点的子树的根
- 兄弟：同一双亲下的同层结点
- 堂兄弟：双亲位于同一层的结点
- 祖先：即从根到该结点所经分支的所有结点
- 子孙：该结点下层子树中的任一结点
- 结点：树的数据元素
- 结点的度：结点挂接的子树数
- 结点的层次：从根到该结点的层数
- 终端结点：度为0的结点，叶子
- 分支结点：度不为0的结点
- 树的度：所有结点度中的最大值
- 树的深度：指所有结点中最大的层数
-
二叉树是n个结点所构成的集合，它或为空树，或为非空树，对于非空树
- 有且仅有一个称为根的结点
- 除了根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树
-
二叉树的性质
- 满二叉树：一棵高度为h，且含有2^h-1个结点的二叉树
- 完全二叉树：层次遍历过去不会间断
- 非空二叉树叶子结点数等于n0 = n2+1
- 第k层至多有2^(k-1)个结点
- 高为h的二叉树至多2^h-1个结点
-
二叉树的顺序存储
-
二叉树的链式存储
-
typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
-
n个结点，有n+1个空链域
-
-
二叉树的遍历
-
//先序遍历 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->rchild); } }
-
//后序遍历 void PostOrder(BiTree T) { if(T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
-
//层次遍历 void levelOrder(BiTree T) { InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild!=NULL) EnQueue(Q,p->lchild); if(p->rchild!=NULL) EnQueue(Q,p->rchild); } }
-
//中序遍历（非递归） void InOrder2(BiTree T) { InitStack(S); BiTree p = T; while(p || !IsEmpty(S)) { if(p){ Push(S,p); p = p->lchild; } else{ Pop(S,p); visit(p); p = p->rchild; } } }
-
-
线索二叉树
-
如图
-
ltag
- 0:lchild指向左孩子
- 1:lchild指向结点的前驱
-
rtag
- 0:rchild指向右孩子
- 1:rchild指向后继
-
typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree;
-
void InThread(ThreadTree &p , ThreadTree &pre) { if(p != NULL) { InThread(p->lchild,pre); if(p->lchild == NULL) { p->lchild = pre; p->ltag = 1; } if(pre!=NULL && pre->rchild==NULL) { pre->rchild = p; pre->rtag = 1; } pre = p; InThread(p->rchild,pre); } }
-
//求中序遍历时中序序列的第一个结点 ThreadNode *Firstnode(ThreadNode *p) { while(p->ltag == 0) p = p->lchild; return p; }
-
//求中序线索中结点p在中序的后继结点 ThreadNode *Nextnode(ThreadNode *p) { if(p->rtag == 0) return Firstnode(p->rchild); else return p->rchild; }
-
-
树的存储结构
-
双亲表示法
-
#define MAX_TREE_SIZE 100 typedef struct{ ElemType data; int parent; }PTNode; //结点 typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; }PTree; //树
-
-
孩子表示法：每个结点的孩子都用单链表连在一起
- 如图
-
孩子兄弟表示法
-
包括结点值，指向结点第一个孩子结点的指针/指向结点下一个兄弟结点的指针
-
typedef struct CSNode{ ElemTpye data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;
-
-
-
树/森林/二叉树转换
- 树 - 二叉树
- 左孩子，右兄弟
- 森林 - 二叉树
- 1.把每棵树的根相连
- 2.把森林中每棵树转换成相应的二叉树
- 3.以第一课树的根为轴心顺时针45度
- 二叉树 - 森林
- 二叉树的根及其左子树为第一课树的二叉树
- 二叉树的根的右子树
- 右子树的右子树
- 树 - 二叉树
-
树和森林的遍历
- 先根遍历：森林第一棵的根 - 他的子树 - 先序其它森林的树
- 中序遍历：先中序遍历第一棵树的子树，在访问第一棵树的根结点/中序其它树
-
并查集
-
//并查集定义 #define SIZE 100 int UFSets[SIZE]; void Initial(int S[]) { for(int i = 0;i < size ; i++) { s[i] = -1; } }
-
//Find(找包含x的树的根) int Find(int S[],int x) { while(S[x] >= 0) x = S[x]; return x; }
-
//Union操作 void Union(int S[], int Root1,int Root2) { S[Root2] = Root1; }
-
-
二叉排序树
-
通过中序遍历可以得到从小到达的序列
-
//二叉排序查找（非递归） BSTNode *BST_Search(BiTree T, ElemType key,BSTNode &p) { p = NULL; while(T != NULL && key!=T->data) { p = T; if(key < T->data) T = T->lchild; else T=T->rchild; } return T; }
-
//二叉树的插入 int BST_Insert(BiTree &T,KetType k) { if(T == NULL) { T = (BiTree)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->rchild = NULL; return 1; } else if(k == T->key) return 0; else if( k < T->key) return BST_Insert(T->lchild,k); else return BST_Insert(T->rchild,k); }
-
//二叉排序树的构建 void Create_BST(BiTree &T, KeyType str[],int n) { T = NULL; int = 0; while(i < n) { BST_Insert(T,str[i]); i++; } }
-
-
二叉排序树的删除
- 右子树为空，用左子树补
- 左子树空，用右子女填补
- 左右子树均不空，在右子树上找中序第一个子女填补
-
平衡二叉树定义
-
LL
-
RR
-
LR
-
RL
-
哈夫曼树（最优二叉树）
- 构造过程
-
哈夫曼编码