资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

(六)数据结构--二叉树-创新互联

1、树

定义：树是n(n≥0)个节点的有限集，当n=0时，称为空数
非空树要满足：

超过10多年行业经验，技术领先，服务至上的经营模式，全靠网络和口碑获得客户，为自己降低成本，也就是为客户降低成本。到目前业务范围包括了：成都做网站、网站建设，成都网站推广，成都网站优化，整体网络托管，成都小程序开发，微信开发，手机APP定制开发，同时也可以让客户的网站和网络营销和我们一样获得订单和生意！
  • 有且仅有一个特定的称为根的结点。
  • 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，…，Tm,其中每个集合本事又是一颗树，并且称为根的子树。

特点：树作为一种逻辑结构，同时也是一种分层结构

  • 树的跟结点没有前驱，除根结点外的所有结点有且仅有一个前驱
  • 所有结点可以有零个或者多个后继

A是第一层，B/C/D是第二层，E/F/G/H/I/J是第三层，K/L/M第四层

2、二叉树

特点：每个树节点最多只有两颗子树(不存在度大于2的结点)，且二叉树的子树有左右之分，次序不能随意颠倒

  • 满二叉树每层结点个数:2^(n-1)；
  • 如果k结点去掉，就不是完全二叉树了
3、二叉树的存储

说明：图中的.表示该点没有内容，个人笔记习惯

顺序存储
一层一层逐一放置，如果该节点不存在用0补齐

12304050060

链式存储
数据结构：

typedef char BiElemType;
typedef struct BiTNode{BiElemType c;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode, *BiTree;

树中任何一个结点都是一个结构体，他的空间是通过malloc申请出来

4、二叉树层次建树

向二叉树中输入a,b,c,d,e,f,g,h,i,j十个字母
实现效果：如图

  • 需要使用的辅助队列
    步骤：
1.把`a`放进辅助队列，此时pcur始终指向要放子节点的结点上；
2.把`b`放进辅助队列，判断pcur所指的结点a的左孩子是不是为NULL，如果左孩子为NULL放在左边；
3.把`c`放进辅助队列，判断pcur所指的结点a的右孩子是不是为NULL，如果右孩子为NULL放在右边；
4.当a的左右孩子都不为NULL时，pcur后移一个
    calloc申请的空间大小是两个想乘，对申请的空间初始化，赋值为0
    代码实现：
function.h文件
#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H

#include#includetypedef char BiElemType;
// 二叉树结构体
typedef struct BiTNode{BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;
// 辅助队列结构体
typedef struct tag{BiTree p; //树的某一个结点的地址值
    struct tag *pnext;
} tag_t, *ptag_t;
#endif //TREE_FUNCTION_H
main.cpp文件
#include "function.h"

int main() {//1.用来指向新申请的树节点
    BiTree pnew;
    BiTree tree=NULL; //tree 指向树根用来代表树
    BiElemType c;
    // 2.辅助队列
    ptag_t  phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
    // abcdefghij
    while (scanf("%c",&c)){if (c=='\n'){break; //读到换行就结束
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));
        pnew->c=c;
        // 给队列结点申请空间
        list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
        list_pnew->p=pnew;
        // 判断是否是树的第一个结点
        if (tree==NULL) {tree = pnew; // tree指向树的根节点
            phead = list_pnew; // 第一个结点即是队列头，也是队列尾
            ptail = list_pnew;
            pcur = list_pnew; // 指向进入树的父亲元素
            continue;
        } else {// 先入队列
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            // 把结点放入树中
            if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
            } else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //当前左右结点都有了，pcur后移一个
                pcur=pcur->pnext;
            }
        }
    }
    return 0;
}
5、二叉树的前序中序后序遍历

每一个遍历都必须和自己的父亲挨着

前序遍历(preOrder)–深度优先遍历

先打印自身，再打印左子树，再打印右子树
前序遍历打印结果：abdhiejcfg

void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
        preOrder(Tree->lchild);
        preOrder(Tree->rchild);
    }
}
中序遍历(inOrder)

先打印左子树，再打印自身，再打印右子树
bacdbeac…
中序遍历打印结果：hdibjeafcg

void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
        printf("%c",Tree->c); //打印
        inOrder(Tree->rchild);
    }
}
后序遍历(PostOrder)

先打印左子树，再打印右子树，在打印自身
后序遍历打印结果：hidjebfgca

void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
        postOrder(Tree->rchild);
        printf("%c",Tree->c); //打印
    }
}
层序遍历(LevelOrder)–广度优先遍历

层序遍历打印结果：abcdefghij

// 层序遍历--广度优先遍历
void levelOrder(BiTree Tree){// 定义一个队列
    LinkQueue Q;
    // 初始化
    initQueue(Q);
    BiTree p;
    // 入队
    EnQueue(Q,Tree);
    while (!isEmpty(Q)){// 判断队列是否为空
        DeQueue(Q,p); // 出队当前结点并打印
        putchar(p->c);
        if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入队左孩子
        }
        if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入队右孩子
        }
    }
}
代码整理

结合上一节“(五)数据结构–队列”的代码实现。
结合辅助队列，
新建queue.cpp文件

#include "function.h"
// 队列初始化使用带头结点的链表来标识
void initQueue(LinkQueue &Q){Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //链表头和链表尾指向同一个结点
    Q.front->next=NULL; // 头结点的next指针为NULL
}
// 判断队列是否为空
bool isEmpty(LinkQueue Q){if (Q.front==Q.rear){return true;
    } else{return false;
    }
}
// 入队
void EnQueue(LinkQueue &Q, ElemType value){LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p->data=value;
    p->next=NULL; //要让next为NULL
    Q.rear->next=p; //尾指针的next指向p,从尾部入队;
    Q.rear=p; //rear指向新的尾部
}
// 出队
bool DeQueue(LinkQueue &Q, ElemType &value){if (isEmpty(Q)){return false;  //队列为空
    }
    LinkNode *q=Q.front->next; //拿到第一个结点，存入q
    value=q->data;
    Q.front->next=q->next;
    // 链表只剩余一个结点时，被删除后要改变rear
    if (Q.rear==q){Q.rear=Q.front;
    }
    free(q); // 断链
    return true;
}

修改function.h中的代码

#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H

#include#includetypedef char BiElemType;
// 二叉树结构体
typedef struct BiTNode{BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;
// 辅助队列结构体
typedef struct tag{BiTree p; //树的某一个结点的地址值
    struct tag *pnext;
} tag_t, *ptag_t;

+  typedef BiTree ElemType;
// 链表结点结构体
+  typedef struct LinkNode{+      ElemType data;
+      struct LinkNode *next;
+  }LinkNode;
+  typedef struct {+      LinkNode *front, *rear; // 链表头和链表尾
+  }LinkQueue;

+  void initQueue(LinkQueue &Q);
+  bool isEmpty(LinkQueue Q);
+  void EnQueue(LinkQueue &Q,ElemType value);
+  bool DeQueue(LinkQueue &Q,ElemType &value);

#endif //TREE_FUNCTION_H

main.cpp文件

#include "function.h"

// 前序遍历--深度优先遍历
void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
        preOrder(Tree->lchild);
        preOrder(Tree->rchild);
    }
}
// 中序遍历
void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
        printf("%c",Tree->c); //打印
        inOrder(Tree->rchild);
    }
}
// 后序遍历
void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
        postOrder(Tree->rchild);
        printf("%c",Tree->c); //打印
    }
}
// 层序遍历--广度优先遍历
void levelOrder(BiTree Tree){// 定义一个队列
    LinkQueue Q;
    // 初始化
    initQueue(Q);
    BiTree p;
    // 入队
    EnQueue(Q,Tree);
    while (!isEmpty(Q)){// 判断队列是否为空
        DeQueue(Q,p); // 出队当前结点并打印
        putchar(p->c);
        if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入队左孩子
        }
        if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入队右孩子
        }
    }
}
int main() {//1.用来指向新申请的树节点
    BiTree pnew;
    BiTree tree=NULL; //tree 指向树根用来代表树
    BiElemType c;
    // 2.辅助队列
    ptag_t  phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
    // abcdefghij
    while (scanf("%c",&c)){if (c=='\n'){break; //读到换行就结束
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));
        pnew->c=c;
        // 给队列结点申请空间
        list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
        list_pnew->p=pnew;
        // 判断是否是树的第一个结点
        if (tree==NULL) {tree = pnew; // tree指向树的根节点
            phead = list_pnew; // 第一个结点即是队列头，也是队列尾
            ptail = list_pnew;
            pcur = list_pnew; // 指向进入树的父亲元素
            continue;
        } else {// 先入队列
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            // 把结点放入树中
            if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
            } else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //当前左右结点都有了，pcur后移一个
                pcur=pcur->pnext;
            }
        }
    }
    printf("----------preOrder----------\n");
    preOrder(tree);
    printf("\n");
    printf("----------inOrder----------\n");
    inOrder(tree);
    printf("\n");
    printf("----------postOrder----------\n");
    postOrder(tree);
    printf("\n");
    printf("----------levelOrder----------\n");
    levelOrder(tree);
    printf("\n");
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


本文名称：(六)数据结构--二叉树-创新互联
网页网址：http://cdkjz.cn/article/djjcgi.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
企业网站设计微信公众号二次开发郫县门窗定制公司网站建设国泰民安消防蜀锦在线成都微信小程序开发成都微信小程序开发成都网络推广公司安卓开发

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图