二叉树基础操作总结-白红宇

二叉树基础操作总结

阅读量：3946 次

发布时间：2019-05-24

本文共 6646 字，大约阅读时间需要 22 分钟。

昨天的数据结构讲座，学长讲了二叉树这方面的知识，今天又复习了一下，赶紧记下来。

二叉树的定义

二叉树是n个结点的集合，可以为空，也可以由一个根结点和两棵互不相交的左，右子树组成。

二叉树的特点

1. 每个结点最多有两颗子树（是最多有）。

2. 左右子树有顺序，不能随意颠倒（哪怕其中那个结点只有一颗子树，也要区分是左子树还是右子树）。

现在让我们正式开始讲一下各种操作

先来看一张整体的效果图

数据结构

typedef struct node{
   	char data;	struct node *lchild,*rchild;}Tree;

1. 首先，我们需要一颗二叉树，所以最开始我们先来建立一个二叉树。

我们要先得到原二叉树的扩展二叉树（将原二叉树中每个结点的空指针引出一个虚结点，给其一确定值（如"#"）），然后我们就能做到一个遍历序列确定一颗二叉树了。

我们以前序建树为例，所以我们应该输入 ABD#F##E##C##。

void CreatBiTree(Tree **root){
   	char ch;	scanf("%c",&ch);	if(ch == '#')		*root = NULL;	else	{
   		*root = (Tree *)malloc(sizeof(Tree));		(*root)->data = ch;		CreatBiTree(&(*root)->lchild);		CreatBiTree(&(*root)->rchild);	}}

注：1. 建立二叉树也是利用递归，和递归遍历差距不大，只不过在原来打印结点的地方改成了生成结点，给结点赋值。

2. 中序，后序建树也可以，代码其实差不多，要提前知道其遍历树顺序就好。

2. 建好一颗树后，我们就来看一下遍历（递归 and 非递归）

先来说一下前序，中序，后序遍历。它们3个的递归遍历基本一样，核心就是3行代码，只不过调整一下顺序，递归比较简洁明了，但是效率却比较低（而且别人要是让你写一个二叉树的遍历，你上去直接递归感觉有点不够高级…），所以非递归的就来了，前，中，后序的非递归实现要借助栈（递归遍历也是系统调用栈来实现），可以自己来用c语言来实现一个栈，但c++有封装好的 stack，所以我就直接用了。

前序遍历

递归：

根 -> 左 -> 右

非递归：

从根结点开始，先判断是否为空，不为空就先访问（打印）该结点，然后入栈，接着遍历左子树；为空时让栈顶元素出栈，并以其为父结点访问其右子树，直到当前节点为空且栈为空时结束。

void PreOrderTra(Tree *root){
   	Tree *p = root;	if(p == NULL)		return;	printf("%c ",p->data);	PreOrderTra(p->lchild);	PreOrderTra(p->rchild);}//非递归void PreOrderTra_fdg(Tree *root){
       stack
   
     s;    Tree *p = root;    while(p || !s.empty())    {
           if(p)        {
               printf("%c ",p->data);            s.push(p);      //入栈            p = p->lchild;  //沿左子树        }        else        {
               p = s.top();    //取出            s.pop();        //出栈            p = p->rchild;  //向右        }    }}

中序遍历

递归：

左 -> 根 -> 右

非递归：

和前序遍历差不多，只不过访问节点的顺序不一样，访问节点的时机是从栈中弹出元素时访问，如果从栈中弹出元素，就意味着当前节点的父结点的左子树已经遍历完成，这时候再进行访问。

void InOrderTra(Tree *root){
       Tree *p = root;    if(p == NULL)        return;    InOrderTra(p->lchild);    printf("%c ",p->data);    InOrderTra(p->rchild);}//非递归void InOrderTra_fdg(Tree *root){
       stack
   
     s;    Tree *p = root;    while(p || !s.empty())    {
           if(p)        {
               s.push(p);      //入栈            p = p->lchild;        }        else        {
               p = s.top();    //取出            printf("%c ",p->data);            s.pop();        //出栈            p = p->rchild;        }    }}

后序遍历

递归：

左 -> 右 -> 根

非递归：

对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，或者都已被访问过了，就可以直接访问该结点。如果有孩子未访问，将P的右孩子和左孩子依次入栈（一定要是先右后左，因为访问的时候是从左孩子开始的）。定义两个指针，分别指向当前结点和之前访问过的结点，先将根结点入栈开始。

void PostOrderTra(Tree *root){
       Tree *p = root;    if(p == NULL)        return;    PostOrderTra(p->lchild);    PostOrderTra(p->rchild);    printf("%c ",p->data);}//非递归void PostOrderTra_fdg(Tree *root){
       stack
   
     s;    Tree *p,*q;    p = q = NULL;    s.push(root);    while(!s.empty())    {
           p = s.top();        if((p->lchild == NULL && p->rchild == NULL) || (q != NULL && (q == p->lchild || q == p->rchild)))        {
               printf("%c ",p->data);  //如果当前结点没有孩子或者孩子结点都已被访问过            s.pop();    //出栈            q = p;      //记录上一次访问的结点        }        else    //分别放入右左孩子        {
                  if(p->rchild != NULL)                s.push(p->rchild);            if(p->lchild != NULL)                s.push(p->lchild);        }    }}

ok，了解了前序，中序，后序的遍历之后，再让我们来看一下层序遍历。我写了两种，一种用的数组，一种是 queue（都一样，只不过是借用数组来实现一个队列的功能）。借助队列来实现，还是比较好理解的，先将其父结点入队，然后将其左右孩子依次入队，队列未空就一直按顺序访问即可。

//层序遍历-（数组）void LevelTra(Tree *root){
       Tree *t[20];    //指针数组，存放二叉树结构体指针    int in,out;    in = out = 0;    t[in++] = root; //先保存根结点    while(in > out)    {
           if(t[out])        {
               printf("%c ",t[out]->data);            t[in++] = t[out]->lchild;            t[in++] = t[out]->rchild;        }        out++;    }}//层序遍历-（队列）void LevelTra_dl(Tree *root){
       queue
   
     s;    Tree *p = NULL;    if(root)        s.push(root);           //根结点入队    while(!s.empty())    {
           p = s.front();        printf("%c ",p->data);                if(p->lchild != NULL)            s.push(p->lchild);        if(p->rchild != NULL)            s.push(p->rchild);        s.pop();    }}

3. 求一棵树的结点个数

注：3，4，5，6点都是递归实现的，有些相通的，理解了一个之后，看其它的会比较好理解。

用递归来实现，比较好理解，但是不是很好能想通（我开始是 printf 来的，感受每次递归时的变化）。结点如果为空返回 0，否则返回的是左右子树的结点和再 +1（要加上自己本身）。

int GetNodeNum(Tree *root){
       if(root == NULL)        return 0;    int lNum = GetNodeNum(root->lchild);    int rNum = GetNodeNum(root->rchild);    //printf("%d %d\n",lNum,rNum);    return lNum + rNum + 1;     }

4. 求一棵树的深度

因为自己本身也占一层，所以返回时 +1。

int GetTreeDepth(Tree *root){
       if(root == NULL)        return 0;    int lDepth = GetTreeDepth(root->lchild);    int rDepth = GetTreeDepth(root->rchild);    //printf("%d %d\n",lDepth,rDepth);    return lDepth > rDepth ? (lDepth + 1) : (rDepth + 1);}

5. 求一棵树的叶子结点数

叶子结点：没有孩子的结点。

int GetLeafNodeNum(Tree *root){
       if(root == NULL)        return 0;    if(root->lchild == NULL && root->rchild == NULL)        return 1;    int lNum = GetLeafNodeNum(root->lchild);    int rNum = GetLeafNodeNum(root->rchild);    return (lNum + rNum);}

6. 求一棵树某一层的结点数

k 为要访问的那一层。

int GetNodeNumLevel(Tree *root, int k){
       if(root == NULL || k < 1)        return 0;    if(k == 1)        return 1;    int lNum = GetNodeNumLevel(root->lchild,k - 1);    int rNum = GetNodeNumLevel(root->rchild,k - 1);    return (lNum + rNum);}

7. 再完成了各种操作之后，一定不能忘记的就是要销毁二叉树了

void DeleteTree(Tree *root){
       if(root == NULL)        return;    DeleteTree(root->lchild);    DeleteTree(root->rchild);    free(root);}

以上便是我今天所总结的一些有关二叉树的操作，因为自己也比较菜，所以若是有什么地方有错误，请大家指正！

最后贴上我的主函数

需要注意的就是最后要让指针指向 NULL。

int main(){
   	Tree *m_root = NULL;    int k;    int NodeNum,TreeDepth,LeafNodeNum,NodeNumLevel;        printf("创建二叉树: ");	CreatBiTree(&m_root);    printf("前序遍历（递归）: ");	PreOrderTra(m_root);	printf("\n");    printf("前序遍历（非递归）: ");    PreOrderTra_fdg(m_root);    printf("\n");    printf("中序遍历（递归）: ");    InOrderTra(m_root);    printf("\n");    printf("中序遍历（非递归）: ");    InOrderTra_fdg(m_root);    printf("\n");    printf("后序遍历（递归）: ");    PostOrderTra(m_root);    printf("\n");    printf("后序遍历（非递归）: ");    PostOrderTra_fdg(m_root);    printf("\n");    printf("层序遍历（数组）: ");    LevelTra(m_root);    printf("\n");    printf("层序遍历（队列）: ");    LevelTra_dl(m_root);    printf("\n");    printf("树的结点数: ");    NodeNum = GetNodeNum(m_root);    printf("%d\n",NodeNum);    printf("树的深度: ");    TreeDepth = GetTreeDepth(m_root);    printf("%d\n",TreeDepth);    printf("树的叶子结点数: ");    LeafNodeNum = GetLeafNodeNum(m_root);    printf("%d\n",LeafNodeNum);    printf("获取第几层的结点数: ");    scanf("%d",&k);    NodeNumLevel = GetNodeNumLevel(m_root,k);    printf("第%d层结点数为: %d\n",k,NodeNumLevel);	DeleteTree(m_root);    m_root = NULL;    //防止野指针	return 0;}

!@#$%^&*~

转载地址：http://inqwi.baihongyu.com/

你可能感兴趣的文章