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

逗爷 2023-07-18 23:47:56 747

二叉树的基本操作（树与二叉树基本操作）二叉树已经调整过了但还是歪啦树的定义是递归的树适合表示具有层次结构的数据树的性质

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

非空树应该满足一下几点

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

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

树的定义是递归的

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

树的性质

二叉树的基本操作（树与二叉树基本操作）(1)

已经调整过了但还是歪啦

二叉树

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

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

性质:

二叉树的基本操作（树与二叉树基本操作）(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;

孩子表示法(顺链)

二叉树的基本操作（树与二叉树基本操作）(3)

孩子兄弟表示法(链)

二叉树的基本操作（树与二叉树基本操作）(4)

树的遍历

先根遍历

二叉树的基本操作（树与二叉树基本操作）(5)

后根遍历

二叉树的基本操作（树与二叉树基本操作）(6)

树的应用

并查集(支持三种操作)

#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。也就是说，红黑树是在二叉

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