数据结构--二叉树遍历算法的应用

落日映苍穹つ 2022-01-07 23:27 185阅读 0赞

### 文章目录 ###

*  查询二叉树中的某个节点
 *  统计二叉树中叶子节点的个数
 *   *  参数形式
     *  全局变量形式
     *  返回值形式
 *  求二叉树的深度（后序遍历）
 *  复制二叉树（后续遍历）
 *  层次遍历二叉树
 *  总结

# 查询二叉树中的某个节点 #

1.  在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回TRUE;
2.  否则在左子树中进行查找,若找到,则返回TRUE;
3.  否则继续在右子树中进行查找,若找到,则返回TRUE,否则返回FALSE;

bool preOrder(BiTree T, int x, BiTree &p){
        //若二叉树中存在与x相同的元素
        //则p指向该节点并返回OK，否则返回false
        if(T){
            if(T->data == x){
                return true;
            } else {
                if(preOrder(T->lchild, x, p)){
                    return true;
                } else {
                    return preOrder(T->rchild, x, p);
                }
            }
        } else {
            return false;
        }
    }

# 统计二叉树中叶子节点的个数 #

算法基本思想:  
先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增 1。

## 参数形式 ##

void countLeaf(BiTree T, int &count){
        if(T){
            if(!T->lchild && !T->rchild){
                count++;    //对叶子节点计数
            }
            countLeaf(T->lchild, count);
            countLeaf(T->rchild, count);
        }
    }

## 全局变量形式 ##

void leaf(BiTree){
        if(T){
            leaf(T->lchild);
            leaf(T->rchild);
            if(!T->lchild && !T->rchild){
                leafCount++;
            }
        }
    }

## 返回值形式 ##

int countLeaf(BiTree T){
        if(T){
            m = countLeaf(T->lchild);
            n = coutLeaf(T->rchild);
            return m + n;   //若是要返回树的全部节点个数，则返回m+n+1
        }
    }

# 求二叉树的深度（后序遍历） #

算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加1 。

int depth(BiTree){
        if(!T){
            depthVal = 0;
        } else {
            depthLeft = depth(T->lchil);
            depthRight = depth(T->rchild);
            depthVal = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
        }
        return depthVal;
    }

# 复制二叉树（后续遍历） #

![image][]

BiTree getTreeNode(int item, BtTree *lptr, BiTree *rptr){
        if(!(T = new BiNode){
            exit(-1);
        }
        T->data = item;
        T->lchild = lptr;
        T->rchild = rptr;
        return T;
    }
    
    BiTree copyTree(BiNode *T){
        if(!T){
            return NULL;
        }
        if(T->lchild){  //复制左子树
            newlptr = copyTree(T->lchild);
        } else {
            newlptr = NULL;
        }
        
        if(T->rchild){  //复制右子树
            newlptr = copyTree(T->rchild);
        } else {
            newlptr = NULL;
        }
        
        newT = getTreeNode(T->data, newlptr, newrptr);
        return newT;
    }

--------------------

![image][image 1]

![image][image 2]

# 层次遍历二叉树 #

由层次遍历的定义可知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。

因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作:

1.  访问该元素所指结点;
2.  该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。

此过程不断进行，当队列为空时，二叉树的层次遍历结束。

void levelOrder(BiTree b){
        BiTree Queue[MAX_TREE_SIZE];
        int front, rear;
        if(b == NULL){
            return;
        }
        front = -1;
        rear = 0;
        Queue[rear] = b;
        while(front != rear){   //队列非空
            Visit(Queue[++front]->data)
            if(Queue[front]->lchild != NULL){
                Queue[++rear] = Queue[front]->lchild;
            }
            if(Queue[front]->rchild != NULL){
                Queue[++rear] = Queue[front]->rchild;
            }
        }
    }

# 总结 #

1.  若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2.  若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
3.  若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
4.  若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。

[image]: http://note.youdao.com/yws/res/15287/56B80CDA8AE344ABB796ADF11474CDAF
[image 1]: http://note.youdao.com/yws/res/15299/EBD1C7A22AF5495ABF677DE22C2F6184
[image 2]: http://note.youdao.com/yws/res/15301/2F5101C66A024064AFD1048CD6AA2489