精华内容
下载资源
问答
  • 复制二叉树非递归算法
    2021-05-24 04:49:29

    二叉链表类型定义:

    typedef char TElemType; // 设二叉树的元素为char类型

    typedef struct BiTNode {

    TElemType data;

    BiTNode *lchild, *rchild;

    } BiTNode, *BiTree;可用队列类型Queue的相关定义:

    typedef BiTree QElemType; // 设队列元素为二叉树的指针类型

    Status InitQueue(Queue &Q);

    Status EnQueue(Queue &Q, QElemType e);

    Status DeQueue(Queue &Q, QElemType &e);

    Status GetHead(Queue Q, QElemType &e);

    Status QueueEmpty(Queue Q);实现函数如下:

    void CopyBiTree(BiTree T, BiTree &TT)

    /* 基于层次遍历的非递归复制二叉链表 */

    {

    BiTree p1,p2;

    Queue Q1,Q2;

    if(!T){

    TT = NULL;

    return ;

    }

    TT = (BiTree)malloc(sizeof(BiTNode));

    InitQueue(Q1);

    InitQueue(Q2);

    EnQueue(Q1,T);

    EnQueue(Q2,TT);

    while(!QueueEmpty(Q1)){

    DeQueue(Q1,p1);

    DeQueue(Q2,p2);

    p2 -> data = p1 -> data;

    if(p1 ->lchild){//复制左子树

    EnQueue(Q1,p1 -> lchild);

    p2 -> lchild = (BiTree)malloc(sizeof(BiTNode));

    if(!p2 -> lchild){

    exit(OVERFLOW);

    }

    EnQueue(Q2,p2 -> lchild);

    }

    if(p1 ->rchild){//复制右子树

    EnQueue(Q1,p1 -> rchild);

    p2 -> rchild = (BiTree)malloc(sizeof(BiTNode));

    if(!p2 -> rchild){

    exit(OVERFLOW);

    }

    EnQueue(Q2,p2 -> rchild);

    }

    }

    }

    更多相关内容
  • 编写复制一棵二叉树非递归算法编写复制一棵二叉树非递归算法编写复制一棵二叉树非递归算法编写复制一棵二叉树非递归算法编写复制一棵二叉树非递归算法编写复制一棵二叉树非递归算法编写复制一棵二叉树的...
  • 遍历二叉树非递归算法用到一个栈,而复制的话用到两个栈,一个存被复制二叉树,一个存复制到的二叉树。新的二叉树永远跟着已经存在的二叉树的节奏走,已经存在的那颗二叉树找左结点,新的二叉树也找左结点,已经...

    文章目录

    思路

    怎么写呢?

    就是二叉树遍历的非递归算法,前几篇博文有讲

    后序遍历值得的注意点

    数据结构-二叉树(遍历二叉树的非递归算法)中有讲

    复制的非递归与遍历的非递归的区别

    遍历二叉树的非递归算法用到一个栈,而复制的话用到两个栈,一个存被复制的二叉树,一个存复制到的二叉树。新的二叉树永远跟着已经存在的二叉树的节奏走,已经存在的那颗二叉树找左结点,新的二叉树也找左结点,已经存在的二叉树入栈,新的二叉树也入栈。每次到根结点的时候就进行二叉树结点值的拷贝

    方法的返回

    拷贝方法返回新二叉树的根结点,我们需要在方法最开始把新二叉树的根结点赋值给一个新 Node,因为循环中用的是这个新 Node(存在 Node = Node->left 这样的操作),这样就不会影响最初的那个形参的值,我们最后也就可以大方的return n

    Java 实现

    // 结点
    class Node {
        int data;
        Node left = null;
        Node right = null;
    }
    
    // 二叉树
    public class BinaryTree {
        // 根结点
        private Node root;
        // 输入的数组
        private int[] arr_in;
        // 输出的数组
        private int[] arr_out;
        // 记录数组下标
        private static int index;
        
        // 初始化
        public BinaryTree(int[] arr) {
            root = new Node();
            this.arr_in = arr;
            arr_out = new int[arr.length];
            index = 0;
        }
        
        // 先序复制二叉树(非递归)根→左→右
        public Node preorderCopy(Node r, Node n) {
            Stack rStack = new Stack();
            Stack nStack = new Stack();
            Node rNode = r;
            Node nNode = n;
            while (rNode || !rStack.empty()) {
                if (rNode) {
                    rStack.push(rNode);
                    nNode = new Node();
                    nStack.push(nNode);
                    // 根
                    nNode.data = rNode.data;
                    // 左
                    rNode = rNode.left;
                    nNode = nNode.left;
                }
                else {
                    Node rTop = rStack.pop();
                    Node nTop = nStack.pop();
                    // 右
                    rNode = rTop.right;
                    nNode = nTop.right;
                }
            }
            return n;
        }
    
        // 中序复制二叉树(非递归)左→根→右
        public Node inorderCopy(Node r, Node n) {
            Stack rStack = new Stack();
            Stack nStack = new Stack();
            Node rNode = r;
            Node nNode = n;
            while (rNode || !rStack.empty()) {
                if (rNode) {
                    rStack.push(rNode);
                    nNode = new Node();
                    nStack.push(nNode);
                    // 左
                    rNode = rNode.left;
                    nNode = nNode.left;
                }
                else {
                    Node rTop = rStack.pop();
                    Node nTop = nStack.pop();
                    // 根
                    nTop.data = rTop.data;
                    // 右
                    rNode = rNode.right;
                    nNode = nNode.right;
                }
            }
            return n;
        }
        
        // 后序复制二叉树(非递归)左→右→根
        public Node postorderCopy(Node r, Node n) {
            Stack rStack = new Stack();
            Stack nStack = new Stack();
            Node rNode = r;
            Node nNode = n;
            Node rTop;
            Node nTop;
            while (rNode || !rStack.empty()) {
                if (rNode) {
                    rStack.push(rNode);
                    rNode = new Node();
                    rStack.push(rNode);
                    // 左
                    rNode = rNode.left;
                    nNode = nNode.left;
                }
                else {
                    if (rStack.peek().right != null && rStack.peek().right != rTop) {
                        // 右
                        rNode = rNode.right;
                        nNode = nNode.right;
                    }
                    else {
                        rTop = rStack.pop();
                        nTop = nStack.pop();
                        // 根
                        nTop.data = rTop.data;
                        rNode = rStack.peek();
                        nNode = nStack.peek();
                    }
                }
            }
            return n;
        }
    }
    
    展开全文
  • //找某个结点的祖先结点方法:对二叉树进行【中】序遍历,当扫描到该结点时,栈中的结点都是祖先结点 //为方便测试,假设各个结点值均不相同 int find_ancestors ( BTNode * bt , int x , BTNode * stack ...

    好像有点问题。。。但是用测试代码测试 find_ancestors 函数时候,结果没有问题啊?为啥回到main里之后就弄不出来了。。。?

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct BTNode
    {
        int data;
        struct BTNode *left, *right;
    }BTNode;
    
    BTNode *creat_tree()
    {
        BTNode *t = NULL;
        int x;
        //printf ("正在建立一个新二叉树,请输入结点的值:");
        scanf ("%d", &x);
        if (x == 0)   return NULL;
        else
        {
            t = (BTNode *) malloc (sizeof(BTNode));
            t -> data = x;
            t -> left = creat_tree();
            t -> right = creat_tree();
        }
        return t;
    }
    
    //找某个结点的祖先结点方法:对二叉树进行【中】序遍历,当扫描到该结点时,栈中的结点都是祖先结点
    //为方便测试,假设各个结点值均不相同
    
    int find_ancestors(BTNode *bt, int x, BTNode *stack[]) //原本 【int x】 应为【BTNode *p】
    {   
        int top = -1;
        if (bt != NULL)
        {   
            BTNode *q = bt;        //q为工作指针,用于中序遍历
            while(q != NULL || top != -1)
            {   
                while (q!=NULL && q->data != x)
                {
                    stack[++top] = q;
                    q=q->left;
                }
                if (q->data == x)
                    return top;
                else
                {
                     if (top != -1)
                    {
                        q = stack[top--];
                        q = q->right;
                    }
                }
               
                
            }
            
        }   
        return top;
    }
    
    
    int main()
    {
        BTNode *tree = creat_tree();
        int px=0, qx=0;
        printf("请输入待操作的结点p的结点值:");
        scanf("%d", &px);
        printf("请输入待操作的结点q的结点值:");
        scanf("%d", &qx);
        
        BTNode *stack1[100];    int top1;
        BTNode *stack2[100];    int top2;
        
        top1 = find_ancestors(tree, px, stack1);
        top2 = find_ancestors(tree, qx, stack2);
        
        
        for (int i = top1; i>=0; --i)
        {   
            printf("%d", stack1[i]->data);
            for (int j = top2; j>=0; --j)
            {
                printf("%d", stack2[j]->data);
                if (stack1[i]->data == stack2[j]->data)
                    printf("%d", stack1[i]->data);
                    break;
            }
        }
        return 0;
    }
    
    
    //用于测试 find_ancestors函数是否正确,可删掉
    /*
    int main()
    {
        BTNode *tree = creat_tree();
        BTNode *stack[100];
        int x=0;
        printf("请输入待操作的结点的值:");
        scanf("%d", &x);
        int top = find_ancestors(tree, x, stack);
        
        for (int i=0; i<=top; ++i)
            printf("%d\n", stack[i]->data);
    
        return 0;
    }
    
    */
    
    展开全文
  • 本文针对二叉树的先序建立过程给出了详细的实现过程,包括非递归算法和递归算法两种不同的实现模式。所谓的先序法,就是按照先序遍历二叉树的流程创建二叉树。使用的二叉树数据如下图所示。本文给出了C语言版本的...

    一、引言
    二叉树是一种非常重要的非线性数据结构,在信号处理、移动通讯等应用中均有重要的应用。
    在二叉树的应用中,首先要建立二叉树。本文针对二叉树的先序建立过程给出了详细的实现过程,包括非递归算法和递归算法两种不同的实现模式。所谓的先序法,就是按照先序遍历二叉树的流程创建二叉树。使用的二叉树数据如下图所示。本文给出了C语言版本的先序创建二叉树的非递归算法。
    在这里插入图片描述

    二、二叉树的创建-先序法
    按照算法的具体实现细节,要求对原二叉树的结点进行补充空结点。具体补充结果下图所示,其中黄色结点是二叉树的结点,蓝色结点是扩充的结点,仅仅是为了算法实现方便实现而已。最终创建的二叉树还是如上图所示,遍历也是根据上图进行遍历。
    在这里插入图片描述
    1、算法的基本思路(有点复杂,可以参考后面的详细步骤理解):
    为了能够确定新读入的结点链接到当前结点(双亲)的左子树还是右子树,引入了链接标志flag,其初始值为假。flag值为真,则表示需将新读入的结点s插入当前结点(双亲)p的右子树,否则插入p的左子树。
    具体步骤主要包括如下三步:
    (1) 如果新读入的数据非空,当flag值为假时,将新读入的结点链接到当前结点(双亲)p的左子树,同时当前结点(双亲)p入栈(作为待插入的右子树的双亲结点),然后把新读入的结点作为当前结点(双亲)p。当flag值为真时,将新读入的结点链接到当前结点(双亲)p的右子树,并将flag置为假;
    (2) 如果新读入的数据为空,且flag为真,则栈顶元素出栈;
    (3) 如果新读入的数据为空,且flag为假,则继续读入数据,此时数据若非空,则建立新结点s,并链接到当前结点的右子树,同时将当前结点(双亲)p指向s;若为空数据,则栈顶结点出栈给p,同时flag值置为1,表示左子树已经处理完毕,再读入新结点则放到双亲的右子树。若栈为空,则结束二叉树的创建。
    2、创建二叉树的详细步骤示例:
    有图有真相。
    按照图(2)所示,使用先序法创建二叉树,需要读入的数据依次为:
    在这里插入图片描述
    (1)读入a,二叉树、栈的状态、flag的值:
    在这里插入图片描述
    (2)读入b,二叉树、栈的状态、flag的值:

    在这里插入图片描述
    (3)读入d,二叉树、栈的状态、flag的值:
    在这里插入图片描述
    (4)读入一个?,二叉树、栈和flag值都没有发生改变
    (5)再读入一个?,二叉树、栈的状态、flag的值:
    在这里插入图片描述

    (6)读入e,二叉树、栈的状态、flag的值:
    在这里插入图片描述

    (7)读入g,二叉树、栈的状态、flag的值:
    在这里插入图片描述
    (8)读入一个?,二叉树、栈和flag值都没有发生改变
    (9)再读入一个?,二叉树没变,指针p位置变了,栈顶元素出栈
    在这里插入图片描述
    (10)再读入一个?,二叉树不变、栈顶元素出栈,flag值仍为1

    在这里插入图片描述

    (11)读入c,二叉树、栈的状态、flag的值:
    在这里插入图片描述
    (12)读入一个?,二叉树、栈和flag值都没有发生改变
    (13)读入f,二叉树、栈的状态、flag的值:
    在这里插入图片描述

    (14)读入一个?,二叉树、栈和flag值都没有发生改变
    (15)读入h,二叉树、栈的状态、flag的值:
    在这里插入图片描述
    (16)读入一个?,二叉树、栈和flag值都没有发生改变
    (17)再读入一个?,由于此时栈已经为空,所以创建二叉树的过程结束。
    三、创建二叉树的代码:
    注:在只有创建二叉树的前提下检验创建结果是否正确,可以在创建的过程中增加打印结点与双亲之间关系的语句。
    1)宏定义及结点存储结构

    #include"stdio.h"
    #include"malloc.h"
    //根据结点数据的类型定义空数据为‘?’或者 0
    #ifdef CHAR
    #define NULLKEY '?'
    #else
    #define NULLKEY 0
    #endif
    //根据字符型数据或者整型数据定义结点数据类型
    #ifdef CHAR
    typedef char datatype;
    #else
    typedef int datatype;
    #endif
    #define MAX_NODE 100
    //定义存储结点的结构体类型
    typedef struct node
    {
    	datatype data;
    	struct node *Lchild;
    	struct node *Rchild;
    }BiTree;
    

    2)创建二叉树的函数

    /************************************************************************
    //先序创建二叉树:非递归算法。
    //输入参数:无
    //返回值:  树根
    //说明:1.所有的叶子结点、分支不完整的结点,都要进行扩充,扩充方式为:
    			字符型结点:扩充‘?’
    			整型结点:  扩充‘0’,也可根据实际情况调整
    		2.在输入数据时,应该按照扩充后的二叉树的先序遍历序列进行输入
    		3.示例 
    		a b d ? ? e g ? ? ? c ? f ? h ? ?
    		1 2 4 0 0 5 3 0 0 0 6 0 7 0 8 0 0
    ************************************************************************/
    BiTree *CreatBiTtreePreorder() {
    	BiTree *T, *s, *p, *stack[MAX_NODE];
    	datatype x;
    	int top = 0;
    	int flag  = 0;
    
    #ifdef CHAR
    	printf( "\n请输入字符,以 ? 作为每个节点的结束标志:" );
    	scanf( "%c",&x );
    	getchar();//过滤空格或者换行符 
    #else
    	printf( "\n请输入正整数以0作为结束标志:" );
    	scanf( "%d",&x );
    #endif
    //创建树根
    	if( x == NULLKEY ) {
    		T = NULL;
    		return T;
    	}	
    	T = ( struct node * )malloc( sizeof(BiTree) );
    	T->data   = x;
    	T->Lchild = NULL;
    	T->Rchild = NULL;
    
    	p = T;
    	while( 1 )
    	{
    	#ifdef CHAR
    		scanf( "%c",&x );
    		getchar();//过滤空格或者换行符
    	#else
    		scanf( "%d",&x );
    	#endif
            //(1)如果新读入的数据非空
    		if( x != NULLKEY ) {
    			s = ( struct node * )malloc( sizeof(BiTree) );
    			s->data   = x;
    			s->Lchild = NULL;
    			s->Rchild = NULL;
    			if( flag == 1 ) {//flag为真,则链接到右子树
    				p->Rchild = s;
    				flag = 0;
    #ifdef CHAR
    				printf( " %c is %c \' R \n", x, p->data );
    #else
    				printf( " %d is %d \' R \n", x, p->data );
    #endif
    			}
    			else {//flag为假,则链接到左子树
    				p->Lchild = s;
    				stack[ top++ ] = p;//双亲压栈
    #ifdef CHAR
    				printf( " %c is %c \' L \n", x, p->data );
    #else
    				printf( " %d is %d \' L \n", x, p->data );
    #endif
    			}
    			p = s;
    		}
            //(2)如果新读入数据为空,且flag为真,则弹栈
    		else if( x == NULLKEY && flag == 1 ) {
    			if( top > 0 )
    		    {
    		    	p = stack[ --top ];//弹栈
    			}
    			else
    				break;
    		} 
    //(3)如果新读入数据为空,且flag为假,则继续读入结点数据
    		else	{
    #ifdef CHAR
    			scanf( "%c",&x );
    			getchar();//过滤空格或者换行符
    #else
    			scanf( "%d",&x );
    #endif
                //第一次读入数据为空,第二次非空,链接到右子树
    			if( x != NULLKEY ) {
    				s = ( struct node * )malloc( sizeof(BiTree) );
    				s->data   = x;
    				s->Lchild = NULL;
    				s->Rchild = NULL;
    				p->Rchild = s;
    #ifdef CHAR
    				printf( " %c is %c \' R \n", x, p->data );
    #else
    				printf( " %d is %d \' R \n", x, p->data );
    #endif
    				p = s;		
    		    }
    //第一次读入数据为空,第二次为空,栈非空则弹栈,且flag置为真
    		    else {
    		    	if( top > 0 )
    		    	{
    		    		p = stack[ --top ];
    		    		flag = 1;
    				}
    				else// 栈空则结束创建
    					break;
    			}	
    		}
    	}
    	return( T );
    }
    

    3)主函数及运行结果

    int main()
    {
    	
    	BiTree *bintree;
    	bintree = CreatBiTtreePreorder();
    	return 0;
    }
    

    在这里插入图片描述

    展开全文
  • 二叉树非递归遍历算法(先序,中序,后序,层次)
  • (※)中序遍历二叉树非递归算法

    千次阅读 多人点赞 2020-05-06 17:31:32
    在此之前,我们已经学习了中序遍历二叉树递归算法,相信大家已经将其牢牢掌握了. 除了使用递归思想作为求解问题的钥匙,还可以借助栈来以非递归方式实现该问题的求解. 首先,我们要讨论存储二叉树结点信息的栈...
  • 二叉树非递归算法(C++实现)

    千次阅读 2018-08-04 01:05:09
    接着上面一篇博客,我们开始叙述有关二叉树非递归遍历...首先是二叉树的中序遍历,这是二叉树尤为重要的一种遍历方式,虽然它在三种非递归方式中是最简单的,但是很多算法都是基于这种方法进行再创作。 //中序遍...
  • 编写复制一颗二叉树非递归算法

    千次阅读 2013-11-28 10:39:19
    问题描述:设栈的类型为seqstack,initstack(s)为对栈s初始化。 基本思路:用两个栈保存左右树访问的节点,每次访问根后PUSH一下,然后pop出继续保存左右子树。 ...// CopyBinaryTrees.cpp : 定义控制台应用程序...
  • 以下主要分析二叉树复制、销毁、以及但含有递归思想的非递归遍历方法。 1 二叉树节点构建,与前文一致,不再分析 typedef struct Tree //二叉树 { void *data; //数据域,void* 可保存任意数据类型的地址 ...
  • 二叉树的前中后序递归以及非递归算法以及层序遍历思想做了整合 因为某些书籍上对这类算法,写的非常笼统,所以,这里将从树的链式存储开始,结合整个 链表、栈、队列等结构来完成对树的学习,当然,这里也将会完美...
  • 非递归实现基本思想: 受后续遍历二叉树思想的启发,想到可以利用后续遍历的方法来求二叉树的深度,在每一次输出的地方替换成算栈S的大小,遍历结束后最大的栈S长度即是栈的深度。 算法的执行步骤如下: ...
  • 复制二叉树非递归实现)

    千次阅读 2013-01-15 19:32:07
    pbinary_tree_node copy_binary_tree(pbinary_tree_node bt) {//先序遍历输出一颗树的...这个算法使用了两个栈,一个栈用来遍历原来的二叉树,另一个栈一边创建新的二叉树,一边同第一个栈同步,保存遍历时的轨迹。
  • 二叉树递归算法(先序,中序,后序)以及结点数,叶子结点数和深度,树的深度
  • 本文使用C语言完整实现二叉树非递归先序、中序、后序遍历。 以下是原递归算法二叉树的先序、中序、后序遍历的递归实现算法): // 1.先序递归实现算法 void PreOrder(BiTree T) { if (T != NULL) { visit(T);...
  • 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。...在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。 一.前序遍历 前序遍历按
  • 二叉树的遍历可以分为前序、中序、后序、层次遍历。前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中—>左—>右;中序遍历,遍历节点的顺序为:左—>中—>右;后序遍历,遍历节点的顺序为...
  • 二叉树非递归后序遍历(双栈法和双指针法,有图有真相)
  • 汉诺塔问题的递归程序很简单,也很容易理解,C源程序如下。 // 程序1 #include <stdio.h> int n; void move(int k, char from, char to) { static int Ser_num; Ser_num++; printf("%3d k=%2d %c-->%c...
  • 【4】非递归算法计算T中的叶子数 【5】用递归算法计算T中度为1的结点数 【1】求二叉树的深度 //求二叉树的深度 private static int high(btnode T) { if(T==null) return 0; else return Math....
  • 二叉树相关操作的实现(先序、中序、后序遍历,递归及非递归算法实现,深度,结点数,叶子结点数等代码实现) 以下是源代码: #include&lt;stdio.h&gt; #include&lt;malloc.h&gt; #include&...
  • void CopyBiTree(BiTree T, BiTree &TT) /* 基于层次遍历的非递归复制二叉链表 */ { QElemType p;Queue t2,tt2; InitQueue(t2); InitQueue(tt2); if(!T)TT=NULL; else { EnQueue(t2,T); if(!(TT=(BiTNode*)malloc...
  • LinkedStack2 队列的链式存储结构实现-LinkedQueue3 二叉树的链式存储结构实现3.1 树的结点定义-TreeNode3.2 二叉树定义3.3 前中后序遍历-递归算法实现3.4 前中后序遍历-非递归算法实现3.5 层序遍历算法实现4 代码...
  • } //中序遍历非递归算法 void SimInorder(BTNode *t){ if(!t) cout空二叉树"; stack*> S; while(t||!S.empty()){ if(t){ S.push(t); t=t->lchild; } else{ t=S.top(); S.pop(); cout...
  • 递归计算二叉树的高度Previously I wrote about an algorithm for finding out the height of a binary tree using iteration. Though that method gets the job done (in 7 steps no less), the same can be ...
  • C语言-数据结构-二叉树的递归遍历和非递归遍历

    千次阅读 多人点赞 2018-08-16 09:05:23
    看了大量网络相关的理论和程序,... 最值得研究的还是后序遍历的非递归算法, 当时想了使用flag, 想到了多用一个栈, 想到了很多种方式,最后都以失败告终,经过网络查找, 感谢 https://www.cnblogs.com/rain-lei/p/3...
  • 使用栈非递归实现复制二叉树

    千次阅读 2013-11-27 10:17:43
    void BiTreeCopy_Stack(BTree *root, BTree * ©root) //非递归复制二叉树,将root复制到copyroot { /*指针与引用的区别 指针:存放变量地址的一个变量,逻辑上是独立的,它可以被改变。 引用:是一个别名,逻辑...
  • 二叉树的拷贝构造函数(递归与非递归

    千次阅读 多人点赞 2019-10-27 22:22:17
    二叉树是数据结构中非常重要的一章,与之前的数组、链表之类的靠循环的章节在难度上有了一个小的飞跃,这是因为二叉树要用到很多关于递归算法。但是二叉树真的难的地方并不是递归,而是如何不用递归(用栈)来实现...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,698
精华内容 5,879
热门标签
关键字:

复制二叉树非递归算法