精华内容
下载资源
问答
  • 2018-06-19 14:00:05

    二叉树的非递归遍历

    • 二叉树的三种遍历方式也可以通过非递归的方法借助栈来实现。
    • 通过控制节点的出栈和入栈先后顺序来实现对树的不同方式的遍历。

    非递归先根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 从根节点开始,依次访问树中最左端的节点并入栈,当节点为空停止入栈。
    • 取栈顶元素为当前节点并出栈,如果当前节点有右子树,则遍历其右子树。
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归中根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 同样地,先依次将根节点及其左子树最左端的节点入栈,但不进行访问。当节点为空,则停止入栈。
    • 访问栈顶元素作为当前节点并出栈,如果当前节点有右子树,则遍历访问其右子树。
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归后根遍历二叉树

    • 非递归后根遍历相比前两个有点麻烦,需要引入一个中间变量标记已经访问节点。
    • 当栈不为空或者当前节点为不为空,执行操作:
    • 依次将根节点及其左子树的左端节点入栈,但不进行访问,当节点为空,停止入栈。
    • 取栈顶元素作为当前节点,如果当前节点的右孩子(右子树)不为空且其右孩子不是上一次访问的节点。则当前节点变为其右子树,遍历其右子树。如果当前节点的右孩子为空或者其右孩子已经被访问,则访问当前节点,标记当前节点为已访问节点,出栈。将当前节点置为空(此时右孩子访问过了),继续取栈顶元素(为了访问根节点)。
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    附总的代码实现

    #include<iostream>
    using namespace std;
    typedef int ElemType;
    
    typedef struct _TreeNode {  // 定义二叉查找树的结构
        ElemType data;          // 数据
        struct _TreeNode* left;         // 指向左孩子指针
        struct _TreeNode* right;        // 指向其右孩子指针 
    }TreeNode, *SearchBTree;
    
    typedef SearchBTree StackElemType;
    typedef struct StackNode {          // 定义栈的结构(基于链表)
        SearchBTree data;
        StackNode *next;
    }*Stack;
    
    void initStack(Stack St)        // 初始化栈,把头节点看作是栈顶
    {
        St->next = nullptr;
    }
    
    int isEmpty(Stack St)
    {
        return St->next == nullptr;
    }
    
    void Push(Stack St, SearchBTree x)      // 每次从将元素插入到头节点的位置,头节点上移
    {
        StackNode* q = new StackNode;
        q->data = x;
        q->next = St->next;     // q的next域指向St(头节点)的后继结点
        St->next = q;           // St(头节点/栈顶)next域指向q,实现栈往上移
    }
    
    void Pop(Stack St)      // 出栈
    {
        StackNode* p = St->next;        // 临时结点指向头结点(栈顶)的后继结点
        St->next = p->next;     // 栈顶下移
        delete p;           // 释放空间
    }
    
    SearchBTree getTop(Stack St)
    {
        return St->next->data;
    }
    
    SearchBTree EmptyTree(SearchBTree T)    // 初始化、构造一颗空树/销毁一颗树
    {
        if (!T)
        {
            EmptyTree(T->left);     // 递归地释放空间
            EmptyTree(T->right);
            delete T;
        }
        return nullptr;
    }
    
    void Insert(SearchBTree &T, ElemType x)
    {
        if (!T)
        {
            TreeNode* pT = new TreeNode;        // 申请节点空间
            pT->data = x;                       // 为节点赋值
            pT->left = pT->right = nullptr;
            T = pT;                             // 将pT赋给T
        }
        else
        {
            if (x < T->data)                // 如果x小于某个结点的数据
                Insert(T->left, x);         // 递归地在其左子树上寻找空结点插入
            else if (x > T->data)           // 如果x大于某个结点的数据
                Insert(T->right, x);        // 递归地在其左子树上寻找空结点插入
        }
    }
    
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    int main()
    {
        const ElemType rawdata[] = { 19, 7, 9, 15, 23, 39, 4, 2, 75, 100, 43, 58 };
        SearchBTree myTree = new TreeNode;
        myTree = EmptyTree(myTree);     // 初始化树
        for (int i = 0;i < sizeof(rawdata) / sizeof(ElemType);i++)
        {
            Insert(myTree, rawdata[i]);     // 向树中插入给定数据
        }
    
        cout << "The inorder print of the tree is: \n";
        InorderPrint(myTree);
        cout << "The preorder print of the tree is: \n";
        PreorderPrint(myTree);
        cout << "The postorder print of the tree is: \n";
        PostorderPrint(myTree);
    
        delete myTree;
        system("pause");
        return 0;
    }
    • 操作运行结果
    The preorder print of the tree is:
    19 7 4 2 9 15 23 39 75 43 58 100
    The inorder print of the tree is:
    2 4 7 9 15 19 23 39 43 58 75 100
    The postorder print of the tree is:
    2 4 15 9 7 58 43 100 75 39 23 19
    更多相关内容
  • 二叉树先次序遍历中根次序遍历、后次序遍历
  • 二叉树先根遍历中根遍历、后根遍历非递归算法的C++代码

    上期文章: 数据结构 | 树与二叉树

    参考教材:《数据结构》,刘大有

    编程语言: C++


    目录

    (一)二叉树的存储结构

    (二)二叉树的遍历

    先根遍历非递归算法

    中根遍历非递归算法

    后根遍历非递归算法


    (一)二叉树的存储结构

     二叉树在计算机中具有顺序存储和链式存储两种存储方式。在本文所讨论的算法中,二叉树均是采用二叉链表的存储方式

    struct Node{
        Node *left;
        Node *right;
        char data;
        Node():left(nullptr),right(nullptr),data('#'){}
    };

    其中left指向该结点左儿子的指针right指向该结点右儿子的指针 

    (二)二叉树的遍历

    先根遍历非递归算法

    先根遍历的顺序为①访问根、②遍历左子树、③遍历右子树

    为了实现先根遍历的非递归算法,我们需要引进一个辅助堆栈,栈的元素为Node *类型

    //栈
    class Stack{
    public:
        Stack():top(0){
            for(int i=0;i<s_size;i++){
                s[i]=nullptr;
            }
        }
        //入栈
        void push(Node *p){
            if(top<s_size){
                s[top]=p;
                top++;
            }else{
                cout<<"Stack overflow!"<<endl;
                return;
            }
        }
        //出栈
        Node *pop(){
            if(top==0){
                return nullptr;
            }else{
                top--;
                return s[top];
            }
        }
        bool isEmpty(){
            if(top==0)
                return true;
            else
                return false;
        }
    private:
        const int s_size=20;
        Node *s[s_size];
        int top;
    };

    先根遍历的非递归算法较为简单,用自然语言描述就是:

    1. 根结点入栈
    2. 判断,如果栈为空则结束算法;否则,当栈不为空时:弹栈,访问该结点;如果该结点右儿子存在则入栈;如果该结点左儿子存在则入栈
    3. 返回第2步
    /*先根遍历非递归算法*/
    void nPreOrder(Node * root){
        if(root == nullptr){
            return;
        }
        Stack s;
        Node *p=root;
        //根节点入栈
        s.push(p);
        //栈不为空时:
        while(!s.isEmpty()){
            //弹栈:
            p=s.pop();
            cout<<p->data;
            //右儿子入栈:
            if(p->right!=nullptr){
                s.push(p->right);
            }
            //左儿子入栈:
            if(p->left!=nullptr){
                s.push(p->left);
            }
        }
        return;
    }

    以下面这棵树为例

    算法执行过程中,栈的变化情况如下,最终输出的先根序列为ABDFCE


    中根遍历非递归算法

    中根遍历的顺序为①遍历左子树、②访问根、③遍历右子树

    中根遍历的非递归算法也需要引入辅助堆栈,栈的结构与上面先根遍历非递归算法用到的栈Stack相同

    中根遍历非递归算法思想:

    1. 令p=root
    2. 判断,如果栈不为空或p不等于nullptr,执行下一步;否则算法结束
    3. 当p不等于nullptr(空指针)时,让p结点入栈;如果p结点的左儿子存在,也让其左儿子入栈;如果p结点左儿子的左儿子存在,依然让其左儿子的左儿子入栈......以此类推,直到p的某一个后裔结点不存在左儿子时,执行下一步
    4. 弹出栈顶元素(这时候栈一定不为空),访问该结点,把该结点的右儿子的地址赋值给p;返回第2步
    /*中根遍历非递归算法*/
    void nInOrder(Node * root){
        if(root==nullptr){
            return;
        }
        Stack s;
        Node *p=root;
    
        while( (!s.isEmpty()) || (p!=nullptr) ){
            while(p!=nullptr){
                s.push(p);
                p=p->left;
            }
            p=s.pop();
            cout<<p->data;
            p=p->right;
        }
    }

    以下面这棵树为例

    算法执行过程中,栈的变化情况如下,最终输出的中根序列为BFDAEC


    后根遍历非递归算法

    后根遍历的顺序为①遍历左子树、②遍历右子树、③访问根

    后根遍历的非递归算法依然需要引入辅助堆栈。但是注意,这里栈的结构与上面的栈结构不同,这里栈的元素为包含Node *int 类型的结构体

    //栈2元素的结构
    struct NodeOfStack{
        Node *pnode;
        int times;//入栈次数
        NodeOfStack():pnode(nullptr),times(0){}
    };

    其中pnode为Node *类型的指针,times记录了该结点入栈的次数 ,times的值可取0,1,2

    栈2的定义如下:

    //栈2
    class Stack2{
    public:
        Stack2():top(0){
            for(int i=0;i<s_size;i++){
                s[i].pnode=nullptr;
                s[i].times=0;
            }
        }
        //入栈
        void push(Node *p,int t){
            if(top<s_size){
                s[top].pnode=p;
                s[top].times=t;
                top++;
            }else{
                cout<<"Stack overflow!"<<endl;
                return;
            }
        }
        //出栈
        NodeOfStack pop(){
            if(top>0){
                top--;
                return s[top];
            }
        }
        bool isEmpty(){
            if(top==0)
                return true;
            else
                return false;
        }
    private:
        const int s_size=20;
        NodeOfStack s[20];
        int top;
    };

    后根遍历的非递归算法:

    1. (root,0)入栈
    2. 判断,如果栈为空,结束算法;否则,栈不为空时:弹栈,记为(p,times)。若times==0,(p,1)入栈,如果p的左儿子存在则(p->left,0)也压入栈。若times==1,(p,2)入栈,如果p的右儿子存在则(p->right,0)也压入栈。若times==2,访问p结点
    3. 返回第2步
    
    /*后根遍历非递归算法*/
    void nPostOrder(Node * root){
        if(root==nullptr){
            return;
        }
        Stack2 s;
        s.push(root,0);
        while(!s.isEmpty()){
            NodeOfStack nos=s.pop();//中间变量,存储每一次栈弹出的数据
            Node *p=nos.pnode;
            if(nos.times==0){
                s.push(nos.pnode,1);
                if(p->left!=nullptr){
                    s.push(p->left,0);
                }
            }else if(nos.times==1){
                s.push(nos.pnode,2);
                if(p->right!=nullptr){
                    s.push(p->right,0);
                }
            }else if(nos.times==2){
                cout<<p->data;
            }
        }
    }

     以下面这棵树为例

    最终输出的后根序列为FDBECA

    展开全文
  • 数据结构二叉树的递归与非递归遍历算法(先序、中序、后序)+层次遍历算法分析与实现。 数据结构二叉树的遍历算法!!!

    文章篇幅有点长,二叉树的递归遍历算法不作详细分析,但是二叉树的非递归遍历算法和层次遍历算法都有非常详细的分析过程记得往下翻哦!

    二叉树的递归遍历算法实现

    我们首先用递归的方法先序遍历创建这样一棵二叉树,如图所示,二叉树创建完毕,我们开始研究二叉树的非递归遍历算法。
    在这里插入图片描述

    1. 算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 1000
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode,*BiTree;
    BiTree creat_BiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')
    	{
    		T= NULL;
    	}
    	else
    	{
    		T = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = creat_BiTree();
    		T->RChild = creat_BiTree();
    	}
    	return T;
    }
    //先序遍历
    int PreOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	printf("%c", pointer->data);
    	PreOrder(pointer->LChild);
    	PreOrder(pointer->RChild);
    }
    //中序遍历
    int InOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	InOrder(pointer->LChild);
    	printf("%c", pointer->data);
    	InOrder(pointer->RChild);
    }
    //后序遍历
    int PostOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	PostOrder(pointer->LChild);
    	PostOrder(pointer->RChild);
    	printf("%c", pointer->data);
    }
    //二叉树的层次遍历
    int Levelprint(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	BiTree a[maxsize];
    	int front = -1;
    	int rear = 0;
    	BiTreeNode* p = pointer;
    	a[rear] = p;
    	while (front != rear)
    	{
    		front++;
    		printf("%c", a[front]->data);
    		if (a[front]->LChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->LChild;
    		}
    		if (a[front]->RChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->RChild;
    		}
    	}
    	return 1;
    }
    //统计二叉树的结点数
    int PreOrder2(BiTree pointer,int *count)
    {
    	if (pointer == NULL) return 0;
    	(*count)++;
    	PreOrder2(pointer->LChild, count);
    	PreOrder2(pointer->RChild, count);
    }
    //统计二叉树非终端结点(分支结点)的个数
    int PreOrder3(BiTree pointer, int* count)
    {
    	if (pointer == NULL) return 0;
    	if (pointer->LChild != NULL||pointer->RChild != NULL)
    	{
    		(*count)++;
    	}
    	PreOrder3(pointer->LChild, count);
    	PreOrder3(pointer->RChild, count);
    }
    //统计二叉树的叶子结点的个数
    int PreOrder4(BiTree pointer, int* count)
    {
    	if (pointer == NULL) return 0;
    	if (!pointer->LChild&&!pointer->RChild)
    	{
    		(*count)++;
    	}
    	PreOrder4(pointer->LChild, count);
    	PreOrder4(pointer->RChild, count);
    }
    //求二叉树的高度
    int BiTree_height(BiTree pointer)
    {
    	int LHeight, RHeight, Tree_Height;
    	if (pointer == NULL) return 0;
    	LHeight = BiTree_height(pointer->LChild);
    	RHeight = BiTree_height(pointer->RChild);
    	Tree_Height = (LHeight > RHeight) ? LHeight + 1 : RHeight + 1;
    	return Tree_Height;
    }
    void main()
    {
    	BiTree T;
    	int count1 = 0,count2=0,count3=0,count4=0;
    	T = creat_BiTree();
    	printf("先序遍历序列:\n");
    	PreOrder(T);
    	printf("\n中序遍历序列:\n");
    	InOrder(T);
    	printf("\n后序遍历序列:\n");
    	PostOrder(T);
    	printf("\n层次遍历序列:\n");
    	Levelprint(T);
    	printf("\n二叉树的结点数为:\n");
    	PreOrder2(T, &count1);
    	printf("%d", count1);
    	printf("\n二叉树的分支结点数为:\n");
    	PreOrder3(T, &count2);
    	printf("%d", count2);
    	printf("\n二叉树的叶子结点数为:\n");
    	PreOrder4(T, &count3);
    	printf("%d", count3);
    	printf("\n二叉树的高度为:\n");
    	count4 = BiTree_height(T);
    	printf("%d", count4);
    }
    

    2. 代码运行结果:
    在这里插入图片描述

    二叉树的非递归遍历算法实现

    我们首先用递归的方法先序遍历创建这样一棵二叉树,如图所示,二叉树创建完毕,我们开始研究二叉树的非递归遍历算法。
    在这里插入图片描述

    一、非递归先序遍历算法

    1.算法实现思路:

    二叉树的先序遍历算法主要思想是:访问根结点,先序遍历左子树,先序遍历右子树。我们可以使用一个栈来实现二叉树的非递归先序遍历算法。首先,创建栈S并对其初始化,栈中的每一个元素是二叉树中的结点。定义指针p开始指向根结点,从根结点开始遍历二叉树中的结点,若结点存在(P!=NULL),输出该结点的值,并将该结点入栈S中,将指针p指向其左孩子(P=P->Lchild),之后判断P指向的结点是否为空,若为空,则从栈中弹出上一结点,并让指针P指向该结点的右孩子( p=pop(s),p = p->RChild),用一个while循环重复以上步骤。直到结点不存在且栈为空结束时循环 while(p || !isempty(s)),二叉树先序遍历遍历结束。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归先序遍历
    void Non_recursive_PREprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p;
    	p = pointer;
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			printf("%c", p->data);
    			push(s, p);
    			p = p->LChild;
    		}
    		else
    		{
    			p = pop(s);
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的先序遍历:\n");
    	Non_recursive_PREprint(T);
    }
    

    3.代码运行结果
    在这里插入图片描述

    二、非递归中序遍历算法

    1.算法思路:

    二叉树的中遍历算法主要思想是:中序遍历左子树,访问根结点,中序遍历右子树。该遍历算法与先序遍历算法思路相似,同样使用一个栈来实现二叉树的非递归中遍历算法。首先,创建栈S并对其初始化,栈中的每一个元素是二叉树中的结点。定义指针p开始指向根结点,从根结点开始遍历二叉树中的结点,若结点存在(P!=NULL),将该结点入栈S中,将指针p指向其左孩子(P=P->Lchild),之后判断P指向的结点是否为空,若为空,则从栈中弹出上一结点,并输出该结点的值,并让指针P指向该结点的右孩子( p=pop(s);printf(“%c”,p->data);p = p->RChild),用一个while循环重复以上步骤。直到结点不存在且栈为空结束时循环 while(p || !isempty(s)),二叉树中序遍历算法结束。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归中序遍历
    void Non_recursive_INprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p;
    	p = pointer;
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			push(s, p);
    			p = p->LChild;
    		}
    		else
    		{
    			p = pop(s);
    			printf("%c", p->data);
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的中序遍历:\n");
    	Non_recursive_INprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    三、非递归后序遍历算法

    1.算法思路:

    二叉树的后序遍历算法的主要思想是:后序遍历左子树,后序遍历右子树,访问根结点。二叉树的非递归后序遍历算法可以构造一栈来实现,栈中的元素存储的是二叉树中的结点,对于后序遍历算法,我们需要判断二叉树中每个结点的左子树是否遍历完,只有将左子树遍历完,我们才能对该结点的右子树和该结点进行遍历输出,我们可以定义一个标志数组int temp[maxsize],先初始化为0,数组元素和栈s中元素对应,栈顶指针top和数组下标对应。首先,先让指针p指向这棵二叉树的根结点,将该结点压入栈s中,同时对其标志数组赋值为0 (tem[s->top]=0),将指针p指向该结点的左孩子(p=p->Lchild),如果其左孩子为空,将栈s的栈顶元素出栈,指针p指向其右孩子,同时将该结点压回栈s中,同时对其标志数组赋值为1 (tem[s->top]=1),表示该结点的左子树已遍历完成, 若该结点的右孩子为空,则对堆栈结点进行遍历,将标志数组tem[s->top]值为1的结点全部打印输出。从二叉树的根结点开始,定一个外部循环,不断重复以上对结点的操作,直到指针p指向的结点为空且栈s中元素为空时结束循环。这就是非递归后续遍历二叉树的主要思路。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归后序遍历
    void Non_recursive_POSTprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p = pointer;
    	int temp[maxsize] = { 0 };
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			push(s, p);
    			temp[s->top] = 0;
    			p = p->LChild;
    		}
    		else
    		{
    			while (temp[s->top] == 1)
    			{
    				p = pop(s);
    				printf("%c", p->data);
    			}
    			if (s->top == -1)
    			{
    				break;
    			}
    			p = pop(s);
    			push(s, p);
    			temp[s->top] = 1;
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的后序遍历: ");
    	Non_recursive_POSTprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    四、二叉树的层次遍历算法

    1.算法思路:

    二叉树的层次遍历算法是指从二叉树的第一层开始,逐层从左到右依次遍历结点,最终将整棵二叉树遍历完成。对于这个算法,我们可以采用队列来实现,我们初始化一个顺序队列,顺序队列的每个元素都存储着二叉树的结点,开始顺序队列为空,首先,将根结点入队,进入循环,将队头指针所指的元素出队,并输出其结点的值,如果该结点的左孩子存在,则将其左孩子入队,如果该结点的右孩子存在,则将右孩子入队,直到队头指针和队尾指针相等时(表明队列为空)退出循环,这颗二叉树的层次遍历就完成了。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的层次遍历
    int Levelprint(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	BiTree a[maxsize];
    	int front = -1;
    	int rear = 0;
    	BiTreeNode* p = pointer;
    	a[rear] = p;
    	while (front != rear)
    	{
    		front++;
    		printf("%c", a[front]->data);
    		if (a[front]->LChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->LChild;
    		}
    		if (a[front]->RChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->RChild;
    		}
    	}
    	return 1;
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的层次遍历为: ");
    	Levelprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    展开全文
  • 创建一棵二叉树,以二叉链表作存储结构,实现先根遍历算法
  • 二叉树的遍历算法

    2022-03-17 15:02:58
    遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序...二叉树常用的遍历方式有:前序遍历、中序遍历、后序遍历、层序遍历四种遍历方式,不同的遍历算法,其思想略有不同,我们来看一下这四种遍...

     遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有节点,使每一个节点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。

                    ​​​​​​​      

                              ​​​​​​​        

    二叉树常用的遍历方式有:前序遍历、中序遍历、后序遍历、层序遍历四种遍历方式,不同的遍历算法,其思想略有不同,我们来看一下这四种遍历方法主要的算法思想:

    1、先序遍历二叉树顺序:根节点 –> 左子树 –> 右子树,即先访问根节点,然后是左子树,最后是右子树。
    上图中二叉树的前序遍历结果为:0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 

     

    2、中序遍历二叉树顺序:左子树 –> 根节点 –> 右子树,即先访问左子树,然后是根节点,最后是右子树。
    上图中二叉树的中序遍历结果为:3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

     

    3、后续遍历二叉树顺序:左子树 –> 右子树 –> 根节点,即先访问左子树,然后是右子树,最后是根节点。
    上图中二叉树的后序遍历结果为:3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

     

    4、层序遍历二叉树顺序:从上往下,从左往右,一层一层遍历,直到所有节点都遍历完成。
    上图中二叉树的层序遍历结果为:0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

     

    代码示例:

    
    typedef struct _Node
    {
    	int data;
    	_Node* lchild;
    	_Node* rchild;
    	_Node()
    	{
    		data = -1;
    	}
    }Node, *pNode;
    
    //前序遍历
    void PreOrderParse(Node* node)
    {
    	if (node == NULL)
    		return;
    
    	cout << node->data;
    	PreOrderParse(node->lchild);
    	PreOrderParse(node->rchild);
    }
    
    //中序遍历
    void InOrderParse(Node* node)
    {
    	if (node == NULL)
    		return;
    
    	PreOrderParse(node->lchild);
    	cout << node->data;
    	PreOrderParse(node->rchild);
    }
    
    //后序遍历
    void PastOrderParse(Node* node)
    {
    	if (node == NULL)
    		return;
    
    	PreOrderParse(node->lchild);
    	PreOrderParse(node->rchild);
    	cout << node->data;
    }
    
    //层序遍历
    void SequenceParse(queue<Node*> que)
    {
    	while (!que.empty()) 
    	{
    		// 得到队头元素并且将队头元素出队列
    		Node* node = que.front();
    		que.pop();  
    		// 如果当前节点不为空,那么输出该节点,并且将该节点的左右子节点插入队尾 
    		if (node != NULL)
    		{
    			cout << node->data << endl;
    			que.push(node->lchild);
    			que.push(node->rchild);
    		}
    	}
    }

    展开全文
  • 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先后指的是访问节点的顺序 eg:先序 左右 中序 左右 后序 左右 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历  a 先访问...
  • 树的遍历算法

    2021-07-12 10:08:47
    树的遍历算法Python实现
  • 图解二叉树先根、根、后根遍历

    千次阅读 2020-09-02 09:23:17
    先根、根、后根遍历 三种遍历都是递归遍历 先根遍历 结果:ABCDEFGH 原理:先遍历根节点,再遍历左子树,最后遍历右子树; 中根遍历 结果:CBEDFAGH 原理:先遍历左子树,再遍历根节点,最后遍历右子树; 后...
  • //先根遍历右子树 } } //中根遍历二叉树的递归算法 public void inRootTraverse(BiTreeNode T) { if(T!=null) { inRootTraverse(T.lchild); //中根遍历左子树 System.out.print(T.data); //访问根...
  • 本文实例讲述了php实现的二叉树遍历算法。分享给大家供大家参考,具体如下: 今天使用php来实现二叉树的遍历 创建的二叉树如下图所示 php代码如下所示: <?php class Node { public $value; public $child_...
  • 二叉树的遍历:指从结点出发,按照某种次序依次访问二叉树所有结点,使得每个结点被访问一次且仅访问一次。 二叉树的遍历方法:1、前序遍历 若二叉树为空,则空操作返回,否则先访问结点,然后前序遍历左子树...
  • 二叉树的层次遍历算法

    千次阅读 2021-10-15 08:03:10
    前面学的二叉树的遍历是把...先将结点入队,接下来就不断从队伍去出队一个结点,同时,如果他有左右孩子,就分别将他的左右孩子入队,这就是访问顺序:首先是结点,然后是他的左右孩子,左右孩子后面是他的左..
  • 前序、中序、后序的非递归遍历中,要数后序最为麻烦,如果只在栈保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈。方法有很多,这里只举一种,先定义栈结点的数据结构 代码如下:typedef struct{...
  • 二叉树遍历算法

    千次阅读 2019-10-27 01:02:12
    前言 二叉树的遍历是指从节点触发,按照某种次序依次访问二叉树所有的节点。 由于不同于线性结构,...下面的遍历算法用Python实现,不会Python的同学不用担心,因为算法逻辑很简单。 先看下我们的节点对象的定...
  • 遍历(Traversal),是指沿着某条搜索路线,依次对树每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 1、二叉树基本结构 struct Node { int value; Node* left; Node* right; ...
  • 二叉树的7种遍历算法

    2020-10-09 00:13:12
    二叉树的7种遍历算法
  • 二叉树的非递归遍历算法

    千次阅读 2020-06-01 15:30:46
    具体算法思想:将二叉树的结点赋值给遍历的指针,若当前节点存在,则输出当前节点的相关数据并做入栈操作(将该节点的地址存入栈),继而访问其左孩子;执行如上操作,直到当前节点为空,做出栈操作并访问其右...
  • 二叉树遍历算法的应用 1.建立二叉链表(在先序遍历基础上) void CreateBiTree(BiTree &T){ //扫描字符序列,读入字符ch cin >> ch; //(if)如果ch为字符#,表明该二叉树为空树,即T为NULL,否则(else)...
  • 目录二叉树各种遍历算法 Java 实现总结0 二叉树简述0.0 概述0.1 分类0.2 数据结构1 二叉树的遍历1.1 前序遍历1.2 中序遍历1.3 后序遍历1.4 层序遍历1.5 小总结 二叉树各种遍历算法 Java 实现总结 0 二叉树简述 0.0 ...
  • C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序、中序、后序的非递归遍历,要数后序最为麻烦,如果只在栈保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈。 方法有很多,这里只举一...
  • 二叉树层次遍历算法

    千次阅读 多人点赞 2020-08-27 01:23:39
    在二叉树,我们常见的遍历方式 主要有四种。分别是: 前序遍历节点->左节点->右节点) 中序遍历(左节点->节点->右节点) 后序遍历(左节点->右节点->节点) 层次遍历 其实记住以上的...
  • 二叉树遍历是非常经典的算法题,也是二叉树的一道基础算法题。 但是在平常的笔试面试,其出现的频率其实并不是特别的高,我推测是这种题目相对来说比较基础,算是一个基础知识点。 比如剑指offer出现的后序遍历...
  • 层序遍历: 从二叉树节点开始,按自上而下、从左到右的顺序进行的遍历。 1. **基本思路**:用队列实现 2. **大致过程**:遍历结点开始,首先将结点入队,然后开始执行循环:结点出队、访问该结点、其左右...
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的节点开始,首先将节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作: 访问该元素所指向的节点 若该元素所指节点的左右孩子...
  • 这篇主要是关于树的前遍历,递归实现和非递归实现两种,现在很多自命题在考算法的时候很喜欢要求同时写出递归和非递归两种实现。最后还有层次遍历的实现。代码实现,试卷上可用,上机运行可以结合注释完善一下。...
  • 从二叉树的递归定义可知,一棵非空的二叉树由结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作: (1)访问结点本身(N), (2)遍历该结点的左子树(L), (3)遍历该...
  • 二叉树遍历算法总结

    万次阅读 多人点赞 2018-09-03 10:40:30
    A. 二叉树的遍历 1.前序遍历二叉树:  (1)若二叉树为空,则为空操作,返回空。  (2)访问结点。... (3)前序遍历左子树。...二叉树前序遍历的递归算法: void PreOrderTraverse(BiTree BT)  {  if(BT)  {  ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 169,402
精华内容 67,760
关键字:

中根遍历的算法