精华内容
下载资源
问答
  • 二叉树先序中序递归与迭代遍历实现 代码 #include <stdio.h> #include <stdlib.h> typedef struct BINARYNODE { char ch; struct BINARYNODE *lchild; struct BINARYNODE *rchild; }BinaryNode; //...

    二叉树先序中序递归与迭代遍历实现

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BINARYNODE
    {
    	char ch;
    	struct BINARYNODE *lchild;
    	struct BINARYNODE *rchild;
    }BinaryNode;
    
    //先序(递归)
    void Recursion1(BinaryNode *root)
    {
    	if(root == NULL)
    	{
    		return;
    	}
    	printf("%c",root->ch);
    	Recursion(root->lchild);
    	Recursion(root->rchild);
    }
    //先序(非递归) 
    void Porderf(BinaryNode *root)
    {
    	int top=0; 
    	BinaryNode *p, *s[10];
    	p=root;
    	while (p || top)
    	{
    		while (p!=NULL)
    		{
    			printf("%c\t",p->ch);
    			s[top++]=p;
    			p=p->lchild;
    		}
    		if(top>0)
    		{
    			p=s[--top];
    			p=p->rchild;
    		}
    	}
    }
    //中序(非递归) 
    void inorderf(BinaryNode *root)
    {
    	int top=0; 
    	BinaryNode *p, *s[10];
    	p=root;
    	while (p || top)
    	{
    		while (p!=NULL)
    		{
    			s[top++]=p;
    			p=p->lchild;
    		}
    		if(top>0)
    		{
    			p=s[--top];
    			printf("%c",p->ch);
    			p=p->rchild;
    		}
    	}
    }
    //中序(递归) 
    void Recursion2(BinaryNode *root)
    {
    	if(root == NULL)
    	{
    		return;
    	}
    	Recursion(root->lchild);
    	printf("%c",root->ch);
    	Recursion(root->rchild);
    }
    
    void CreateBinaryTree()
    {
    	BinaryNode node1 = {'A',NULL,NULL};
    	BinaryNode node2 = {'B',NULL,NULL};
    	BinaryNode node3 = {'C',NULL,NULL};
    	BinaryNode node4 = {'D',NULL,NULL};
    	BinaryNode node5 = {'E',NULL,NULL};
    	BinaryNode node6 = {'F',NULL,NULL};
    	BinaryNode node7 = {'G',NULL,NULL};
    	BinaryNode node8 = {'H',NULL,NULL};
    	
    	node1.lchild = &node2;
    	node1.rchild = &node6;
    	node2.rchild = &node3;
    	node3.lchild = &node4;
    	node3.rchild = &node5;
    	node6.rchild = &node7;
    	node7.lchild = &node8;
    	
    	Porderf(&node1);//先序(递归)
    //	Recursion1(&node1);//先序(非递归) 
    //	inorderf(&node1);//中序(非递归)
    //	Recursion2(&node1);//中序(递归)
    }
    
    int  main()
    {
    	CreateBinaryTree();
    	return 0;
    }
    
    

    二叉树参考
    在这里插入图片描述

    展开全文
  • 数据结构二叉树——编写函数实现:建立二叉树、中序递归遍历、借助栈实现中序非递归遍历、借助队列实现层次遍历、求高度、结点数、叶子数及交换左右子树。("."表示空子树)#include #include //***********二叉树链表...

    数据结构二叉树——

    编写函数实现:建立二叉树、中序递归遍历、借助栈实现中序非递归遍历、借助队列实现层次遍历、求高度、结点数、叶子数及交换左右子树。

    ("."表示空子树)

    #include<stdio.h>
    #include<stdlib.h>
    //***********二叉树链表节点结构
    typedef char DataType;
    
    typedef struct Node
    {
     DataType data;
     struct Node*LChild;
     struct Node*RChild;
    }BiTNode,*BiTree;
    
    void Insert_tree(BiTree *T)
    {
     char ch;
     ch = getchar();
     if (ch == '.')//"."表示空子树
      *T = NULL;
     else 
     {
      *T = (BiTree)malloc(sizeof(BiTNode));
      (*T)->data = ch;
      Insert_tree(&((*T)->LChild));
      Insert_tree(&((*T)->RChild));
     }
    }
    
    //*************二叉树的中序递归遍历
    void InOrder(BiTree root)
    {
     if (root != NULL)
     {
      InOrder(root->LChild);
      printf("%c ",root->data);
      InOrder(root->RChild);
     }
    }
    //****************二叉树的中序非递归遍历算法(调用栈操作)
    #define Stack_Size 50
    
    typedef struct //顺序栈结构
    {
     BiTree elem[Stack_Size];
     int top;   //用来存放栈顶元素的下标,top为-1表示空栈
    }SeqStack;
    
    void InitStack(SeqStack *S)// 顺序栈初始化
    {
     S->top = -1;  //制造一个空栈
    }
    
    int Push(SeqStack *S, BiTree x)  //顺序进栈
    {
     if (S->top == Stack_Size - 1)
      return 0;  //栈已满
     S->top++;
     S->elem[S->top] = x;
     return 1;
    }
    
    int Pop(SeqStack * S, BiTree *x)//顺序出栈
    {
     if (S->top == -1)  //栈为空
      return 0;
     else
     {
      *x = S->elem[S->top];
      S->top--;
      return 1;
     }
    }
    
    int IsEmpty(SeqStack *s)
    {
     return s->top == -1 ? 0 : 1;
    }
    
    void InOrder_2(BiTree root)   //二叉树的中序非递归遍历
    {
     BiTree p;
     SeqStack S;
     InitStack(&S);
     p = root;
     while (p != NULL|| IsEmpty(&S))
     {
      if (p != NULL)
      {
       Push(&S, p);
       p = p->LChild;
      }
      else
      {
       Pop(&S,&p);
       if(p != NULL)
       printf("%c ", p->data);
       p = p->RChild;
      }
     }
    }
    
    //***********************借助队列实现二叉树的层次遍历
    #define MAXSIZE 50
    typedef struct
    {
     BiTree element[MAXSIZE];
     int front;
     int rear;
    }SeqQueue;
    
    void InitQueue(SeqQueue *Q)//循环队列初始化
    {
     Q->front = 0;
     Q->rear = 0;
    }
    
    int EnterQueue(SeqQueue *Q,BiTree x) //循环队列入队
    {
     if ((Q->rear + 1) % MAXSIZE == Q->front)
      return 0;
     Q->element[Q->rear] = x;
     Q->rear = (Q->rear + 1) % MAXSIZE;
     return 1;
    }
    
    int IsEmpty_Q(SeqQueue *Q)//判断是否为空
    {
     return(Q->rear == Q->front) ? 0 : 1;
    }
    
    int EeleteQueue(SeqQueue *Q,BiTree *x)  //循环队列出队
    {
     if (Q->front == Q->rear)
      return 0;
     *x = Q->element[Q->front];
     Q->front = (Q->front + 1) % MAXSIZE;
     return 1;
    }
    
    int Layer_Order(BiTree root)
    {
     SeqQueue Q;
     BiTree p;
     InitQueue(&Q);
     if (root == NULL)
      return 0;
     EnterQueue(&Q, root);
     while (IsEmpty_Q(&Q))
     {
      EeleteQueue(&Q,&p);
      printf("%c ", p->data);
      if(p->LChild)
      EnterQueue(&Q,p->LChild);
      if(p->RChild)
      EnterQueue(&Q,p->RChild);
     }
     return 1;
    }
    
    //***********************二叉树的高度(后序遍历)
    int PostTreeDepth(BiTree bt)
    {
     int hl, hr, max;
     if (bt != NULL)
     {
      hl = PostTreeDepth(bt->LChild);
      hr = PostTreeDepth(bt->RChild);
      max = hl > hr ? hl : hr; //使用三目运算符 为书写方便
      return (max + 1);
     }
     else
      return 0;
    }
    //***********************二叉树的结点个数
    
    int Order(BiTree root)
    {
     static int ordercount = 0;//static 定义静态变量,在静态区存储,程序运行结束释放,用于实现在原先基础上加“1”,实现统计数字的效果(与下文运用全局变量目的一致)
     if (root != NULL)
     {
      ordercount++;
      Order(root->LChild);
      Order(root->RChild);
     }
     return ordercount;
    }
    
    //***********************二叉树的叶子个数
    int LeafCount = 0;//定义全局变量,它的内存在程序执行完之后才释放,用于实现在原先基础上加“1”,实现统计数字的效果
    void leaf(BiTree root)  //后序遍历统计叶子结点数目
    {
     //int LeafCount = 0;
     if (root != NULL)
     {
      leaf(root->LChild);
      leaf(root->RChild);
      if ((root->LChild == NULL) && (root->RChild == NULL))
       LeafCount++;
     }
     //return LeafCount;
    }
    //***********************交换二叉树每个结点的左子树和右子树
    void Exchange(BiTree root)
    {
     BiTree temp = NULL;
     if (root != NULL)
     {
      temp = root->LChild;
      root->LChild = root->RChild;
      root->RChild = temp;
      Exchange(root->LChild);
      Exchange(root->RChild);
     }
    }
    
    void menu()
    {
     printf("***********************************************\n");
     printf("*                  MENU                       *\n");
     printf("***********************************************\n");
     printf("* 1.输入字符序列,建立二叉树的二叉链表   *\n");
     printf("* 2.二叉树的中序递归遍历                *\n");
     printf("* 3.二叉树的中序非递归遍历              *\n");
     printf("* 4.借助队列实现二叉树的层次遍历        *\n");
     printf("* 5.求二叉树的高度                      *\n");
     printf("* 6.求二叉树的结点个数                  *\n");
     printf("* 7.求二叉树的叶子个数                  *\n");
     printf("* 8.交换二叉树每个结点的左子树和右子树  *\n");
     printf("* 0.退出                                *\n");
     printf("***********************************************\n");
     printf("***********************************************\n");
     printf("请输入选择序号:->");
    }
    
    int main()
    {
     int choose = 1;
     BiTree TT = NULL;
     while (choose)
     {
      menu();
      scanf_s("%d", &choose);
      getchar();//为不影响二叉树的输入,将输入缓存中的回车(\n)取出
      switch (choose)
      {
      case 1:
       Insert_tree(&TT);
       break;
      case 2:
       InOrder(TT);
       printf("\n");
       break;
      case 3:
       InOrder_2(TT);
       printf("\n");
       break;
      case 4:
       Layer_Order(TT);
       printf("\n");
       break;
      case 5:
       printf("高度 = %d\n",PostTreeDepth(TT));
       break;
      case 6:
       printf("节点个数 = %d \n",Order(TT));
       break;
      case 7:
       leaf(TT);
       printf("叶子个数 = %d\n", LeafCount);
       break;
      case 8:
       Exchange(TT);
       InOrder(TT);
       printf("\n");
       break;
      default:
       break;
      }
     }
     system("pause");
     return 0;
    }

    650) this.width=650;" title="1" style="float:none;" alt="wKiom1ZYnovBCZaUAABBH6tMzUY685.png" src="http://s3.51cto.com/wyfs02/M02/76/AD/wKiom1ZYnovBCZaUAABBH6tMzUY685.png" />

    650) this.width=650;" title="2" style="float:none;" alt="wKiom1ZYnoyDPSEQAAA4oiJsLxE546.png" src="http://s2.51cto.com/wyfs02/M01/76/AD/wKiom1ZYnoyDPSEQAAA4oiJsLxE546.png" />

    650) this.width=650;" title="3" style="float:none;" alt="wKioL1ZYnu2gyBeQAAA8vXmRBmk651.png" src="http://s2.51cto.com/wyfs02/M02/76/AC/wKioL1ZYnu2gyBeQAAA8vXmRBmk651.png" />

    650) this.width=650;" title="4" style="float:none;" alt="wKiom1ZYno3wdp2nAAA2RLmk5y8571.png" src="http://s2.51cto.com/wyfs02/M00/76/AD/wKiom1ZYno3wdp2nAAA2RLmk5y8571.png" />

    650) this.width=650;" title="5" style="float:none;" alt="wKiom1ZYno3DInoiAAAot-rzufg582.png" src="http://s1.51cto.com/wyfs02/M01/76/AD/wKiom1ZYno3DInoiAAAot-rzufg582.png" />

    650) this.width=650;" title="6" style="float:none;" alt="wKiom1ZYno7BCmj-AAAoiiUJhEA414.png" src="http://s1.51cto.com/wyfs02/M00/76/AD/wKiom1ZYno7BCmj-AAAoiiUJhEA414.png" />

    650) this.width=650;" title="7" style="float:none;" alt="wKioL1ZYnu7xLqx4AAAop0JJB98011.png" src="http://s3.51cto.com/wyfs02/M02/76/AC/wKioL1ZYnu7xLqx4AAAop0JJB98011.png" />

    650) this.width=650;" title="8" style="float:none;" alt="wKioL1ZYnu_xIEh9AAAoun43vMA904.png" src="http://s3.51cto.com/wyfs02/M02/76/AC/wKioL1ZYnu_xIEh9AAAoun43vMA904.png" />


    展开全文
  • (二)二叉树中序递归遍历: void InoderTraverseTree_Recur(TreeNode *root) { if(NULL == root) return; InoderTraverseTree_Recur(root->left); std::cout << root->val ; InoderTraverseTree_Recur...

    二叉树如下:


    二叉树前序序列化表示如下:

    1 2 4 7 -1 -1 8 -1 -1 5 -1 -1 3 6 -1 -1 -1

    -1代表左右子树为NULL的情况,使用前序序列构造二叉树。

    二叉树结构体表示如下:

    struct TreeNode{
    	TreeNode(int value):left(NULL),right(NULL),val(value){   }
    	TreeNode *left;
    	TreeNode *right;
    	int val;
    };

    (一)二叉树中序非递归遍历:

    二叉树中序遍历,使用栈来模拟,与前序非递归遍历的唯一区别在于,打印当前结点值的位置不同

    void InoderTraverseTree(TreeNode *root)
    {
    	if(root == NULL) return;
    	stack<TreeNode*> s;
    	s.push(root);
    	TreeNode *curnode = NULL;
    	while(!s.empty()){	
    		while(curnode = s.top()) s.push(curnode->left);
    		s.pop();
    		if(!s.empty()){
    			curnode = s.top();
    			s.pop();
    			std::cout << curnode->val << " ";    //中序在此打印
    			s.push(curnode->right);
    		}
    	}
    }

    (二)二叉树中序递归遍历:

    void InoderTraverseTree_Recur(TreeNode *root)
    {
    	if(NULL == root) return;
    	InoderTraverseTree_Recur(root->left);
    	std::cout << root->val << " ";
    	InoderTraverseTree_Recur(root->right);
    }

    调用函数:

    int main(void)
    {
    	TreeNode *root = NULL;
    	//先序建立一棵树
    	PreoderBuildTree(root);
    	//中序非递归遍历
    	InoderTraverseTree(root);
    	std::cout << std::endl;
    	//中序递归遍历
    	InoderTraverseTree_Recur(root);
    	std::cout << std::endl;
    }



    展开全文
  • printf("中序递归:"); InOrderTraverse(root); printf("\r\n"); printf("后序递归:"); PostOrderTraverse(root); printf("\r\n前序非递归:"); NonRecursionPreOrder(root); printf("\r\n"); printf...
    #include <iostream>
    #include <stack>
    using namespace std;
    
    int preOrder[] = {10, 6, 4, 8, 14, 12, 16};
    int inOrder[] =  {4, 6, 8, 10, 12, 14, 16};
    
    //int preOrder[] = {1, 2, 3, 4,5 , 6};
    //int inOrder[] =  {1, 2, 3, 4, 5, 6};
    
    typedef struct Node_
    {
    	Node_ * left, * right;
    	int data;
    	bool visit;
    }Node;
    
    //递归前序遍历
    void preTraverse(Node * root)
    {
    	if(!root)
    	{
    		return;
    	}
    
    	printf("%d ", root->data);
    	preTraverse(root->left);
    	preTraverse(root->right);
    }
    
    //递归中序遍历
    void InOrderTraverse(Node * root)
    {
    	if(!root)
    	{
    		return;
    	}
    
    
    	InOrderTraverse(root->left);
    	printf("%d ", root->data);
    	InOrderTraverse(root->right);
    }
    
    //递归后序遍历
    void PostOrderTraverse(Node * root)
    {
    	if(!root)
    	{
    		return;
    	}
    
    	PostOrderTraverse(root->left);
    	PostOrderTraverse(root->right);
    	printf("%d ", root->data);
    }
    
    //非递归中序排序
    void NonRecursionInOrder(Node * root)
    {
    	if(!root)
    	{
    		return;
    	}
    	stack<Node*> st;
    	st.push(root);
    
    	while(!st.empty())
    	{
    		Node * top = st.top();
    		while( top)
    		{
    			st.push(top->left);
    			top  = top->left;
    		}
    
    		Node * tmpRoot = 0;
    		st.pop();
    
    		if(!st.empty())
    		{
    			 tmpRoot = st.top();
    			 st.pop();
    
    			printf("%d ", tmpRoot->data);
    			st.push(tmpRoot->right);
    
    		}
    	}
    
    }
    
    //非递归前序排序
    void NonRecursionPreOrder(Node * root)
    {
    	if (!root)
    	{
    		return;
    	}
    
    	stack<Node *> st;
    	st.push(root);
    	while(!st.empty())
    	{
    		Node * cur = st.top();
    		if (cur)
    		{
    			printf("%d ", cur->data);
    			while(cur && cur->left)
    			{
    
    				cur = cur->left;
    				st.push(cur);
    				printf("%d ", cur->data);
    			}
    
    		}
    		else
    		{
    			st.pop(); 
    		}
    		
    		if(!st.empty())
    		{
    			cur = st.top(); st.pop();
    			st.push(cur->right);
    		}
    		
    	}
    }
    
    
    //非递归后序排序
    void NonRecursionPostOrder(Node * root)
    {
    	if (!root)
    	{
    		return;
    	}
    
    	stack<Node * > st;
    	st.push(root);
    	root->visit = false;
    
    	while(!st.empty())
    	{
    
    		Node * cur = st.top();
    		if(cur->visit == true)
    		{
    			printf("%d ",cur->data);
    			st.pop();
    		}
    		else
    		{
    
    			if (cur->visit == false)
    			{
    				cur->visit = true;
    			}
    
    			if (cur->right)
    			{
    				cur->right->visit = false;
    				st.push(cur->right);
    			}
    
    			if(cur->left)
    			{
    				cur->left->visit = false;
    			
    				st.push(cur->left);
    			}
    		}
    
    	
    	}
    
    }
    
    Node * RebuildBTree(Node * & root, int n, int pl, int pr, int il, int ir)
    {
    	int i = 0;
    
    	for (i = il;i <= ir; ++i)
    	{
    		if (inOrder[i] == preOrder[pl])
    		{
    			break;
    		}
    	}
    	int k = i - il;
    	if (i <= ir)
    	{
    		root = new Node();
    		root->data = inOrder[i];
    	}
    	else
    	{
    		root = NULL;
    		return root;
    	}
    	root->left = RebuildBTree(root->left, k,pl + 1 ,pl + k , il, i-1);
    	root->right = RebuildBTree(root->right,ir - i ,pl + k + 1,pr, i+1, ir);
    
    	return root;
    }
    
    int main()
    {
    	Node * root = 0;
    	int n = 7;
    	int pl = 0, pr = 6;
    	int il = 0, ir = 6;
    	root = RebuildBTree(root, n, pl, pr, il,ir);
    
    	printf("前序递归:");
    	preTraverse(root);
    
    	printf("\r\n");
    	printf("中序递归:");
    	InOrderTraverse(root);
    
    	printf("\r\n");
    	printf("后序递归:");
    	PostOrderTraverse(root);
    	
    	printf("\r\n前序非递归:");
    	NonRecursionPreOrder(root);
    
    	printf("\r\n");
    	printf("中序非递归:");
    	NonRecursionInOrder(root);
    
    	printf("\r\n后序非递归:");
    	NonRecursionPostOrder(root);
    	return 0;
    }
    


    展开全文
  • 二叉树的前序,中序递归,非递归遍历   例如 二叉树  10  / \  6 14  / \ / \
  • ## **二叉树中序递归遍历** void InOrder(TreeNode* root, vector & temp) { if (root) { if (root->left) { InOrder_pre(root->left, temp); } temp.push_back(root->val); if (root->left) { InOrder_pre(root->...
  • void preOrder(TreeNode *root) { stack<TreeNode*> s; TreeNode *p=root; while(p||!s.empty()) { while(p) { printf("%d ",p->val); s.push(p); p=p->left; } if(!s.empty()) { ...}
  • //非递归中序遍历 PostOrderWithoutRecursion(T);//非递归后续遍历 FindCount_0; findCount_1; findCount_2; PreOrderTraverse(T); InOrderTraverse(T); PostOrderTraverse(T); LevelOrderTraverse(T); //层次...
  • 其实就是在中序遍历的递归过程中加入一个辅助指针,另外用一个额外指针记住中序遍历开头的位置,转化过程的参考图片来自博客 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # ...
  • Given a binary tree, return the inorder traversal of its nodes’ values.For example: Given binary tree [1,null,2,3], 1 ...这个题很简单,就是二叉树的中序遍历。代码如下:import java
  • /* 操作结果: 中序遍历T,对每个结点调用函数Visit一次且仅一次。 */ /* 一旦Visit()失败,则操作失败 */ VisitFunc=Visit; if(!BiTreeEmpty(T)) /* 树不空 */ InTraverse(T,0); printf("\n"); return ...
  • /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) { InOrderTraverse(T->lchild,Visit); /* 先中序遍历左子树 */ Visit(T->data); /* 再访问根结点 */ InOrderTraverse(T->...
  • 信息工程学院数据结构 课程设计报告 设 计 题 目 二叉树的中序的递归非递归遍历算法 专 小 业 组 班 成 级 员 题目二叉树的中序的递归非递归遍历算法 小组任务分工 马凯编写二叉树中序递归遍历非递归遍历 崔妍编写...
  • 数据结构中的遍历先序递归中序递归后序递归遍历
  • VC6 0 链式二叉树的中序创建 递归中序遍历 非递归堆栈中序遍历 中序销毁 求树的深度
  • 前序中序中序后序 递归构建二叉树(检测输入序列的合法性)和二叉树的动态打印 前序中序中序后序 递归构建二叉树(检测输入序列的合法性)和二叉树的动态打印 前序中序中序后序 递归构建二叉树(检测输入序列...
  • 二叉树的遍历中序递归,先序后序递归
  • #include #include using namespace std; //第一种表示方法 :二叉链表示法 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild;...//中序递归遍历 void inOrder(BiTNode*root) { if (root==N
  • 之前给大家介绍了java二叉树前序遍历递归和非递归实现的内容,下面就接着给大家介绍java中序遍历递归和非递归实现的内容,一起看看吧。1、中序遍历看看访问顺序:左子树-根节点-右子树;上面图片的访问结果是ADEFGHMZ...
  • (1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
  • 中序递归算法

    2020-10-26 20:06:16
    中序递归算法 首先我们初始化一个栈,让根指针进栈。因为是中序遍历,所以我们首先要找到树的最左边结点,代码标记1完成的就是这个任务。那么代码标记1循环停止的条件不满足时,这个时候GetTop(S,p)得到的指针p是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,858
精华内容 6,343
关键字:

中序递归