二叉树的遍历及基本操作

时间:2022-01-31 17:30:49

        二叉树,顾名思义,是有每个结点有两个分支的树,我们将结点称为根节点,将它的两个分支称为它的左子树、右子树,所以我们用以下结构来定义二叉树的结构。
typedef char TreeNodeType;


typedef struct TreeNode//树的结点
{
    TreeNodeType data;//数据
    struct TreeNode* lchild;//左子树
    struct TreeNode* rchild;//右子树                                                                                                                                   
}TreeNode;

        树的基本实现:
void TreeInit(TreeNode** proot)//初始化
{
    if(proot == NULL)//非法输入
        return;
    *proot = NULL;
    return;
}

TreeNode* CreateTreeNode(TreeNodeType value)//创造一个新结点
{
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = value;
    new_node->lchild = NULL;
    new_node->rchild = NULL;
    return new_node;
}

void DestroyTreeNode(TreeNode* node)//销毁结点
{
    free(node);
    return;
}

        对于二叉树,最最基本的操作就是对二叉树进行遍历。而二叉树的遍历方式我们有先序遍历、中序遍历、后序遍历、层次遍历这几种,且遍历二叉树最重要的就是做到“ 不重不漏”。
1. 先序遍历(先访问根节点,再访问左子树,最后访问右子树)

二叉树的遍历及基本操作
        如图,即我们对图中二叉树进行了一个先序遍历。
(1)我们对整棵树的根节点进行访问,也就是图中的1即结点A;
(2)然后访问整棵树的左子树即2,对于2子树,我们再访问它的根节点也就是B,再访问它的左子树也就是3;
(3)我们可以看到3子树,只有根结点而无子树,所以我们访问了根结点D就可以返回到2树;
(4)返回到2树之后,按先序遍历的顺序接下来该访问2的右子树即4树;
(5)访问4树的根节点E,再访问它的左子树,因为它的左子树只有根结点G,所以我们访问完G就可以返回,而4树也无右子树,所以我们继续返回;
(6)上步最后我们应该返回到1树,去访问它的右子树5,对于5树先访问它的根节点C;
(7)访问完C后,应该访问C的左子树,但它左子树为空,所以我们直接访问右子树F;
(8)至此,该树已遍历完,所以先序遍历的结果是:A B D E G C F 

    整个过程,利用代码我们可以用递归实现,实现代码如下:
void TreePreOrder(TreeNode* root)//先序遍历
{//根左右
    //树为空也是遍历结束的条件
    if(root == NULL)//空树
    {
        printf("[%c] ",'#');
        return;
    }
    //访问根结点
    printf("[%c] ",root->data);
    //递归访问左子树
    TreePreOrder(root->lchild);
    //递归访问右子树
    TreePreOrder(root->rchild);
    return;                                                                                                                                                            
}
2. 中序遍历(先访问左子树,再访问根节点,最后访问右子树) 

        中序遍历的思想与先序遍历一样,只是访问顺序改变了。针对上图的二叉树,我们进行中序访问:
二叉树的遍历及基本操作
(1)首先访问1树的左子树2,对2树再访问左子树即3,3树无子树,所以访问根节点D,再返回到2树;

(2)此时,2树已访问完左子树,接下来访问根节点B,再到右子树4树;
(3)对4树,先访问它的左子树,左子树仅一个单节点,所以直接访问G,再返回访问E,4树无右子树,所以返回到2树,2树也访问完了,再继续返回到1树;
(4)1树该访问根节点即A,再访问1树的右子树即5树;
(5)对5树再按中序遍历访问,即C再F;
(6)至此,中序遍历访问结束,结果是:D B G E A C F

利用递归实现,实现代码如下:
void TreeInOrder(TreeNode* root)//中序遍历
{//左根右
    //树为空也是遍历结束的条件
    if(root == NULL)//空树
        return;
    //递归访问左子树
    TreeInOrder(root->lchild);
    //访问根结点
    printf("[%c] ",root->data);
    //递归访问右子树
    TreeInOrder(root->rchild);
    return;                                                                                                                                                            
}

3 . 后序遍历(先访问左子树,再访问右子树,最后访问根节点)  
二叉树的遍历及基本操作
(1)首先访问1的左子树2树,再访问2的左子树3,所以访问结点D,再返回到2树访问2的右子树4树;

(2)对4树,先访问左子树G,再访问右子树,因为右子树为空,所以访问根节点E,再返回到2树;
(3)此时该访问2树的根节点B,再返回到1树;

(4)此时该访问1树的右子树5树,对于5树先访问左子树为空,再访问右子树为F,最后访问根节点C,再返回1树;
(5)最后访问1树的根节点即A;

(6)至此,遍历结束结果为:D G E B F C A
利用递归实现代码如下:
void TreePostOrder(TreeNode* root)//后序遍历
{//左右根
    //树为空也是遍历结束的条件
    if(root == NULL)//空树
        return;
    //递归访问左子树
    TreePostOrder(root->lchild);
    //递归访问右子树
    TreePostOrder(root->rchild);
    //访问根结点
    printf("[%c] ",root->data);
    return;
}

4.层序遍历(从第一层,一层一层向下访问)
二叉树的遍历及基本操作
层序遍历很简单,大家应该都能很快地遍历出来:A B C D E  F G
代码实现的思想:
(1)我们可以利用队列实现,首先将二叉树的根节点放入队列即入A;
(2)拿队首元素为当前元素并访问,访问完出队,同时将当前元素的左右子树即B、C入队(子树为空则不入队);
(3)重复(2)步骤,即访问B再入D、E;访问C再入F;
(4)直至队列为空,遍历结束

实现代码

void TreeLevelOrder(TreeNode* root)//层序遍历
{//1.建一个队列,若根结点非空,先将根结点入队
//2.打印当前队列的首元素结点的data值,并将其出队
//3.若刚刚出队元素的左/右子树不为空,就将其入列,再重复23步骤,直至队列为空即遍历结束
    //树空也作为遍历结束的条件
    if(root == NULL)//空树
        return;
    SeqQueue queue;
    SeqQueueInit(&queue);
    SeqQueuePush(&queue,root);
    while(1)
    {
        SeqQueueType front;
        int ret = SeqQueueGetFront(&queue,&front);
        //队首元素为空说明遍历结束
        if(ret == 0)
            break;
        //访问当前元素结点,并打印其值
        printf("[%c] ",front->data);
        //将当前结点出队
        SeqQueuePop(&queue);
        //将当前结点的左右子树(若非空)则入队
        if(front->lchild != NULL)
            SeqQueuePush(&queue,front->lchild);
        if(front->rchild != NULL)
            SeqQueuePush(&queue,front->rchild);                                                                                                                        
    }
    printf("\n");
    return;
}

其中,以上用到的队列相关代码如下:(具体队列相关操作的实现,大家都可以在这里找到 点击打开链接,这里的代码只是稍作了修改而已)
typedef TreeNode* SeqQueueType;                                                                                                      
typedef struct SeqQueue//整个队列的元素是从head到tail,
{           //由于出队是头删,所以前面可能会有空,所以当tail走到最后时,tail再指向0,只要size与MAX_SIZE不相等,就还有空间
    SeqQueueType data[MAX_SIZE];
    size_t head;//队列第一个元素下标
    size_t tail;//队列最后一个元素的下标
    size_t size;//用了多少个元素的空间
}SeqQueue;
因为这里,要向队列里存放的是子树结点的指针,所以这里稍微修改了,下面的基本操作代码还是没有什么变化的。
void SeqQueueInit(SeqQueue* q)//初始化
{
    if(q == NULL)//非法操作
        return;
    q->size = 0;
    q->head = 0;
    q->tail = 0;
    return;
}

void SeqQueueDestroy(SeqQueue* q)//销毁队列
{
    if(q == NULL)
        return;
    q->size = 0;
    q->head = 0;
    q->tail = 0;
    return;
}

void SeqQueuePush(SeqQueue* q,SeqQueueType value)//入队列(尾插)
{
    if(q == NULL)
        return;
    if(q->size >= MAX_SIZE)//队列已满
        return;
    q->data[q->tail++] = value;
    if(q->tail >= MAX_SIZE)//tail走到最后,就再指向头(只要size<MAX_SIZE)
        q->tail = 0;
    q->size++;
    return;
}

void SeqQueuePop(SeqQueue* q)//出列队(头删)
{
    if(q == NULL)//非法操作
        return;
    if(q->size == 0)//空队
        return;
    q->head++;
    if(q->head >= MAX_SIZE)//别忘记!!!
        q->head = 0;
    q->size--;
    return;
}

int SeqQueueGetFront(SeqQueue* q,SeqQueueType* value)//取队首元素
{
    if(q == NULL)
        return 0;
    if(q->size == 0)
        return 0;
    *value = q->data[q->head];
    return 1;                                                                                                                        
}

void SeqQueuePrint(SeqQueue* q,const char* msg)//打印
{
    printf("[%s]\n",msg);
    if(q == NULL)
        return;
    if(q->size == 0)//空队列
    {
        printf("空队\n");
        return;
    }
    size_t i = q->head;
    if(q->tail <= q->head)//tail在head前
    {
        for(; i<MAX_SIZE; ++i)
            printf("[%c] ",q->data[i]);
        for(i=0; i<q->tail; ++i)//q->tail指向最后一个元素的下一个位置
            printf("[%c] ",q->data[i]);
    }
    else//tail在head后
    {
        for(i=q->head; i<q->tail; ++i)
            printf("[%c] ",q->data[i]);
    }
    printf("\n");
    return;
}
5.根据数组所给内容(包括空子树),构建一颗二叉树
TreeNode* _TreeCreate(TreeNodeType data[],size_t size,size_t* index,TreeNodeType null_node)//真正实现构建二叉树的代码
{
    if(index == NULL)//非法输入
        return NULL;
    if(*index >= size)//访问数组越界
        return NULL;
    if(data[*index] == null_node)//当前是空子树
        return NULL;
    TreeNode* new_node = CreateTreeNode(data[*index]);//2.
    ++(*index);//3.
    new_node->lchild = _TreeCreate(data,size,index,null_node);
    ++(*index);//4.
    new_node->rchild = _TreeCreate(data,size,index,null_node);
    return new_node;//返回当前子树的根结点
}

TreeNode* TreeCreate(TreeNodeType data[],size_t size,TreeNodeType null_node)//根据数组所给内容构建一颗二叉树
{//数组所给内容(这里给的是先序遍历结果)包括空子树,即参数null_node所代表的,第二个参数size表示树的大小
    //1.index用来标记当前元素为数组的哪个元素的下标
    //2.根据index所指内容创建一个结点
    //3.先++index,然后递归构建新结点的左子树
    //4.再++index,然后构建新结点的右子树
    size_t index = 0;
    return _TreeCreate(data,size,&index,null_node);
}                                        
6.树的深拷贝

        拷贝分为深拷贝、浅拷贝两种。浅拷贝是新建一个指针,将所要拷贝内容的空间的地址拿到放入指针;而深拷贝则是创建一块新内存,将想要的内容全部拷贝一份。
TreeNode* TreeClone(TreeNode* root)//树的深拷贝
{
    if(root == NULL)//空树
        return NULL;
    //按先序来拷贝
    TreeNode* new_node = CreateTreeNode(root->data);
    new_node->lchild = TreeClone(root->lchild);
    new_node->rchild = TreeClone(root->rchild);
    return new_node;
}

7. 树的销毁
法一:
void TreeDestroy1(TreeNode** root)//树的销毁1
{//基于后序来遍历销毁,防止根结点销毁之后找不到子树,造成没有全部销毁
    if(root == NULL)//非法输入
        return;
    if(*root == NULL)//空树
        return;
    TreeDestroy1(&((*root)->lchild));
    TreeDestroy1(&((*root)->rchild));
    DestroyTreeNode(*root);
    *root = NULL;
    return;
}

法二:
void TreeDestroy2(TreeNode** root)//树的销毁2
{//基于先序来遍历销毁,在销毁当前子树的根结点时,先保存左右子树,避免找不到而没删除
    if(root == NULL)//非法输入
        return;
    if(*root == NULL)//空树
        return;
    TreeNode* lchild = (*root)->lchild;
    TreeNode* rchild = (*root)->rchild;
    DestroyTreeNode(*root);
    TreeDestroy2(&lchild);
    TreeDestroy2(&rchild);
    *root = NULL;
    return;
}
8. 求树的结点
法一:

void _TreeSize(TreeNode* root,size_t* size)//真正用来计算树的结点
{
    if(root == NULL)//空树
        return;
    ++(*size);
    _TreeSize(root->lchild,size);
    _TreeSize(root->rchild,size);
}

size_t TreeSize(TreeNode* root)//求树的结点(不计算空结点)
{//用一个计数器,依次遍历结点,不为空就加1
    size_t size = 0;
    _TreeSize(root,&size);
    return size;
}

法二:
size_t TreeSize1(TreeNode* root)//求树的结点
{//根结点加左右子树的结点树
    if(root == NULL)//空树
        return 0;
    return 1+TreeSize(root->lchild)+TreeSize(root->rchild);
}

9. 求树的叶子结点个数
size_t TreeLeafSize(TreeNode* root)//求叶子结点的个数
{//左子树的叶子结点和右子树的叶子结点的和
    if(root == NULL)//空树
        return 0;
    //当前结点是叶子结点
    if(root->lchild == NULL && root->rchild == NULL)
        return 1;
    //当前结点不是叶子结点
    return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}

10. 求树第K层结点个数
size_t TreeKlevelSize(TreeNode* root,int K)//求第K层结点的个数(这里从第一层开始数)
{//求树的第K层结点数即求树的第K-1层结点子树的第一层结点数之和
    if(root == NULL || K < 1)//非法输入
        return 0;
    if(K == 1)
        return 1;
    return TreeKlevelSize(root->lchild,K-1)+TreeKlevelSize(root->rchild,K-1);
}

11.求树的高度
size_t TreeHeight(TreeNode* root)//求树的高度
{//根结点左右子树的高度较高者加1
    if(root == NULL)
        return 0;
    //当前结点无子树
    if(root->lchild==NULL && root->rchild==NULL)
        return 1;
    //当前结点有子树
    size_t lchild = TreeHeight(root->lchild);
    size_t rchild = TreeHeight(root->rchild);
    return 1+(lchild > rchild ? lchild : rchild);
}
12.给定一个数值,返回对应结点的指针(假设树上结点值无重复)
TreeNode* TreeFind(TreeNode* root,TreeNodeType to_find)//查找结点
{//给出一个数值,求对应结点的指针(假设无重复的数值结点)
    if(root == NULL)
        return NULL;
    //按照先序遍历访问
    if(root->data == to_find)
        return root;
    TreeNode* lresult = TreeFind(root->lchild,to_find);
    TreeNode* rresult = TreeFind(root->rchild,to_find);
    return lresult != NULL ? lresult :rresult;
}

13.给定一个结点,返回它的父结点
TreeNode* Parent(TreeNode* root,TreeNode* child)//求结点的父结点
{
    if(root == NULL || child == NULL)//非法输入
        return NULL;
    //当前结点的左或右子树是输入参数孩子结点
    if(root->lchild==child || root->rchild==child)
        return root;
    TreeNode* lresult = Parent(root->lchild,child);
    TreeNode* rresult = Parent(root->rchild,child);
    return lresult != NULL ? lresult : rresult;
}

14.给定一个结点,求它的左右子树
TreeNode* Lchild(TreeNode* root)//求当前结点的左子树
{
    if(root == NULL)
        return NULL;
    return root->lchild;
}

TreeNode* Rchild(TreeNode* root)//求当前结点的右子树
{
    if(root == NULL)
        return NULL;                                                                                                                                                   
    return root->rchild;
}