精华内容
下载资源
问答
  • 首先的概念:1.是N个结点的有限集。N = 0称为空。在任意一个非空中:有且仅有一个特定的称为根的结点(唯一)。2.N>1时,其余节点可分为M个互不相交的有限集T1,T2...Tm,其中每一个集合本身又是一棵...

    首先树的概念:1.树是N个结点的有限集。N = 0称为空树。在任意一个非空树中:有且仅有一个特定的称为根的结点(唯一)。2.N>1时,其余节点可分为M个互不相交的有限集T1,T2...Tm,其中每一个集合本身又是一棵树,称为根的子树。注:树的定义具有递归性,即树中还有树。3.结点拥有的子树数称为该结点的度。度为0的结点称为叶结点或终端结点;度不为0的结点成为非终端结点或分支结点。除根节点外,分支结点也称为内部节点。树的度是树内各结点的度的最大值。

    而二叉树的概念是:二叉树是N个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根节点和两棵互不相交的子树组成,称为左子树和右子树。

    二叉树的每个结点最多有两棵子树,左子树和右子树是有顺序的,某结点只有一棵子树。

    所以说个人认为二叉树更适合计算机编译进行。

    下面是二叉树输出代码:

    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 20

    typedef char ElementType;
    typedef struct treenode
    {
        ElementType value;
        struct treenode* left;
        struct treenode* right;
    }*TreeNode;

    void init(TreeNode* t);//初始化树
    void create1(TreeNode* t);//非递归的方式创建树
    void create2(TreeNode *t);//使用递归创建树
    void previsit(TreeNode t);//前序遍历树,先访问根节点再访问左子树再访问右子树
    void midvisit(TreeNode t);//中序遍历树
    void tailvisit(TreeNode t);//后序遍历树
    void levelvisit(TreeNode t);//按层遍历树
    int depth(TreeNode t);//返回树的深度
    void update(TreeNode t,ElementType old_value,ElementType new_value);//将树中所有的old_value值更新为new_value
    void print(TreeNode t);//以广义表示法进行输出
    void display(TreeNode t,int format);//以目录表示法进行输出
    void clear(TreeNode* t);//清空树

    char *string = "A(B(D,E(G,H)),C(F( ,I), ))";//广义表示法
    char *str = "ABD##EA##H##CA#I###";//扩展二叉树

    int main()
    {
        TreeNode tree;
        init(&tree);
        create1(&tree);
        //create2(&tree);
        previsit(tree);
        printf("\n");
        midvisit(tree);
        printf("\n");
        tailvisit(tree);
        printf("\n");

        levelvisit(tree);
        printf("\n");

        printf("the depth of tree is : %d\n",depth(tree));

        //update(tree,'A','Z');
        //previsit(tree);
        //printf("\n");
        print(tree);
        printf("\n");

        display(tree,0);

        clear(&tree);
        display(tree,0);


        return 0;
    }

    void init(TreeNode* t)//初始化树
    {
        *t = NULL;
    }
    //char *string = "A(B(D,E(G,H)),C(F( ,I), ))";
    void create1(TreeNode* t)//非递归的方式创建树
    {
        int i = 0;
        int flag = 1;//建树的标志,1:建左子树,2:建右子树
        TreeNode s[MAX];//数组模拟栈
        int top = -1;//栈顶指针
        TreeNode p;
        while(*(string + i) != '\0')
        {
            switch(*(string + i))
            {
                case ' ':
                    break;
                case '(':
                    if(top == MAX-1)
                    
                    {
                        printf("the stcak is full\n");
                        exit(2);
                    }
                    top++;
                    s[top] = p;
                    flag = 1;
                    break;
                case ',':
                    flag = 2;
                    break;
                case ')':
                    if(-1 == top)
                    {
                        printf("the stack is empty\n");
                        exit(3);
                    }
                    top--;
                    break;
                default:
                    p = (TreeNode)malloc(sizeof(struct treenode));
                    if(NULL == p)
                    {
                        exit(1);
                    }
                    p->value = *(string + i);
                    p->left = NULL;
                    p->right = NULL;
                    if(NULL == *t)
                    {
                        *t = p;
                    }
                    else
                    {
                        if(flag == 1)
                        {
                            s[top]->left = p;
                        }
                        else
                        {
                            s[top]->right = p;
                        }
                    }
                    break;
            }
            i++;
        }
    }
    //char *str = "ABD##EG##H##CF#I###";
    void create2(TreeNode* t)//使用递归创建树
    {
        static int i = 0;
        char ch = *(str+i++);
        if(ch == '#')
        {
            *t = NULL;
        }
        else
        {
            *t = (TreeNode)malloc(sizeof(struct treenode));
            if(NULL == *t)
            {
                exit(1);
            }
            (*t)->value = ch;
            create2(&((*t)->left));
            create2(&((*t)->right));
        }
    }

    void previsit(TreeNode t)//前序遍历树,先访问根节点再访问左子树再访问右子树
    {
        if(t != NULL)
        {
            printf("%c ",t->value);
            previsit(t->left);
            previsit(t->right);
        }
    }

    void midvisit(TreeNode t)//中序遍历树
    {
        if(t != NULL)
        {
            midvisit(t->left);
            printf("%c ",t->value);
            midvisit(t->right);
        }
    }

    void tailvisit(TreeNode t)//后序遍历树
    {
        if(t != NULL)
        {
            tailvisit(t->left);
            tailvisit(t->right);
            printf("%c ",t->value);
        }
    }

    void levelvisit(TreeNode t)//按层遍历树
    {
        TreeNode array[MAX] = {0};//模拟队列
        int front = 0;
        int rear = 0;
        if(t != NULL)
        {
            array[rear] = t;
            rear = (rear+1) % MAX;
        }

        while(front != rear)
        {
            printf("%c ",array[front]->value);
            if(NULL != array[front]->left)
            {
                array[rear] = array[front]->left;
                rear = (rear+1) % MAX;
            }
            if(NULL != array[front]->right)
            {
                array[rear] = array[front]->right;
                rear = (rear+1) % MAX;
            }
            front = (front+1) % MAX;
        }
    }

    int depth(TreeNode t)//返回树的深度
    {
        if(t != NULL)
        {
            int leftdepth = depth(t->left);
            int rightdepth = depth(t->right);
            return (leftdepth>rightdepth?leftdepth:rightdepth)+1;
        }
        else
        {
            return 0;
        }
    }
    //将树中所有的old_value值更新为new_value
    void update(TreeNode t,ElementType old_value,ElementType new_value)
    {
        if(NULL != t)
        {
            if(t->value == old_value)
            {
                t->value = new_value;
            }
            update(t->left,old_value,new_value);
            update(t->right,old_value,new_value);
        }
    }

    void print(TreeNode t)//以广义表示法进行输出
    {
        if(NULL != t)
        {
            printf("%c",t->value);
            if(NULL != t->left || NULL != t->right)
            {
                printf("(");
                if(NULL == t->left)
                {
                    printf(" ");
                }
                else
                {
                    print(t->left);
                }
                printf(",");
                if(NULL == t->right)
                {
                    printf(" ");
                }
                else
                {
                    print(t->right);
                }
                printf(")");
            }
        }
    }

    void display(TreeNode t,int format)//以目录表示法进行输出,formate为空格的个数
    {
        int i;
        if(NULL != t)
        {
            for(i = 0;i < format;i++)
            {
                printf(" ");
            }
            printf("%c\n",t->value);
            display(t->left,format+1);
            display(t->right,format+1);
        }
    }

    void clear(TreeNode* t)//清空树
    {
        if(NULL != *t)//必须以后序遍历的方式清除树
        {
            clear(&((*t)->left));
            clear(&((*t)->right));
            free(*t);
            *t = NULL;
        }
    }

     

    展开全文
  • 二叉树

    千次阅读 2020-06-26 15:55:41
    二叉树的基本概念

    树的定义和基本术语

    树(Tree) 是 n (n >= 0)个结点的有限集。

    在任意一颗非空树中:

    ​ 1. 有且仅有一个 根(root) 结点

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(SubTree)


    树的 结点 包含一个数据元素及或干个指向子树的分支。

    根结点:非空树中无前驱结点的结点。

    结点的度:结点拥有的子树数。

    度为 0 的结点称为 叶子(Leaf)或 终端结点

    结点的子树的根称为该结点的 孩子,该结点称为孩子的 双亲

    树的度:树内各结点的度的最大值。

    树的深度:树中结点的最大层次。

    树的基本概念和术语

    有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。

    无序树:树中结点的各子树无次序。

    森林:是 m(m >= 0)棵互不相交的树的集合。

    • 把根结点删除,树就变成了森林。
    • 一棵树可以看成是一个特殊的森林。
    • 给森林中的各子树加上一个双亲结点,森林就变成了树。

    树 一定是 森林

    森林 不一定是 树


    二叉树的定义

    二叉树(Binary Tree)是 n (n >= 0)个结点的有限集,它或者是空集 (n= 0),或者由一个根结点两棵互不相交 的分别称作这个根的 左子树右子树 的二叉树组成。

    特点

    1. 每个结点最多有俩孩子(二叉树中不存在度大于 2 的结点)。
    2. 子树有左右之分,其次序不能颠倒。
    3. 二叉树可以是空集合,根可以有空的左子树或空的右子树。

    注:虽然二叉树与树概念不同,但有关树的基本术语对二叉树都适用。


    二叉树的性质

    性质1:在二叉树的第 i 层上 至多 2 i − 1 2^{i-1} 2i1 个结点( i > = 1 i >= 1 i>=1)。

    性质2:深度为 k 的二叉树 至多 2 k − 1 2^k-1 2k1 个结点( k > = 1 k >= 1 k>=1)。

    性质3:对任何一颗二叉树 T,如果其叶子树为 n 0 n_0 n0,度为 2 的结点数为 n 2 n_2 n2,则 n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1

    小扩展

    • 在二叉树的第 i 层上 至少 有 1 个结点( i > = 1 i >= 1 i>=1)。
    • 深度为 k 的二叉树 至少 有 k 个结点( k > = 1 k >= 1 k>=1)。

    满二叉树:一棵深度为 k 且有 2 k − 1 2^k - 1 2k1 个结点的二叉树称为 满二叉树

    • 满二叉树在同样深度的二叉树中 结点 个数最多。
    • 满二叉树在同样深度的二叉树中 叶子结点 个数最多。

    完全二叉树:深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的 满二叉树中编号 为1 ~ n的结点一一对应时, 称之为完全二叉树。

    满二叉树 一定是 完全二叉树

    完全二叉树 不一定是 满二叉树

    注:在满二叉树中,从最后一个结点开始,连续 去掉 任意 个结点,即是一棵完全二叉树。(一定是连续的去掉!!!


    性质4: 具有 n 个结点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ + 1 \lfloor{log2^n}\rfloor + 1 log2n+1

    性质5:如果对一棵有 n 个结点的 完全二叉树(深度为 ⌊ l o g 2 n ⌋ + 1 \lfloor{log2^n}\rfloor + 1 log2n+1的结点按层序编号(从第1层到第 ⌊ l o g 2 n ⌋ + 1 \lfloor{log2^n}\rfloor + 1 log2n+1 层,每层从左到右),则对任一结点 i(1 <= i <= n),有:

    1. 如果 i = 1,则结点 i 是二叉树的根,无双亲;如果 i >1,则其 双亲是结点 ⌊ i / 2 ⌋ \lfloor{i/2}\rfloor i/2

    2. 如果 2i > n,则结点 i 为叶子结点,无左孩子;否则,其 左孩子是结点 2i

    3. 如果 2i + 1 > n,则结点 i 无右孩子;否则,其右孩子是结点 2i + 1

    性质4:表明了完全二叉树 结点数n 与完全二叉树 深度k 之间的关系 。

    性质5:表明了完全二叉树中 双亲结点编号孩子结点编号 之间的关系。


    线索二叉树

    利用二叉链表中的空指针域:

    • 如果某个结点的 左孩子为空,则将空的左孩子指针域改为 指向其前驱
    • 如果某结点的 右孩子为空,则将空的右孩子指针域改为 指向其后继
    • 这种改变指向的指针称为 "线索”
    • 加上了线索的二叉树称为 线索二叉树(Threaded Binary Tree)
    • 对二叉树按某种遍历次序使其变为线索二叉树的过程叫 线索化

    森林与二叉树的转换

    树变二叉树:兄弟相连留长子

    二叉树变树:左孩右右连双亲,去掉原来右孩线

    森林变二叉树:树变二叉跟相连

    二叉树变森林:去掉全部右孩线,孤立二叉再还原


    哈夫曼树的基本概念

    路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

    结点的路径长度:两个结点间路径上的 分支数

    树的路径长度:从 树根 到每个结点的 路径长度之和。记住:TL

    结点数目相同的二叉树中,完全二叉树是路径长度最短的二叉树。


    权(weight):将树中结点赋给一个有着某种含义的数值,则这个数值称为该 结点的权

    结点的带权路径长度:从 根结点 到该结点之间的 路径长度 与该结点的 乘积

    树的带权路径长度:树中所有 叶子 结点的 带权路径长度之和

    哈夫曼树:最优树(带权路径长度(WPL)最短的树)。

    “带权路径长度最短”是在“度相同” 的树中比较而得的结果,因此有最优二叉树、最优三叉树之称等等

    哈夫曼树:最优二叉树(带权路径长度(WPL)最短的二叉树)。


    构造哈夫曼树口诀

    ​ 1. 构造森林全是根

    ​ 2. 选用两小造新树

    ​ 3. 删除两小添新人

    ​ 4. 重复 2、3 剩单根


    包含 n 棵树的森林要经过 n - 1次合并才能形成哈夫曼树,共产生 n - 1 个新结点。

    包含 n 个叶子结点的哈夫曼树中共有 2n - 1 个结点。

    哈夫曼树的结点的度为 0 或 2,没有度为 1 的结点。

    展开全文
  • 在学数据结构的时候基本没有自己实现过的代码,现在基本原理也丢的差不多了,打算陆续做个整理,毕竟温故而知新二叉树二叉树是每个节点最多有两个子树的结构。通常子树被称作 “左子树” 和 “右子”。比如...

    在学数据结构的时候基本没有自己实现过树的代码,现在基本把原理也丢的差不多了,打算陆续做个整理,毕竟温故而知新

    二叉树

    二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。

    比如数组:

    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}

    变为二叉树为:

    %E4%BA%8C%E5%8F%89%E6%A0%91-%E6%95%B0%E7%BB%84.png

    分析:

    1、首先要定义每一个结点,每一个结点包括自身值,左结点和右结点,实现get、set方法。

    public class Node {

    public int data; //自己本身值

    public Node left; //左结点

    public Node right; //右结点

    public Node() {

    }

    public Node(int data, Node left, Node right) {

    this.data = data;

    this.left = left;

    this.right = right;

    }

    public int getData() {

    return data;

    }

    public void setData(int data) {

    this.data = data;

    }

    public Node getLeft() {

    return left;

    }

    public void setLeft(Node left) {

    this.left = left;

    }

    public Node getRight() {

    return right;

    }

    public void setRight(Node right) {

    this.right = right;

    }

    }

    2、创建二叉树

    public class Demo2 {

    public static List list = new ArrayList(); //用一个集合来存放每一个Node

    public void createTree(int[] array) {

    for (int i = 0; i < array.length; i++) {

    Node node = new Node(array[i], null, null); //创建结点,每一个结点的左结点和右结点为null

    list.add(node); // list中存着每一个结点

    }

    // 构建二叉树

    if (list.size() > 0) {

    for (int i = 0; i < array.length / 2 - 1; i++) { // i表示的是根节点的索引,从0开始

    if (list.get(2 * i + 1) != null) {

    // 左结点

    list.get(i).left = list.get(2 * i + 1);

    }

    if (list.get(2 * i + 2) != null) {

    // 右结点

    list.get(i).right = list.get(2 * i + 2);

    }

    }

    // 判断最后一个根结点:因为最后一个根结点可能没有右结点,所以单独拿出来处理

    int lastIndex = array.length / 2 - 1;

    // 左结点

    list.get(lastIndex).left = list.get(lastIndex * 2 + 1);

    // 右结点,如果数组的长度为奇数才有右结点

    if (array.length % 2 == 1) {

    list.get(lastIndex).right = list.get(lastIndex * 2 + 2);

    }

    }

    }

    // 遍历,先序遍历

    public static void print(Node node) {

    if (node != null) {

    System.out.print(node.data + " ");

    print(node.left);

    print(node.right);

    }

    }

    public static void main(String[] args) {

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    Demo2 demo = new Demo2();

    demo.createTree(array);

    print(list.get(0));

    }

    }

    结果为:

    1 2 4 8 9 5 3 6 7

    展开全文
  • 的后半部分,将介绍线索二叉树二叉树的转换及哈夫曼的应用很多,内容主要集中在讲解算法思想,代码量有所减少,另外会附很多图以便讲解。 ps:(一点废话),不咕咕了。这一篇比上篇会短小一点。 一...

    前言

    树的后半部分,将介绍线索二叉树,树和二叉树的转换及哈夫曼树。
    树的应用很多,内容主要集中在讲解算法思想,代码量有所减少,另外会附很多图以便讲解。
    ps:(一点废话),不咕咕了。这一篇比上篇会短小一点。

    一、线索二叉树

    1.引入部分

    (1)遍历二叉树是按某种规则将非线性结构的二叉树结点线性化
    (2)遍历二叉树可得到结点的一个线性序列,在线性序列中,就存在结点的前驱和后继,但是在二叉链表上只能找到结点的左孩子、右孩子
    (3)二叉树结点中没有相应前驱和后继的信息。

    现在的问题是:能否通过结点的两个链域查找出任一结点的前驱和后继?
    结点的前驱和后继只有在每次遍历时动态产生
    (4)回顾前面,我们使用了n个节点的二叉链表:
    有:2n个指针域
    使用:n-1个指针,除根以外,每个结点被一个指针指向
    空指针域数:2n-(n-1)=n+1

    2.线索二叉树

    (1)定义:利用n+1个空链域存放结点的前驱和后继信息
    (2)如图1

    ①先序序列:ABCDEFGHK
    ②线索:指向先序序列中的前驱和后继的指针
    则产生一个问题:如何判断一个指针究竟是指向孩子,还是指向前驱或后继

    (3)结点结构
    为解决以上问题,在二叉链表中增加Ltag和Rtag两个标志域
    此时,链表结点包含5个域:lchild,Ltag,data,Rtag,rchild
    ①考虑结点的左子树:
    若有,则左链域lchild指示其左孩子(Ltag=0)
    否则,令左链域lchild指示其前驱(Ltag=1)
    ②考虑结点的右子树:
    若有,则右链域rchild指示其右孩子(Rtag=0)
    否则,令右链域rchild指示其后继(Rtag=1)

    3.整体结构

    (1)增设一个头结点,令其lchild指向二叉树的根结点,Ltag=0,Rtag=1
    (2)并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继
    (3)最后用头指针指示该结点
    (4)若为空二叉树,只有一个头结点,其Ltag=0、Rtag=1,;lchild与rchild都指向头结点自身

    4.线索链表的类型描述

    //线索链表的类型描述
    //定义1个枚举类型PointerTag,其中Link==0,指针;Thread==1,线索 
    typedef enum
    {
    	Link,Thread
    }PointerTag;
    
    typedef struct BiThrNode
    {
    	TElemType data;
    	struct BiThrNode *lchild,*rchild;//左右孩子指针
    	PointerTag LTag,RTag;//左右标志 
    }BiThrNode,*BiThrTree;//*BiThrTree为指向BiThrNode的指针类型 
    

    (1)称以这种BiThrNode结点结构构成的二叉链表为二叉树的线索链表
    (2)其中指示前驱和后继的链域称为线索
    (3)加上线索的二叉树称为线索二叉树
    (4)线索化:对二叉树以某规则遍历使其变为线索二叉树的过程
    如:
    按中序遍历得到的线索二叉树称为中序线索二叉树
    按先序遍历得到的线索二叉树称为先序线索二叉树
    按后序遍历得到的线索二叉树称为后序线索二叉树

    5.中序线索链表的遍历算法(不需堆栈,非递归处理)

    (1)目的:为了能更快的二叉树进行再次遍历,由于在线索链表中添加了以前遍历中得到的前驱和后继的信息,从而可以简化遍历算法
    (2)考虑几个问题:
    ①中序遍历的第一个结点如何找到?(左子树上最左下的结点)
    ②在中序线索链表中如何找到结点的后继?若无右子树,则为后继线索所指结点,否则为对其右子树进行中序遍历时所访问的第一个结点
    (3)步骤:
    ①设置一个搜索指针p
    ② 先寻找中序遍历的首结点(即最左下角结点),当LTag=0时(表示有左孩子),p=p->lchild,
    直到LTag=1(无左孩子,已到最左下角),首先访问p->data
    ③接着进入该结点的右子树,检查RTag和p->rchild
    1)若该结点的RTag=1(表示有后继线索),则p=p->rchild,访问p->data;并重复1),直到后继结点的RTag=0
    2)当RTag=0时(表示有右孩子),则应从该结点的右孩子开始(p=p->rchild)查找左下角的子孙结点,即重复2
    主要规则:有后继找后继,无后继找右子树的最左子孙

    
    //中序线索二叉树遍历
    void InOrderTraverse_Thr (BiThrTreeT,void(*visit)(TElemType e))
    {
    	p = T->lchild;//p指向根结点
    	while (p!=T)//空树或遍历结束时,p==T 
    	{
    		while (p->LTag==Link)//第一个结点
    		{
    			p = p->lchild;
    	    }
    	    if (!visit(p->data))//访问其左子树为空的结点 
    	    	return ERROR;
    	    while (p->RTag==Thread && p->rchild!=T)//访问其后继结点 
    		{
    			p = p->rchild;
    			visit(p->data);
    		} 
    		p = p->rchild;//处理其右子树 
    	} 
    }
    

    二、树与二叉树的转换

    1.树转换成二叉树

    根据树的二叉链表特征,可以制定以下转换规则与步骤:
    (1)加线:在树兄弟结点之间依次加一连线
    附图1

    (2)抹线:对每个结点,除了其左孩子(第一个孩子)外,去掉其与其余孩子之间的关系
    附图2

    (3)旋转:以树的根结点为轴心,将整树顺时针旋转45°
    附图3

    转换之后的二叉树与其对应的二叉链表一样,根结点右子树一定为空
    原来树中兄弟关系转换成了二叉树中双亲与右孩子的关系

    2.二叉树转换成树

    (1)加线(恰好是上述中抹线的逆过程,恢复双亲与孩子的关系):若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,
    以及沿分支找到的所有右孩子,都与p的双亲用线连起来、
    附图4

    (2)抹线:抹掉原二叉树中双亲与右孩子之间的连线(他们在树中本为兄弟,无需连线)
    附图5

    (3)调整:将结点按层次排列,形成树结构
    附图6

    3.森林转换成二叉树

    (1)将各棵树分别转换成二叉树
    (2)将每棵二叉树的根结点用线相连
    附图7

    (3)以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构
    附图8

    可知,二叉树的根及其左子树来源于第一棵树,根的右孩子及其左子树来源于第二棵树,而根的右孩子的右孩子及其左子树来源于第三课树

    4.二叉树转换成森林

    (1)抹线:将二叉树中根结点与其右孩子的连线,以及沿右分支
    搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树
    附图9

    (2) 利用二叉树转换成树的方法分别将孤立的二叉树还原成树,从而形成森林

    5.树的遍历

    树的遍历要规定根与子树的访问次序,可分成先根遍历与后根遍历
    (1)先根遍历:(递归) (与二叉树的先序遍历一致)
    若树为空,则空操作
    否则,树非空时,按以下两步处理
    ①访问树的根结点
    ②依次先根遍历每颗子树
    附图10

    如图,序列为RADEBCFGHK
    (2)后根遍历:(递归) (与二叉树的中序遍历一致)
    若树为空,则空操作
    否则,树非空时,按以下两步处理
    ①依次后根遍历每颗子树
    ②访问树的根结点
    序列为DEABGHKFCR

    6.森林的遍历

    (1)先序遍历:(递归)(等价于对其二叉树进行先序遍历)
    若森林为空,则空操作
    否则,森林非空时,
    ①访问第一棵树的根结点
    ②先序遍历第一棵树中根结点的子树森林
    ③先序遍历余下的树构成的森林

    (2)中序遍历 :(递归)(等价于对其二叉树进行中序遍历)
    若森林为空,则空操作
    否则,森林非空时,
    ①中序遍历第一棵树中根结点的子树森林
    ②访问第一棵树的根结点
    ③中序遍历余下的树构成的森林

    7.树的遍历和二叉树遍历的对应关系

    在这里插入图片描述

    三、哈夫曼树(基于二叉树的应用)及其应用

    1.最优二叉树 (哈夫曼树)

    (1)路径长度:
    从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目叫做路径长度
    (2)树的路径长度(PL(T)):
    从树根到每一结点的路径长度之和
    举几个例子

    在这里插入图片描述

    问题:什么时候路径长度最小(大)
    分析如下:
    (3)PL(T)最小
    当n个结点的二叉树为完全二叉树时,结点i的层=[log2 i]+1(向下取整)
    树T的根到结点i的路径长度=结点i的层-1=[log2i](向下取整)
    故PL(T)=[log2 1]+[log2 2]+…+[log2 n](向下取整)=∑(1<=i<=n)[log2 i] (向下取整)

    (4)PL(T)最大
    当n个结点的二叉树为单枝树时,PL(T)=0+1+2+…+(n-1)=n(n-1)/2

    (5)树或二叉树T的带全路径长度:WPL(T)
    每个叶子的权与根到该叶子的路径长度的乘积之和
    WPL=∑(1<=k<=n) wk*lk
    其中:
    n——树T的叶子数目
    wk——叶子k的权
    lk——树T的根到叶子k的路径长度、
    如图2

    WPL(T1)=32+43+93+61=51

    (6)哈夫曼树定义:
    在具有n个相同叶子的各二叉树中,WPL最小的树
    如图3

    几点特征:
    ①完全二叉树并不一定是哈夫曼树(如第一棵)
    ②在哈夫曼树中,权值大的结点离根近
    ③哈夫曼树不唯一,但带权路径长度WPL一定相等
    ④不存在度为1 的结点

    2.哈夫曼算法

    (1)以权值分别为w1,w1,…,wn的n个结点,构成n棵二叉树T1,T2,…,Tn,并组成森林F={T1,T2,…,Tn}
    注意:每棵二叉树Ti仅有一个权值为wi的根结点
    (2)在F中选取两棵根结点最小的树作为左右子树构造一颗新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和
    即:根结点的权值=左右孩子权值之和
    叶结点的权值=wi
    (3)从F中删除这两棵二叉树,同时将新二叉树加入到F中
    (4)重复(2)(3)直到F中只含一棵二叉树为止(这棵树就是哈夫曼树)

    3.哈夫曼编码 / 最小冗余码

    之前学的ASCII码为定长码
    哈夫曼码(不定长)特点:能按字符的使用频率,使文本代码的总长度具有最小值
    举例说明哈夫曼编码与译码

    eg:给定有18个字符组成的文本:AADATARAEFRTAAFTER,求各字符的哈夫曼码
    (1)在文本中统计各字符的出现频率
    附图4

    (2)以上述频度为叶子结点的权值,构造哈夫曼树
    附图5

    (3)在哈夫曼树基础上,对每个字符进行编码,左分支标0,右分支标1
    附图6、图7
    在这里插入图片描述

    可见,哈夫曼码是不定长的码。实现编码时,顺序:对于给定的字符,从叶子结点找双亲,按逆序记录下01串

    另一特点:任一编码不是其他编码的前缀(如A为0,不是其他任意编码的前缀)
    这一特性使得对编码后的01串译码时,具有唯一性

    (4)译码
    顺序:通过输入的01串,从根沿01分支搜索到叶子,得到对应子串的原文字符
    附图8

    4.哈夫曼算法的实现(使用链式和顺序两种存储结构)(建立三叉链表结构)

    (1)哈夫曼树不存在度为1的结点,因此若哈夫曼树有n个叶子结点,则其共有2n-1个结点
    (2)哈夫曼编码时从叶子走到根,译码时又从根走到叶子,因此每个结点需要增开双亲指针分量

    //哈夫曼算法 
    typedef struct
    {
    	unsigned int weight;//权值分量(可放大取整) 
    	unsigned int parent,lchild,rchild;//双亲和孩子分量,指向双亲与左右孩子结点的位置指示域 
    }HTNode,*HuffmanTree;//HuffmanTree为动态数组名 
    typedef char**HuffmanTree;//动态数组存储HuffmanTree编码表(每个符合对应的01编码串)
    
    //先构造哈夫曼树HT(引用型参数),再求出n个字符的编码HC(引用型参数)
    void HuffmanCoding(HuffmanTree &HT,HuffmanTree &HT,HuffmanCode &HC,int *w,int n)//*w存放n个字符的权值,叶子个数n
    //具体函数未给出 
    

    总结

    这篇比较短小,附了很多图。
    简要介绍线索二叉树,一些操作类似于二叉树。
    关于树与二叉树的转换,有很多内容和方法,这里主要贴图,便于大家直观理解。
    哈夫曼树,及最优二叉树。这里举了一点例子,附上图片和代码。

    ps:代码非原创,如有错误,欢迎指正。
    下一篇会讲到图的一些定义和基本算法。

    展开全文
  • 调整角度变成二叉树 2.二叉树转化为 原来的例子 连接父亲与儿子 擦去多余的连接线 将旋转过来 3.二叉树森林转为二叉树 举例: 方法: 每一棵二叉树作为前一棵二叉树的右孩子插入 4.将含有多叉的...
  • 二叉树

    2019-10-13 11:11:27
    二叉树的定义,二叉树是一种形结构,其特点是每个结点至多只有两颗子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分 ,其次序不能任意颠倒。 与相似,二叉树也以递归的形式定义。二叉树是n个...
  • 这次主要是介绍的孩子兄弟表示法以及二叉树的转换。还是老规矩:程序在码云上可以下载。 地址:https://git.oschina.net/601345138/DataStructureCLanguage.git如果你对的基本概念还不清楚请看这个PPT,...
  • 二叉树、二叉查找、二叉搜索
  • 二叉树的转换

    2021-07-04 21:43:41
    二叉树如下图所示(兄弟相连留长子) 二叉树变成树的图示
  • 普通二叉树

    万次阅读 多人点赞 2018-07-13 21:03:30
    知识点系列之---普通二叉树
  • 二叉树、AVL

    2017-11-21 14:24:57
    二叉树、AVL   (注:本文转自http://www.cnblogs
  • 数据结构之二叉树逻辑结构树树的基本概念的基本术语的性质小结二叉树特殊二叉树二叉树完全二叉树二叉排序平衡二叉树二叉树的性质...中序遍历后序遍历层次遍历线索二叉树树、森林、二叉树的转换及遍历...
  • 二叉树

    2011-08-18 19:28:52
    其中,二叉树是我们学习中的重点中的重点——因为任何一颗通过一定的变换都能变成二叉树。每颗都只有一个根节点。n(n&gt;=2)棵可以形成森林。同样,森林可以转化成普通的,而普通的也可以转化成森林,...
  • 二叉树(有序转换为二叉树)讲解

    千次阅读 多人点赞 2019-03-11 21:40:39
    1006: 二叉树 Description 输入一颗普通有序,将它转换为对应的二叉链表存储,然后输出该二叉树的先序和后序遍历序列。 Input 包含多组测试数据。 每组测试数据第1行为的结点个数n(1≤n≤26)。 接...
  • 树到二叉树的转换 (1)在树中所有的兄弟结点之间加一条线 ...(1)先森林中的每棵树变成二叉树 (2)再将各二叉树的根节点视为兄弟从左到右连在一起,就形成了一棵二叉树 二叉树到树、森林的转换 ...
  • 将普通转为二叉树

    千次阅读 2016-05-12 21:10:57
    普通转化为二叉树! 普通转化为二叉树! 普通转化为二叉树! 重要的事情说三遍(雾)   最近在刷形dp的题,而形dp的某些特殊题目多依靠二叉树的结构写出状态转移方程,所以专门看看不得不说说的普通...
  • 二叉树总结

    千次阅读 2015-02-14 21:23:53
    1. 2.二叉树 3.二叉树的节点类及二叉树类 4.二叉树的遍历 5.线索二叉树 6.和森林 7.的应用
  • 文章目录概述一、的定义二、的基本术语三、为什么要研究二叉树四、二叉树的区别五、二叉树的定义六、二叉树的不同形态小结 概述 非线性结构元素的前驱和后继的个数不是为1的,这一节讲的形结构元素的前驱...
  • 是一种非线性结构。 ...二叉树的抽象类型定义 引入: 定义: 而子树本身又是一个,又可以看成是由一个根和其它元素所构成的集合组成的。所以很容易看出来,的定义是一个递...
  • ,二叉链表,二叉树的存储
  • 一、从二叉查找到平衡二叉树 一个二叉查找是由n个节点随机构成,所以,对于某些情况,二叉查找会退化成一个有n个节点的线性链.如下图:  b图为一个普通的二叉查找,a图中,如果我们的根节点选择不恰当如...
  • 二叉树的学习总结

    千次阅读 多人点赞 2019-03-15 20:10:34
    文章目录一般树二叉树一般二叉树二叉树完全二叉树二叉排序树二叉树的遍历红黑BB+ 经过Python的学习,顺便系统的学习了与相关的数据结构与算法,因此就记录一下吧,留待以后回忆参考。 一般 二叉树 ...
  • 文章目录将转换成二叉树二叉树转换成树将森林转换成二叉树二叉树转换成森林的遍历森林的遍历 由于二叉树都可以用二叉链表作存储结构,则以二叉链表作媒介可以导出二叉树之间的一个对应关系 将转换...
  • 红黑二叉树

    2017-08-30 00:34:16
    对一个平衡二叉树做几次增加删除节点的操作,它就变成非平衡的了,这不利于查找。所以每次增加删除节点后都要进行调整,调整的算法就是按红黑的规则“红节点的孩子不能是红节点”。对一个n个节点的红黑做一次...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,019
精华内容 15,207
关键字:

把树变成二叉树