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补齐

1	2	3	0	4	0	5	0	0	6	0

链式存储
数据结构：

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元起，快前往官网查看详情吧

文章标题：(六)数据结构--二叉树-创新互联
URL分享：http://kswsj.cn/article/djjcgi.html