锐客网

  1. 首页 > it技术 > >

数据结构与算法——树与二叉树

我们先来熟悉下树与二叉树的概念。

  • 树
    树是n个结点的集合，当n为0时，为空树。当n不等于0时，是非空树，此时树有且仅有一个根结点。
    树的结构如下

    数据结构与算法——树与二叉树
    文章图片
    一般树结构.png
【数据结构与算法——树与二叉树】树结构中高度、深度以及层数

数据结构与算法——树与二叉树
文章图片
image.png
  • 二叉树
    二叉树是一种特殊的树，二叉树中每个一个结点最多只有2个子结点，结构如下：
    数据结构与算法——树与二叉树
    文章图片
    二叉树.png
    一、特殊的二叉树
    1.满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
    如果一个二叉树的层数为K，且结点总数是(2^k) -1
    数据结构与算法——树与二叉树
    文章图片
    满二叉树.png
    2.完全二叉树:如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布。则为完全二叉树。
    数据结构与算法——树与二叉树
    文章图片
    非完全二叉树与完全二叉树.png
    二、二叉树的性质
    1.在二叉树的第i层上最多有2的i-1次方个结点。
    2.深度为K的二叉树最多有个2的K+1次方-1个结点。
    3.对于任何一颗二叉树，如果其树终点数为n，度为2的结点数为n2,则n = n2+1；
    4.具有n个结点的完全二叉树深度为log2n+1
    5.对具有n个结点的完全二叉树，如果按照从上至下，从左到右的顺序对二叉树的所有结点从1开始编码，则对于任意的序号为i的结点有：
    A.如果i>1,那么序号为i的结点双亲结点序号为i/2；
    B.如果i=1，那么序号为i的结点为根结点，无双亲；
    C.如果2i<=n，那么序号为i的结点的左孩子结点序号为2i；
    D.如果2i>n，那么序号为i的结点无左孩子；
    E.如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1；
    F.如果2i+1>n，那么序号为i的结点无右孩子。
    三、二叉树遍历
    ?叉树的遍(Traversing binary tree) 是指的从根结点出发,按照某种次序依次访问
    ?叉树中所有结点,使得每个结点被访问?次且仅被访问?次.
    二叉树的遍历方式
    1、前序遍历： 若?叉树为空,则空操作返回; 否则先访问根结点,然后前序遍历左?树,再前序遍历右?树。
    数据结构与算法——树与二叉树
    文章图片
    前序遍历.png
    2、中序遍历：若?叉树为空,则空操作返回; 否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左?树,然后是访问根结点,最后中序遍历右?树。
    数据结构与算法——树与二叉树
    文章图片
    中序遍历.png
    3、后续遍历:若?叉树为空,则空操作返回; 否则从左到右先叶?后结点的?式遍历左右?树,最后访问根结点。
    数据结构与算法——树与二叉树
    文章图片
    后续遍历.png
    4、层序遍历:若?叉树为空,则空操作返回; 否则从树的第?层,也是就是根结点开始访问,从
    上?下逐层遍历,在同?层中, 按从左到右的顺序对结点逐个访问。
    数据结构与算法——树与二叉树
    文章图片
    层序遍历.png
三、二叉树的顺序存储方式分析
假设分析上图”非完全二叉树与完全二叉树“，以顺序存储是什么样子的呢？
先看完全二叉树，存储为ABCDEF，而非完全二叉树则是ABCDE(null)G.如果是ABCDEG这样会分不清楚是二叉树结点的右树还是左树，先记录根结点然后左到右子结点，再然后是从左到右叶子结点。当一个结点左树为空时，只有个右树，要左树存储的空间为NULL。但是顺序存储有个缺点，例下图

数据结构与算法——树与二叉树
文章图片
image.png
这样就是浪费了大量的存储空间。
顺序存储方式代码
#include #include "stdlib.h"#include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int CElemType; /* 树结点的数据类型，目前暂定为整型 */ typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点*/ CElemType Nil = 0; /*设整型以0为空 或者以 INT_MAX(65535)*/ typedef struct{ int level; //结点层 int order; //本层的序号 }Position; #pragma mark - 二叉树的基本操作 Status visit(CElemType c){ printf("%d ",c); return OK; } Status InitBiTress(SqBiTree T){ for (int i = 0; i=0; i--) { if (T[i]!=Nil) { //记录最后结点的位置 break; } } do { j++; } while (pow(2, j) 结点层.表示第几层; Position.order -> 本层的序号(按照满二叉树给定序号规则) */ printf("%d\n",(int)pow(2, e.level-1)); printf("%d\n",e.order); return T[(int)pow(2, e.level)+e.order-1-1]; } //获取二叉树的根结点 Status Root(SqBiTree T,CElemType *e){ if (BiTreeEmpty(T)) { return ERROR; } *e = T[0]; return OK; } //给处于位置e的结点赋值 Status Assign(SqBiTree T,Position e,CElemType value){ //获取结点所处的位置 int place = (int)pow(2, e.level)+e.order-1-1; //叶子结点的双亲为空 if (value !=Nil && T[(place+1)/2-1]==Nil) { return ERROR; } //给双亲赋空值但是有叶子结点 if (value =https://www.it610.com/article/= Nil && (T[place*2+1] != Nil || T[place*2+2] != Nil)) { returnERROR; } T[place] = value; return OK; } //获取双亲 CElemType Parent(SqBiTree T,CElemType e){ if (T[0]==Nil) { //空树 return Nil; } for (int i = 0; i

四、二叉树的链式存储方式
#include "string.h" #include "stdio.h" #include "stdlib.h"#include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0/* 存储空间初始分配量 */ #define MAXSIZE 100 /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Status; #pragma mark--二叉树构造 int indexs = 1; typedef char String[24]; /*0号单元存放串的长度 */ String str; Status StrAssign(String T,char *chars) { int I; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1; i<=T[0]; I++) T[i]=*(chars+i-1); return OK; } }#pragma mark--二叉树基本操作typedef char CElemType; CElemType Nil=' '; /* 字符型以空格符为空 */ typedef struct BiTNode/* 结点结构 */ { CElemType data; /* 结点数据 */ struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; /*7.1 打印数据*/ Status visit(CElemType e) { printf("%c ",e); return OK; }/* 7.2 构造空二叉树T */ Status InitBiTree(BiTree *T) { *T=NULL; return OK; }/* 7.3 销毁二叉树 初始条件: 二叉树T存在。 操作结果: 销毁二叉树T */ void DestroyBiTree(BiTree *T) { if(*T) { /* 有左孩子 */ if((*T)->lchild) DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 *//* 有右孩子 */ if((*T)->rchild) DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */free(*T); /* 释放根结点 */*T=NULL; /* 空指针赋0 */ } } #define ClearBiTree DestroyBiTree/*7.4 创建二叉树 按前序输入二叉树中的结点值(字符),#表示空树; */ 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 = https://www.it610.com/article/ch; /* 构造左子树 */ CreateBiTree(&(*T)->lchild); /* 构造右子树 */ CreateBiTree(&(*T)->rchild); }}/* 7.5 二叉树T是否为空; 初始条件: 二叉树T存在 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */ Status BiTreeEmpty(BiTree T) { if(T) return FALSE; else return TRUE; }/* 7.6 二叉树T的深度 初始条件: 二叉树T存在 操作结果: 返回T的深度 */ 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; }/* 7.7 二叉树T的根 初始条件: 二叉树T存在 操作结果: 返回T的根 */ CElemType Root(BiTree T){ if (BiTreeEmpty(T)) return Nil; return T->data; }/* 7.8 返回p所指向的结点值; 初始条件: 二叉树T存在，p指向T中某个结点 操作结果: 返回p所指结点的值 */ CElemType Value(BiTree p){ return p->data; }/* 7.8 给p所指结点赋值为value; 初始条件: 二叉树T存在，p指向T中某个结点 操作结果: 给p所指结点赋值为value */ void Assign(BiTree p,CElemType value) { p->data=https://www.it610.com/article/value; }#pragma mark--二叉树遍历 /* 7.8前序递归遍历T 初始条件:二叉树T存在; 操作结果: 前序递归遍历T */void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */ PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */ PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */ }/* 7.9中序递归遍历T 初始条件:二叉树T存在; 操作结果: 中序递归遍历T */ void InOrderTraverse(BiTree T) { if(T==NULL) return ; InOrderTraverse(T->lchild); /* 中序遍历左子树 */ printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */ InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */ }/* 7.10后序递归遍历T 初始条件:二叉树T存在; 操作结果: 中序递归遍历T */ void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /* 先后序遍历左子树*/ PostOrderTraverse(T->rchild); /* 再后序遍历右子树*/ printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */ }int main(int argc, const char * argv[]) { // insert code here... printf("二叉树链式存储结构实现!\n"); int I; BiTree T; CElemType e1; InitBiTree(&T); StrAssign(str,"ABDH#K###E##CFI###G#J##"); CreateBiTree(&T); printf("二叉树是否为空%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T)); e1=Root(T); printf("二叉树的根为: %c\n",e1); printf("\n前序遍历二叉树:"); PreOrderTraverse(T); printf("\n中序遍历二叉树:"); InOrderTraverse(T); printf("\n后序遍历二叉树:"); PostOrderTraverse(T); printf("\n"); return 0; }

    推荐阅读


    上一篇：今天是国庆

    下一篇：Xcode11|Xcode11 AppDelegate结构变化 SceneDelegate分屏