树与二叉树的基本知识（树与二叉树基本操作）

def: 树是n个结点的有限集合

非空树应该满足一下几点

1)有且只有一个特定的称为根的结点.

2)当n>1,其余结点可分为m个互不相交的有限集合

树的定义是递归的

树适合表示具有层次结构的数据

树的性质

已经调整过了,但还是歪啦

二叉树

def: 是另外一种树形结构,特点是每个结点嘴都只有2棵子树,子树有左右之分,顺序不能颠倒

特殊形式(满二叉树 完全二叉树 二叉排序树 平衡二叉树)

性质:

二叉树遍历(算法模板片段)

void PreOrder(BiTree T)//先序遍历 { if (T != NULL); { visit(T); PreOrder(T->lchild); preOrder(T->rchild); } } void InOrder(BiTree T)//中序遍历 { if (T != NULL); { PreOrder(T->lchild); visit(T); PreOrder(T->rchild); } } void PostOrder(BiTree T)//后序遍历 { if (T != NULL); { PreOrder(T->lchild); PreOrder(T->rchild); visit(T); } } void LevelOrder(BiTree T)//层次遍历 { InitQueue(Q);//初始化辅助队列 BiTree p; EnQueue(Q, T);//根节点入队 while (!IsEmpty(Q))//队列不空循环 { DnQueue(Q, p);//队头元素出队 visit(p); if (p->lchild = NULL) EnQueue(Q, p->lchild);//左子树不空,则入队 if (p->rchild = NULL) EnQueue(Q, p->rchild);//右子树不空,则入队 } }

树的遍历实例代码(简单的先,中,后遍历,所以没有注释)

#include<stdio.h> #include<stdlib.h> #include<string.h> struct BiTNode { int data; struct BiTNode *lchild, *rchild; }; typedef struct BiTNode BiTNode; typedef struct BiTNode BiTree; void preOrder(BiTNode *root) { if (root == NULL) { return; } printf("%d", root->data); preOrder(root->lchild); preOrder(root->rchild); } void inOrder(BiTNode *root) { if (root == NULL) { return; } inOrder(root->lchild); printf("%d", root->data); inOrder(root->rchild); } void postOrder(BiTNode *root) { if (root == NULL) { return; } postOrder(root->lchild); postOrder(root->rchild); printf("%d", root->data); } void main() { BiTNode t1, t2, t3, t4, t5; memset(&t1, 0, sizeof(BiTNode)); memset(&t2, 0, sizeof(BiTNode)); memset(&t3, 0, sizeof(BiTNode)); memset(&t4, 0, sizeof(BiTNode)); memset(&t5, 0, sizeof(BiTNode)); t1.data = 1; t2.data = 2; t3.data = 3; t4.data = 4; t5.data = 5; t1.lchild = &t2; t1.rchild = &t3; t2.lchild = &t4; t3.lchild = &t5; preOrder(&t1); inOrder(&t1); postOrder(&t1); printf("hello...\n"); system("pause"); return; }

计算叶子节点个数(核心代码)

把全局变量变成参数

void coutLeaf(BiTNode *T,int *sum)//指针做函数参数 { if (T != NULL) { if (T->lchild == NULL&& T->rchild == NULL) { (*sum) ;//指针所指向的内存空间的数据 1,不是指针 1.一定要加括号 } if (T->lchild) { coutLeaf(T->lchild,sum); } if (T->rchild) { coutLeaf(T->rchild,sum); } } }

求树的高度(也相当于是遍历的过程)

int Depth(BiTNode *T) { int deptleft = 0; int deptright = 0; int deptval = 0; if (T == NULL) { deptval = 0; return deptval ; } deptleft = Depth(T->lchild); deptright = Depth(T->rchild); deptval = 1 (deptleft > deptright) ? deptleft : deptright; return deptval; }

树的拷贝

BiTNode *CopyTree(BiTNode*T)//拷贝 { BiTNode *newNode = NULL; BiTNode *newLp = NULL; BiTNode *newRp = NULL; if (T == NULL) { return NULL; } if (T->lchild != NULL) { newLp = CopyTree(T->lchild); } else { newLp = NULL; } if (T->rchild != NULL) { newRp = CopyTree(T->rchild); } else { newRp = NULL; } newNode = (BiTNode*)malloc(sizeof(BiTNode)); if (newNode == NULL) { return NULL; } newNode->lchild = newLp; newNode->rchild = newRp; newNode->data = T->data; return NULL; }

二个辅助指针变量挖字符串(这个是为了二叉树线索化的预备知识)

int spitString(const char *buf1, const char c, char buf[18][30], int *nycount) { char *p = NULL; int count = 0; char *pTmp = NULL; int tmpcount = 0; char buf2[1024]; pTmp = buf1; p = buf1; do { p = strchr(p, c); if (p != NULL) { tmpcount - p = pTmp; memcpy(buf[count], pTmp, tmpcount);//行成差值,然后归并 buf[count][tmpcount] = '\0'; printf("%s\n", buf2); pTmp = p = p 1; count ; } else { break; } } while (*p != '\0'); } void main() { char *p = "aefasergazksdksakaddaweraerdfzdfzjfszg"; char c = ','; char buf[18][30]; int ncount; spitString(p, c, buf, &ncount); system("pause"); }

树的存储结构

双亲表示法(顺存)

#define MAX_TREE_SIZE 100 //最多结点数 typedef struct //树的结点定义 { ElemType data;//数据元素 int parent;//双亲位置域 }PTNode; typedef struct //树的类型定义 { PTNode nodes(MAX_TREE_SIZE);//双亲表示 int n; }PTree;

孩子表示法(顺 链)

孩子兄弟表示法(链)

树的遍历

先根遍历

后根遍历

树的应用

并查集(支持三种操作)

#define SIZE 100 int UFSets[SIZE]; void Initial(int S[]) { for (int i = 0; i<size; i )//每个自成单元素集合 S[i] = -1; } int Find(int S[], int x) { while (S[x] >= 0)//循环寻找x的根 x = S[x]; return x; } void Union(int S[], int Root1, int Root2)//求两个不相交子集合的名字 { S[Root2] = Root1; }

平衡二叉树(左<根<右)

失衡以后调整方法(简单介绍,不是重点)

LL(右单旋转)

RR(左单旋转)

RL(先右后左双旋转)

LR(先左后右双旋转)

只有左孩子才能右上旋(孩子变爹,爹变孩子)

只有右孩子才能左上旋(孩子变爹,爹变孩子)

红黑树以及其查找复杂

答：（1）红黑树来源于二叉搜索树，其在关联容器如map中应用广泛，主要优势在于其查找、删除、插入时间复杂度小，但其也有缺点，就是容易偏向一边而变成一个链表。

红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。也就是说，红黑树是在二叉

查找树基础上进一步实现的；

红黑树的五个性质：

性质1. 节点是红色或黑色；

性质2. 根节点是黑色；

性质3 每个叶节点（指树的末端的NIL指针节点或者空节点）是黑色的；

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)；

性质5. 从任一节点到其每个尾端NIL节点或者NULL节点的所有路径都包含相同数目的黑色节点。

（注：上述第3、5点性质中所说的NIL或者NULL结点，并不包含数据，只充当树的路径结束的标志，即此叶结点非常见的叶子结点）。

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查

找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)；

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加以上五个性质使得红黑树相对平衡，从而保证了

红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

（2）左旋右旋

红黑树插入或删除后，一般就会改变红黑树的特性，要恢复红黑树上述5个性质，一般都要那就要做2方面的工作：

1、部分结点颜色，重新着色

2、调整部分指针的指向，即左旋、右旋。

左旋右旋如图所示：

左旋，如图所示（左->右），以x->y之间的链为“支轴”进行，使y成为该新子树的根，x成为y的左孩子，而y的左孩子则成为x的右孩

子。算法很简单，旋转后各个结点从左往右，仍然都是从小到大。

左旋代码实现，分三步:

（1） 开始变化，y的左孩子成为x的右孩子；

（2） y成为x的父结点；

（3） x成为y的左孩子；

右旋类似，不再累述；

,