第十章 基本数据结构——二叉树

可以参考：http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

摘要

　　书中第10章10.4小节介绍了有根树，简单介绍了二叉树和分支数目无限制的有根树的存储结构，而没有关于二叉树的遍历过程。为此对二叉树做个简单的总结，介绍一下二叉树基本概念、性质、二叉树的存储结构和遍历过程，主要包括先根遍历、中根遍历、后根遍历和层次遍历。

1、二叉树的定义

　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。

　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：

2、二叉树的性质

（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方

（2）深度为k的二叉树至多有2^k-1个节点（k>=1)。

（3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。

满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。

完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。

可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。

举例如下图是所示：

（4）具有n个节点的完全二叉树的深度为log2n + 1。

3、二叉树的存储结构

　　可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示：

//二叉树的数据结构
typedef struct binary_tree_node
{
    int elem;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
}binary_tree_node,*binary_tree;

举例说明二叉链表存储过程，如下图所示：

从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。

 

4、遍历二叉树

　　遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法：

（1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下：

//前序遍历递归版
void preorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        cout<<root->elem<<endl;
        preorder_traverse_recursive(root->left);
        preorder_traverse_recursive(root->right);
    }
}

具体过程如下图所示：

（2）中根遍历（中序遍历）：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。递归过程实现代码如下：

//中序遍历递归版
void inorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        inorder_traverse_recursive(root->left);
        cout<<root->elem<<endl;
        inorder_traverse_recursive(root->right);
    }
}

具体过程如下图所示：

（3）后根遍历（后序遍历）：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。递归实现代码如下：

//后序遍历递归版
void postorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        postorder_traverse_recursive(root->left);
        postorder_traverse_recursive(root->right);
        cout<<root->elem<<endl;
    }
}

具体过程如下图所示：

　　写一个完整的程序练习二叉树的三种遍历，采用递归形式创建二叉树，然后以递归的形式遍历二叉树，后面会接着讨论如何使用非递归形式实现这三种遍历，程序采用C++语言实现，完整程序如下：

#include<iostream>
#include<cstdlib>
using namespace std;

//二叉树的数据结构
typedef struct binary_tree_node
{
    int elem;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
}binary_tree_node,*binary_tree;

//前序遍历递归版
void preorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        cout<<root->elem<<endl;
        preorder_traverse_recursive(root->left);
        preorder_traverse_recursive(root->right);
    }
}

//中序遍历递归版
void inorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        inorder_traverse_recursive(root->left);
        cout<<root->elem<<endl;
        inorder_traverse_recursive(root->right);
    }
}

//后序遍历递归版
void postorder_traverse_recursive(binary_tree root)
{
    if(root!=NULL)
    {
        postorder_traverse_recursive(root->left);
        postorder_traverse_recursive(root->right);
        cout<<root->elem<<endl;
    }
}

//初始化二叉树
void init_binary_tree(binary_tree *root)
{
    *root=NULL;
}

//方法一：创建二叉树，注意传入的参数是二级指针，否则不能运行正确结果
/*void create_binary_tree(binary_tree *root)
{
    int elem;
    cout<<"Enter the node value (0 is end): ";
    cin>>elem;
    if(elem==0)
        *root=NULL;
    else
    {
        *root=(binary_tree)malloc(sizeof(binary_tree_node));
        if(*root==NULL)
        {
            cout<<"malloc error"<<endl;
            exit(1);
        }
        (*root)->elem=elem;
        cout<<"creating the left child node"<<endl;
        create_binary_tree(&((*root)->left));
        cout<<"creating the right child node"<<endl;
        create_binary_tree(&((*root)->right));
    }
}*/
//方法二
binary_tree create_binary_tree()
{
    int elem;
    binary_tree root;
    cout<<"Enter the node value (0 is end): ";
    cin>>elem;
    if(elem==0)
        root=NULL;
    else
    {
        //在堆空间分配的内存，可以返回局部对象
        root=(binary_tree)malloc(sizeof(binary_tree_node));
        if(root==NULL)
        {
            cout<<"malloc error"<<endl;
            exit(1);
        }
        (root)->elem=elem;
        cout<<"creating the left child node"<<endl;
        root->left=create_binary_tree();
        cout<<"creating the right child node"<<endl;
        root->right=create_binary_tree();
    }
    return root;
}

int main()
{
    binary_tree root;
    init_binary_tree(&root);
    root=create_binary_tree();
    preorder_traverse_recursive(root);
    inorder_traverse_recursive(root);
    postorder_traverse_recursive(root);
    exit(0);
}

View Code

 运行结果如下：

其中，两种创建方式以及为什么要传递二级指针，可以参考http://tieba.baidu.com/p/228434573#

 现在来讨论一下如何采用非递归实现这以上三种遍历。将递归形式转换为非递归形式，引入了额外的辅助结构栈。另外在讨论一次二叉树的层次遍历，可以借助队列进行实现。具体讨论如下：

先序遍历，其实过程很简单：一直往左走 root->left->left->left...->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。有两个办法：
1.用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的，因此是一个先进后出结构，需要用栈。
使用栈记忆的实现有两个版本。第一个版本是模拟递归的实现效果，跟LX讨论的，第二个版本是直接模拟递归。
2.节点增加指向父节点的指针：通过指向父节点的指针来回溯（后来发现还要需要增加一个访问标志，来指示节点是否已经被访问，不知道可不可以不用标志直接实现回溯？想了一下，如果不用这个标志位，回溯的过程会繁琐很多。暂时没有更好的办法。

先序遍历C++代码：非递归版本，用栈实现，版本1

//非递归先序遍历,使用栈实现，版本一
void preorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    if(root!=NULL)
    {
        s.push(root);
        binary_tree tmpnode;
        while(!s.empty())
        {
            tmpnode=s.top();
            cout<<tmpnode->elem<<endl; // 先访问根节点，然后根节点就无需入栈了
            s.pop();
            // 先push的是右节点，再是左节点
            if(tmpnode->right)
                s.push(tmpnode->right);
            if(tmpnode->left)
                s.push(tmpnode->left);
        }
    }
}

每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。同一时刻，栈中元素为m-1个右节点和1个最左节点，最高为h。所以空间也为O(h)；每个节点同样被压栈一次，弹栈一次，访问一次，时间复杂度O(n)。

先序遍历代码：非递归版本，用栈实现，版本2

//非递归实现先序遍历，使用栈实现，版本二
void preorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    while(root||!s.empty())
    {
        if(root)
        {
            cout<<root->elem<<endl;// 先序就体现在这里了，先访问，再入栈
            s.push(root);
            root=root->left;// 依次访问左子树
        }
        else
        {
            root=s.top();// 回溯至父亲节点
            s.pop();
            root=root->right;
        }
    }
}

每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最后一个访问的节点，访问其右子树。在同一层中，不可能同时有两个节点压入栈，因此栈的大小空间为O(h)，h为二叉树高度。时间方面，每个节点都被压入栈一次，弹出栈一次，访问一次，复杂度为O(n)。

（2）中根遍历非递归实现

　　中根遍历要求顺序是左根右，借助栈s实现。先将根root入栈，接着从根root开始查找最左的子孩子结点直到为空为止，再将左子树节点出栈遍历，然后判断该左子树的右子树节点入栈。循环此过程，直到栈为空为止。采用C++中模板库stack实现先根遍历如下：

//非递归实现中序遍历，使用栈实现
void inorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    while(root||!s.empty())
    {
        if(root)
        {
            s.push(root);
            root=root->left;
        }
        else
        {
            root=s.top();
            cout<<root->elem<<endl;
            s.pop();
            root=root->right;
        }
    }
}

根据上面的先序遍历，可以类似的构造出中序遍历。仔细想一下，只有第2种方法改过来时最方便的。需要的改动仅仅调换一下节点访问的次序，先序是先访问，再入栈；而中序则是先入栈，弹栈后再访问。

（3）后根遍历递归实现

　　后根遍历要求访问顺序是左右根，采用辅助栈实现时，需要一个标记，判断结点是否访问了，因为右子树是通过跟结点的信息得到的。实现过程是先将根结点及其左子树入栈，并初始标记为0，表示没有访问，然后通过判断栈是否为空和标记的值是否为1来判断是否访问元素。

参考：http://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html

采用C++模板库stack具体实现程序如下：

void postorder_traverse(binary_tree root)
{
    if(NULL != root)
    {
        stack<binary_tree_node*> s;
        binary_tree_node *ptmpnode;
        int flags[100];
        ptmpnode = root;
        while(NULL != ptmpnode || !s.empty())
        {
            //将结点左子树结点入栈
            while(NULL != ptmpnode)
            {
                s.push(ptmpnode);
                flags[s.size()] = 0;   //标记未访问
                ptmpnode=ptmpnode->left;
            }
            //输出访问的结点
            while(!s.empty() && flags[s.size()] == 1)
            {
                ptmpnode = s.top();
                s.pop();
                cout<<ptmpnode->elem<<" ";
            }
            //从右子树开始遍历
            if(!s.empty())
            {
                ptmpnode = s.top();
                flags[s.size()] = 1;  //登记访问了
                ptmpnode = ptmpnode->right;
            }
            else
                break;
        }
    }
}

一种更简单的实现，第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

//非递归后序遍历，使用栈实现
void postorder_traverse(binary_tree root)
{
    binary_tree curr; //当前结点
    binary_tree pre=NULL; //上一次访问的结点
    stack<binary_tree> s;
    if(root)
        s.push(root);
    while(!s.empty())
    {
        curr=s.top();
        //如果当前结点没有孩子结点或者孩子节点都已被访问过
        if((curr->left==NULL&&curr->right==NULL)||(pre!=NULL&&(pre==curr->left||pre==curr->right)))
        {
            cout<<curr->elem<<endl;
            s.pop();
            pre=curr;
        }
        else
        {
            if(curr->right)
                s.push(curr->right);
            if(curr->left)
                s.push(curr->left);
        }
    }
}

对于判断条件if((curr->left==NULL&&curr->right==NULL)||(pre!=NULL&&(pre==curr->left||pre==curr->right)))的第二部分，开始我没了解，后来想想好像是当前访问结点之前的访问结点只有两种情况，如果当前访问结点存在右子树，则上一次的访问结点pre只能是右子树，否则，就是左子树了。所以，如果满足条件pre!=NULL&&pre==curr->left，说明当前结点不存在右子树，所以不需要判断右子树是否被访问了。否则就是左右子树都被访问了。

（4）层次遍历实现

　　层次遍历要求从根向下、从左向右进行访问，可以采用队列实现。先将根入队，然后队列进程出队操作访问结点p，再将结点p的左子树和右子树结点入队，循环执行此过程直到队列为空。出队顺序即是层次遍历结果。采用C++的模板库queue实现如下：

//层次遍历
void levelorder_traverse(binary_tree root)
{
    queue<binary_tree> q;
    binary_tree tmpnode;
    if(root)
        q.push(root);
    while(!q.empty())
    {
        tmpnode=q.front();
        cout<<tmpnode->elem<<" ";
        q.pop();
        if(tmpnode->left)
            q.push(tmpnode->left);
        if(tmpnode->right)
            q.push(tmpnode->right);
    }
}

 综合上面的分析过程写个完整的程序测试二叉树遍历的非递归实现，采用C++语言，借助stack和queue实现，完整程序如下所示：

#include<iostream>
#include<stack>
#include<queue>
#include<cstdlib>
using namespace std;

typedef struct binary_tree_node
{
    int elem;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
}binary_tree_node,*binary_tree;

//非递归先序遍历,使用栈实现，版本一
/*void preorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    if(root!=NULL)
    {
        s.push(root);
        binary_tree tmpnode;
        while(!s.empty())
        {
            tmpnode=s.top();
            cout<<tmpnode->elem<<" ";
            s.pop();
            if(tmpnode->right)
                s.push(tmpnode->right);
            if(tmpnode->left)
                s.push(tmpnode->left);
        }
    }
}*/
//非递归实现先序遍历，使用栈实现，版本二
void preorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    while(root||!s.empty())
    {
        if(root)
        {
            cout<<root->elem<<" ";
            s.push(root);
            root=root->left;
        }
        else
        {
            root=s.top();
            s.pop();
            root=root->right;
        }
    }
}

//非递归实现中序遍历，使用栈实现
void inorder_traverse(binary_tree root)
{
    stack<binary_tree> s;
    while(root||!s.empty())
    {
        if(root)
        {
            s.push(root);
            root=root->left;
        }
        else
        {
            root=s.top();
            cout<<root->elem<<" ";
            s.pop();
            root=root->right;
        }
    }
}

//非递归后序遍历，使用栈实现
void postorder_traverse(binary_tree root)
{
    binary_tree curr;//当前结点
    binary_tree pre=NULL; //前一次访问的结点
    stack<binary_tree> s;
    if(root)
        s.push(root);
    while(!s.empty())
    {
        curr=s.top();
        if((curr->left==NULL&&curr->right==NULL)||(pre!=NULL&&(pre==curr->left||pre==curr->right)))
        {
            cout<<curr->elem<<" ";
            s.pop();
            pre=curr;
        }
        else
        {
            if(curr->right)
                s.push(curr->right);
            if(curr->left)
                s.push(curr->left);
        }
    }
}

//层次遍历
void levelorder_traverse(binary_tree root)
{
    queue<binary_tree> q;
    binary_tree tmpnode;
    if(root)
        q.push(root);
    while(!q.empty())
    {
        tmpnode=q.front();
        cout<<tmpnode->elem<<" ";
        q.pop();
        if(tmpnode->left)
            q.push(tmpnode->left);
        if(tmpnode->right)
            q.push(tmpnode->right);
    }
}
//初始化二叉树
void init_binary_tree(binary_tree *root)
{
    *root=NULL;
}

//方法一：创建二叉树，注意传入的参数是二级指针，否则不能运行正确结果
/*void create_binary_tree(binary_tree *root)
{
    int elem;
    cout<<"Enter the node value (0 is end): ";
    cin>>elem;
    if(elem==0)
        *root=NULL;
    else
    {
        *root=(binary_tree)malloc(sizeof(binary_tree_node));
        if(*root==NULL)
        {
            cout<<"malloc error"<<endl;
            exit(1);
        }
        (*root)->elem=elem;
        cout<<"creating the left child node"<<endl;
        create_binary_tree(&((*root)->left));
        cout<<"creating the right child node"<<endl;
        create_binary_tree(&((*root)->right));
    }
}*/
//方法二
binary_tree create_binary_tree()
{
    int elem;
    binary_tree root;
    cout<<"Enter the node value (0 is end): ";
    cin>>elem;
    if(elem==0)
        root=NULL;
    else
    {
        //在堆空间分配的内存，可以返回局部对象
        root=(binary_tree)malloc(sizeof(binary_tree_node));
        if(root==NULL)
        {
            cout<<"malloc error"<<endl;
            exit(1);
        }
        (root)->elem=elem;
        cout<<"creating the left child node"<<endl;
        root->left=create_binary_tree();
        cout<<"creating the right child node"<<endl;
        root->right=create_binary_tree();
    }
    return root;
}

int main()
{
    binary_tree root;
    init_binary_tree(&root);
    root=create_binary_tree();
    cout<<"先序遍历：";
    preorder_traverse(root);
    cout<<endl;
    cout<<"中序遍历： ";
    inorder_traverse(root);
    cout<<endl;
    cout<<"后序遍历： ";
    postorder_traverse(root);
    cout<<endl;
    cout<<"层次遍历:  ";
    levelorder_traverse(root);
    cout<<endl;
    exit(0);
}

View Code

运行结果：

时间： 2024-09-20 00:05:56

第十章 基本数据结构——二叉树的相关文章

算法-求助，数据结构二叉树问题

问题描述 求助,数据结构二叉树问题 试编写算法,求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列),若这样的路径存在多条,则输出路径终点(叶子结点)在"最左"的一条. 解决方案 ?? #define null 0???#include "stdio.h"???typedef char datatype;?? typedef struct tn? {datatype data;?? struct tn lc,

数据结构二叉树问题求助

问题描述 数据结构二叉树问题求助 设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为(),最小结点数为() 答案是(2^k+1)-1和k+1.我做出来的是(2^k)-1和k 求帮忙算一下哪个是对的,谢谢了 解决方案 带入法计算就可以了.跟节点高度为0,比如高度为1,最大就有3个,最小两个.一看你的答案就错了. 解决方案二: ?? #define null 0???#include "stdio.h" ???typedef char datatype;?? typedef

java 数据结构二叉树的实现代码_java

1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

第十章 基本数据结构——链表

 链表 链表与数组的区别是链表中的元素顺序是有各对象中的指针决定的,相邻元素之间在物理内存上不一定相邻.采用链表可以灵活地表示动态集合.链表有单链表和双链表及循环链表.书中着重介绍了双链表的概念及操作,双链表L的每一个元素是一个对象,每个对象包含一个关键字和两个指针:next和prev.链表的操作包括插入一个节点.删除一个节点和查找一个节点,重点来说一下双向链表的插入和删除节点操作,图例如下: 链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就

C#与数据结构--二叉树的遍历

二叉树的存储结构 二叉树的存储可分为两种:顺序存储结构和链式存储结构. 1.顺序存储结构 把一个满二叉树自上而下.从左到右顺序编号,依次存放在数组内,可得到图6.8(a)所示的结果.设满二叉树结点在数组中的索引号为i,那么有如下性质. (1)如果i = 0,此结点为根结点,无双亲. (2)如果i > 0,则其双亲结点为(i -1) / 2 .(注意,这里的除法是整除,结果中的小数部分会被舍弃.) (3)结点i的左孩子为2i + 1,右孩子为2i + 2. (4)如果i > 0,当i为奇数时,它

数据结构 二叉树-二叉树 节点类型为结构类型 如何初始化和赋值？

问题描述 二叉树 节点类型为结构类型 如何初始化和赋值? struct ItemNode { int id; string name; }; typedef struct BNode { ItemNode node; BNode *lChild; BNode *rChild; }BNode; 解决方案 ItemNode i1, i2, i3; i1.id = 1; i1.name = "a"; i1.id = 2; i1.name = "b"; i1.id = 3;

数据结构——二叉树

1 基本定义 ①二叉树是n(n>=0)个结点的有限集,当n=0时,二叉树为空.当n>0时,二叉树是由一个根节点及至多两颗子树组成,且左右子树都是二叉树.    不同于树,二叉树中的结点要区分左子树和右子树,即使只有一颗子树,左单子树不同于右单子树. ②树的一些基本术语: 结点:包含了数据元素及若干个指向其子树的分支. 结点的度:结点的子树数目或分支个数. 树的度:在树中取各结点的度的最大值. 结点的路径:从根结点到该结点所经分支和结点构成的结点的路径. 结点的层次:设根结点的层次为1,则其子树

数据结构 二叉树 遍历-树的括号表示法怎么写

问题描述 树的括号表示法怎么写 #include #include #include using namespace std;struct treenode{char data;treenode firstchild;treenode *nextsibling;};treenode * creat_tree(char&a){ if((*a)==''){a++;}if((*a)=='')return NULL;if((*a)==')'){a++;return NULL;}if((*a)=='(')

第十章 基本数据结构——栈和队列

摘要 本章介绍了几种基本的数据结构,包括栈.队列.链表以及有根树,讨论了使用指针的简单数据结构来表示动态集合.本章的内容对于学过数据结构的人来说,没有什么难处,简单的总结一下. 1.栈和队列 栈和队列都是动态集合,元素的出入是规定好的.栈规定元素是先进后出(FILO),队列规定元素是先进先出(FIFO).栈和队列的实现可以采用数组和链表进行实现.在标准模块库STL中有具体的应用,可以参考http://www.cplusplus.com/reference/. 栈的基本操作包括入栈push和出栈p