二叉树的操作集合总结

2024-01-06 22:06:40

一，二叉树：

1，重要性质：

2，二叉树的遍历：

二叉树的遍历一共分为四种，三种是用递归实现的，一种是使用队列实现的：

三种分别是前序遍历，中序遍历，后序遍历。还有一种是层序遍历是通过队列实现的

void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空树则直接返回 */
    
    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}

对于一个二叉树而言，有一个根节点，两个儿子。前三种遍历的区别就是访问顺序不同。中序遍历先访问左节点，再访问根节点，最后是右节点。那么最后储存的形式是根节点在中间，左边是左子树，右边是右子树。后面就我的理解对这个递归的过程做一个分析：从根节点开始如果左子树存在的话就一直往左子树递归，栈帧全部都会被保存，当左节点是空的话就开始返回并执行后面的语句，每次访问之后都会看是否存在右节点，如果存在的话就对右结点进行递归，如果不存在的话这个栈帧好像是给直接跳过不执行了。因为左递归是在上面的，所以说每次右递归递归一次后都要看是否存在左节点，如果存在的话左节点进行递归之后再进行右结点的递归。

前序遍历就是先访问再进行左遍历，右遍历。后续就是先左再右再中，递归过程按我的理解和上面差不多。

最后就是层序遍历了

层序遍历利用队列来实现，首先创建一个空队列，把根结点入队，只要队列不是空的，就把队列头给取出来判断是否有左（右）儿子。如果有的话就入队重复这样的操作也能够遍历所有的结点。这样遍历出现的结点都是一层一层出现的所以叫层序遍历。

3，中序遍历的非递归算法：

这个个人感觉还是要画一个图来思考（[⊹(ಡᗜಡ)⊹]我比较笨直接看，看不懂），首先把树的左节点全部压入栈，全部压入之后在出栈后如果有右节点的话，下一个循环就是从右节点开始把相应的左结点都压入栈。如果没有右节点的话，就内循环直接进不去了（前提是栈不是空的，如果栈是空的的话外循环也进不去了）。

4，求树高

求树高也是也是用递归的思路进行的，分别把左子树和右子树遍历到底，记录树的深度，最后返回两者最大值加一。还有就是递归的退出条件是根节点不是NULL。

5，怎么使用遍历来确定一棵树（题目后面再写）

首先要明确一件事就是只能通过中序遍历加上另外一个遍历才能确定唯一二叉树，如果只通过前序和后序遍历是不能确定一棵树的。因为不知道分界点。

举个例子把，首先通过先序遍历可以确定根节点就是开头的位置。然后去找这个根节点再中序遍历中的位置，这个位置左边就是左子树，右边就是右子树。接着就可以通过中序来确定先序序列的左子树和右子树分界线在什么位置了。就是右边的中序序列的根节点的位置，然后左边继续找最开头的位置作为根节点，接着定位到右边的中间，这样又可以把先序序列的左子树分成新的左子树和右子树。像这样按照一定规律继续重复的就肯定可以用递归来计算。（说实话(◍ō ﻌ ō◍)我还没有很搞懂右边右子树是怎么搞的明天写博客就写这个算了，好像pta里面还有两题）

码农公寓