二叉树基础知识及遍历方式

二叉树基础知识及遍历方式

参考自：1、link.
参考自：2、link.

二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。

一、特殊的二叉树及特点 1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少

2、满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡。

根据满二叉树的定义，得到其特点为：

• 叶子只能出现在最下一层。
• 非叶子结点度一定是2.
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

3、完全二叉树

对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。

其中关键点是按层序编号，然后对应查找。

上图就是一个完全二叉树。

结合完全二叉树定义得到其特点：

• 叶子结点只能出现在最下一层（满二叉树继承而来）
• 最下层叶子结点一定集中在左 部连续位置。
• 倒数第二层，如有叶子节点，一定出现在右部连续位置。
• 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

根据下图加深理解，什么时候是完全二叉树。

三、二叉树的性质 1、一般二叉树的性质

1）在非空二叉树的i层上，至多有2^（i-1）个节点(i >=1)。通过归纳法论证。

2）在深度为K的二叉树上最多有2^K - 1个结点（k>=1)。通过归纳法论证。

3）对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1

在一棵二叉树中，除了叶子结点（度为0）之外，就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2;在二叉树中结点总数为T，而连线数为T-1.所有：n0+n1+n2-1 = 2*n2 +n1;最后得到n0 = n2+1;

上图中结点总数是10，n2为4，n1为1，n0为5。

2 完全二叉树性质

在上图中验证

• 第一条： 当i=1时，为根节点。当i>1时，比如结点为7，他的双亲就是7/2= 3；结点9双亲为4.

• 第二条：结点6,6 * 2 = 12>10，所以结点6无左孩子，是叶子结点。结点5，5*2 = 10，左孩子是10,结点4，为8.

• 第三条：结点5，2*5+1>10,没有右孩子，结点4，则有右孩子。

四 二叉树的遍历

二叉树遍历：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。

这里有两个关键词：访问和次序。

在遍历之前，首先要知道二叉树的节点的定义：

struct tree {
  struct tree* left;
  struct tree* right;
  int value;
};

1 递归遍历

1 ) 前序递归遍历

基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。

代码实现，如下所示

//前序递归遍历
void PreOrderTraverse(struct tree* t)
{
  //注意跳出条件
    if(t == NULL)
    {
    	return;
    }
       //注意访问语句顺序
     printf("%d ", t->data);
     PreOrderTraverse(t->lchild);
     PreOrderTraverse(t->rchild);
    
}

2 ) 中序递归遍历:

基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。

//中序递归遍历
void InOrderTraverse(struct tree* t)
{
    //递归结束条件
    if(t == NULL)
    	return;
        
    InOrderTraverse(t->lchild);
    printf("%d ", t->data);
    InOrderTraverse(t->rchild); 
}

3 ) 后序递归遍历:

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。

//后序递归遍历
void PostOrderTraverse(BiTree t)
{
    if(t == NULL)
    	return;
    PostOrderTraverse(t->lchild);
    PostOrderTraverse(t->rchild);
    printf("%d", t->data);
    
}

2 非递归遍历

虽然递归实现简单，但是递归函数有自己特定的问题，比如递归调用会耗费很多的栈空间，也就是内存，同时该过程较为耗时，因此其性能通常不及非递归版本。

那么我们该如何实现非递归的遍历树呢？

要解决这个问题，我们必须清楚的理解递归函数的调用过程。

从递归函数的调用过程可以看出，递归调用无非就是函数帧入栈出栈的过程，因此我们可以直接使用栈来模拟这个过程，只不过栈中保存的不是函数而是树节点。

确定用栈来模拟递归调用这一点后，接下来我们就必须明确两件事：

什么情况下入栈
什么情况下出栈

我们还是以先序遍历为例来说明。

仔细观察递归调用的过程，我们会发现这样的规律：

• 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
• 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并以右子树为新的根节点重复过程1直到栈空为止

现在我们可以回答这两个问题了。

什么情况下入栈？

• 最开始时先把从根节点开始的所有左子树节点放入栈中，第二步中如果栈顶有右子树那么重复过程1，这两种情况下会入栈。

那么什么情况下出栈呢？

• 当查看栈顶元素时实际上我们就可以直接pop掉栈顶元素了，这是和递归调用不同的一点，为什么呢？因为查看栈顶节点时我们可以确定一点事，那就是当前节点的左子树一定已经处理完毕了，因此对于栈顶元素来说我们需要的仅仅是其右子树的信息，拿到右子树信息后栈顶节点就可以pop掉了。

因此上面的描述用代码来表示就是：

void search(tree* root) {
    if(root == NULL)
        return ;
    stacks;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){
        s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并重复过程1直到栈空为止
        tree* top = s.top();
        tree* t = top->right;
        s.pop();
   
        while(t){
            s.push(t);
            t = t->left;
        }
    }
    return r;
}

1）非递归先序遍历

所以对于先序遍历来说，我们只需要在节点入栈之前打印出来就可以了：

void search_pre_order(tree* root) {
    if(root == NULL)
        return ;
    stacks;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){
        printf("%d ", root->value); // 节点入栈前打印 
        s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并重复过程1直到栈空为止
        tree* top = s.top();
        tree* t = top->right;
        s.pop();
   
        while(t){
            printf("%d ", root->value); // 节点入栈前打印 
            s.push(t);
            t = t->left;
        }
    }
    return r;
}

2）非递归中序遍历

对于中序遍历呢只需要在节点pop时打印就可以了：

void search_in_order(tree* root) {
    if(root == NULL)
        return ;
    stacks;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){
        s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并重复过程1直到栈空为止
        tree* top = s.top();
        printf("%d ", top->value); // 节点pop时打印 
        tree* t = top->right;
        s.pop();
   
        while(t){
            s.push(t);
            t = t->left;
        }
    }
    return r;
}

3）非递归后序遍历

后续遍历相对复杂，原因就在于出栈的情况不一样了。

在先序和中序遍历过程中，只要左子树处理完毕实际上栈顶元素就可以出栈了，但是后续遍历情况不同，什么是后续遍历？只有左子树和右子树都遍历完毕才可以处理当前节点，这是后续遍历，那么我们该如何知道当前节点的左子树和右子树都处理完了呢？

显然我们需要某种方法记录下遍历的过程，实际上我们只需要记录下遍历的前一个节点就足够了。

如果我们知道了遍历过程中的前一个节点，那么我们就可以做如下判断了：

如果前一个节点是当前节点的右子树，那么说明右子树遍历完毕可以pop了
如果前一个节点是当前节点的左子树而且当前节点右子树为空，那么说明可以pop了
如果当前节点的左子树和右子树都为空，也就是叶子节点那么说明可以pop了

这样什么情况下出栈的问题就解决了，如果不符合这些情况就不能出栈。

只需要根据以上分析对代码稍加修改就可以了：

void search_post_order(tree* root) {
    if(root == NULL)
        return ;
    stacks;
    TreeNode* last=NULL; // 记录遍历的前一个节点
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){
        s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        tree* top = s.top();
        if (top->left ==NULL && top->right == NULL ||   // 当前节点为叶子节点
            last==top->right ||                         // 前一个节点为当前节点的右子树 
            top->right==NULL && last==top->left){ // 前一个节点为当前节点左子树且右子树为空
            printf("%d ", top->value);            // 节点pop时打印 
            last = top;                           // 记录下前一个节点
            s.pop();
        } else {
            tree* t = top->right;
            while(t){
                s.push(t);
                t = t->left;
            }
        }
    }
    return r;
}

3 总结：

树的递归遍历相对简单且容易理解，但是递归调用实际上隐藏了相对复杂的遍历过程，要想以非递归的方式来遍历二叉树就需要仔细理解递归调用过程。