精华内容
下载资源
问答
  • 二叉树的建立与遍历
    千次阅读
    2018-05-25 22:22:16

    本来想做纯二叉树的遍历的,但是做的时候感觉加上哈夫曼编码的建立规则吧,于是这个四不像便产生啦。。。
    不过基本的三种遍历方法还在。求节点数,树的深度,二叉树每层节点数也有的。

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int Count = 0;                   /*统计二叉树节点*/
    int Depth = 0;                   /*二叉树的深度*/
    
    /*二叉树结构*/
    typedef struct BNode
    {
    	char data;                   /*字符*/
    	int weight;                  /*出现次数,即权重*/
    	struct BNode *left,*right;   /*左子女,右子女*/
    }BTNode,*BTree;
    
    /*字符和出现频率的映射表*/
    typedef struct 
    {
    	char data;                   /*字符*/
    	int weight;                  /*出现次数,即权重*/
    	int level;                   /*该字符所在二叉树层次*/
    }chart;
    
    /*创建字符和频率映射表*/
    chart * CreateChart()
    {
    	int i;
    	chart *List = (chart *)malloc(sizeof(chart) * Count);  /*动态分配有NUM个chart*类型单元的数组*/
    	
    	/*循环方式建立List表*/
    	for (i = 0 ; i < Count ; i++)
    	{
    		printf("Please enter the character of NO%d.:\n",i+1);    /*输入字符*/
    		fflush(stdin);
    		scanf("%c",&List[i].data);                  
    		fflush(stdin);
    		printf("Please enter the weight of NO%d.:\n",i+1);       /*输入权重*/
    		scanf("%d",&List[i].weight);
    		List[i].level = 0;
    	}
    	return List;
    }
    
    /*插入一个数据,数据左小右大*/
    int Insert(BTree root,char Data,int weight)
    {
    	int level = 1;                      /*level代表该节点插入的层次*/
    	BTree temp,father,child;            /*temp是临时结点,father是对比结点的父结点,child是当前对比结点。*/
    
        /*创建临时结点*/
    	temp = (BTree)malloc(sizeof(BTNode));
    	temp->data = Data;
    	temp->weight = weight;
    	temp->left = NULL;
    	temp->right = NULL;
    	child = root;
    
    	/*该临时结点的挂链*/
        while (child)
    	{
    		father = child;
    		if (child->weight > temp->weight)         /*权重小的放在左边*/
    			child = child->left;
    		else                                      /*权重大的放在右边*/
    			child = child->right;
    		level++;
    	}
    	if (father->weight > temp->weight)
    		father->left = temp;
    	else
    		father->right = temp;
    	return level;
    }
    
    
    /*创建二叉树*/
    BTree CreateBTree(chart *List)
    {
    	int i;
    	BTree root;
    	
    	/*创建根节点*/
    	root = (BTree)malloc(sizeof(BTNode));
    	root->data = List[0].data;
    	root->weight = List[0].weight;
    	root->left = NULL;
    	root->right = NULL;
    	List[0].level=1;
    	Depth = 1;
    
    	/*创建其余节点*/
    	for (i=1;i<Count;i++)
    	{
    		List[i].level = Insert(root,List[i].data,List[i].weight);
    		if (Depth < List[i].level)
    			Depth = List[i].level;
    	}
    	return root;
    } 
    
    /*先序遍历*/
    void PreOrderTraverse(BTree root)
    {
    	if (root)
    	{
    		printf("\t%c",root->data);
    		PreOrderTraverse(root->left);
    		PreOrderTraverse(root->right);
    	}
    }
    
    
    /*中序遍历*/
    void InOrderTraverse(BTree root)
    {
    	if(root)
    	{
    		InOrderTraverse(root->left);
    		printf("\t%c",root->data);
    		InOrderTraverse(root->right);
    	}
    }
    
    
    /*后序遍历*/
    void PostOrderTraverse(BTree root)
    {
    	if(root)
    	{
    		PostOrderTraverse(root->left);
    		PostOrderTraverse(root->right);
    		printf("\t%c",root->data);
    	}
    }
    
    
    /*统计输出二叉树每层节点数*/
    void NodeNum(chart *List)
    {
    	int i,L;                                                  /*L是每个字符所在二叉树的层数*/
    	int *llevel;                                              /*llevel指向存储每层结点的数组*/
    	llevel= (int *)malloc(sizeof(int) * (Depth+1) )  ;        /*建立一个拥有Depth+1个单元的数组,用来存储每层节点数。*/
    	memset(llevel, 0, sizeof(int) * (Depth+1));
    	
    	/*统计每层节点数*/
    	for (i = 0; i < Count; i++)                              
    	{
    		L=List[i].level;
    		llevel[L]++;
    	}
    
    	/*输出每层节点数*/
    	for(i = 1; i < Depth+1; i++)                             
    	{
    		printf("Level %d has %d nodes.\n", i, llevel[i] );
    	}
    }
    
    /*主程序*/
    int main(void)
    {
    	chart *List;    /*List是字符和频率的映射表*/
    	BTree root;     /*root是二叉树的根节点*/
    
    	printf("Please enter the number of characters:\n");/*设置字符总数*/
    	scanf("%d",&Count);
    	List = CreateChart();
    	root = CreateBTree(List);/*创建二叉树*/
    	system("cls");
    
    	/*先序输出*/
    	printf("\n先序输出\n");
    	PreOrderTraverse(root);
    	
    	/*中序输出*/
    	printf("\n中序输出\n");
    	InOrderTraverse(root);
    	
    	/*后序输出*/
    	printf("\n后序输出\n");
    	PostOrderTraverse(root);
    	
    	/*输出二叉树节点总数*/
    	printf("\nThe number of nodes of binary tree is: %d.\n",Count);
    
    	/*统计并输出该二叉树的深度*/
    	printf("\nThe number of level of binary tree is: %d\n",Depth);
    
    	/*输出每层有几个节点*/
    	NodeNum(List);
    
    	return 0;
    }
    
    


    更多相关内容
  • 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...
  • 二叉树建立与遍历

    2011-11-04 21:55:56
    二叉树建立与遍历,包括二叉树的定义,有参和无参,前序,中序,后序的遍历
  • 建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
  • 数据结构试验3二叉树建立遍历等操作代码及运行结果。 实验内容: 采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,...
  • 二叉树建立及其遍历

    2018-11-26 23:36:03
    C实现二叉树建立及先中后序的遍历,控制台程序,在各版本vs上均可运行
  • 二叉树建立与遍历

    2016-10-15 17:29:56
    按先序序列构造一棵二叉链表表示的二叉树T,并输出该T的中序遍历序列。实现提示: 1) 按先序序列建立一棵二叉树时,先构造根结点,再构造根的左子树,然后构造右子树;每棵子树又都是二叉树,所以构造一棵子树的过程...
  • 主要介绍了Python 二叉树的层序建立与三种遍历实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 二叉树建立遍历

    千次阅读 2022-04-17 15:25:51
    二叉树建立与遍历

    建立

    二叉树的建立就是一个递归的过程

    首先我们在结构体中定义一个data,和两个结构体类型的指针,放别用来存放结点数据和分别指向左右孩子【lchild,rchild】

    这里我将数据为空格当作树的每一个分支的结束标志,将叶子结点的lchild或rchild指向NULL,若输入数据不为空格,则继续进行递归创建

    代码实现:

    BiTree create_bitree(BiTree &T){
    //注意此处的参数,如果直接加&,就代表直接使用main函数中的指针
    //进行操作;
    //如果不使用&,就必须使用二重指针,如果使用Bitree T在函数结束后内存
    //便会自动释放,以为T只是指向了内存块,而不是指向你所开辟的那一块内存
    	char c;
    	scanf("%c", &c);
    	
    	if(' ' == c)
    	{
    		T = NULL;
    	}
    	else
    	{
    		T = (BiNode *)malloc(sizeof(BiNode));
    		T->data = c;
    		create_bitree(T->lchild);
    		create_bitree(T->rchild);
    	}
    	return T; 
    }
    

    参数为二重指针:

    elemtype create_bitree(BiTree *T){
    	
    	char c;
    	scanf("%c", &c);
    	
    	if(' ' == c)
    	{
    		*T = NULL;
    	}
    	else
    	{
    		*T = (BiNode *)malloc(sizeof(BiNode));
    		(*T)->data = c;
    		create_bitree(&(*T)->lchild);
    		create_bitree(&(*T)->rchild);
    	}
    }
    

    遍历

    二叉树共有三种遍历方法:

    		先序遍历
    		中序遍历
    		后序遍历
    

    代码实现时其实特别方便,因为我们只需要控制输出的顺序就可以了;因为这个一个递归的过程,所以每一个结点都会访问三次,但是访问结点不一定非要进行输出操作

    先序遍历:

    elemtype visit(char c,int level){
    	
    	printf("%c 位于第 %d 层\n", c, level);
    } 
    
    //先序遍历二叉树
    elemtype travel_bitree(BiTree T, int level){
    	
    	if(T)
    	{
    		visit(T->data, level);
    		travel_bitree(T->lchild, level+1);
    		travel_bitree(T->rchild, level+1);
    		
    	}
    } 
    

    中序遍历:

    elemtype visit(char c,int level){
    	
    	printf("%c 位于第 %d 层\n", c, level);
    } 
    
    //中序遍历二叉树
    elemtype travel_bitree(BiTree T, int level){
    	
    	if(T)
    	{
    		travel_bitree(T->lchild, level+1);
    		visit(T->data, level);
    		travel_bitree(T->rchild, level+1);
    		
    	}
    } 
    

    后序遍历:

    elemtype visit(char c,int level){
    	
    	printf("%c 位于第 %d 层\n", c, level);
    } 
    
    //后序遍历二叉树
    elemtype travel_bitree(BiTree T, int level){
    	
    	if(T)
    	{
    		travel_bitree(T->lchild, level+1);
    		travel_bitree(T->rchild, level+1);
    		visit(T->data, level);
    		
    	}
    } 
    

    以下是先序遍历的全部代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef char elemtype;
    typedef struct BiNode{
    	
    	elemtype data;
    	struct BiNode *lchild,*rchild;
    }BiNode,*BiTree;
    
    
    BiTree create_bitree(BiTree &T){
    
    	char c;
    	scanf("%c", &c);
    	
    	if(' ' == c)
    	{
    		T = NULL;
    	}
    	else
    	{
    		T = (BiNode *)malloc(sizeof(BiNode));
    		T->data = c;
    		create_bitree(T->lchild);
    		create_bitree(T->rchild);
    	}
    	return T; 
    }
    
    elemtype visit(char c,int level){
    	
    	printf("%c 位于第 %d 层\n", c, level);
    } 
    
    //先序遍历二叉树
    elemtype travel_bitree(BiTree T, int level){
    	
    	if(T)
    	{
    		visit(T->data, level);
    		travel_bitree(T->lchild, level+1);
    		travel_bitree(T->rchild, level+1);
    		
    	}
    } 
    
    
    int main(){
    	
    	int level = 1;
    	BiTree T = NULL;
    	BiTree S = create_bitree(T);
    	
    	travel_bitree(S,level);
    	return 0;
    } 
    
    展开全文
  • 大型二叉树建立与遍历系统\大型二叉树建立与遍历系统.
  • 实验名称:二叉树建立与遍历算法 指导教师: 实验日期:2022年月日 实验地点: 成绩: 实验目的: 1、掌握二叉树的定义。 2、二叉树的链式存储结构及在链式存储结构中三种遍历(前序,中序,后序)操作的实现...

     

     

    实验名称:二叉树的建立与遍历算法          指导教师:       

    实验日期:2022    日 实验地点:            成绩:     

    实验目的:

    1、掌握二叉树的定义。

    2、二叉树的链式存储结构及在链式存储结构中三种遍历(前序,中序,后序)操作的实现及应用。

    实验内容:

    编写程序,实现以下功能:

    (1)建立一棵二叉树(以链表存储),对该二叉树进行遍历并输出该二叉树的前序,中序,后序遍历序列。要求前序、中序遍历用非递归方法,后序遍历用递归方法完成。

    (2)实现二叉树左右子树的交换。

    (3)统计二叉树中叶子结点个数。(要求用非递归算法完成)

    基本要求:

    1、写出完成实验内容的实验方法和源代码。

    2、写出实验数据及运行结果。

    3、写出在实验过程中所遇到的问题及解决办法。

    实验源码

    #include <stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define Maxsize 20
    typedef struct Node
    {
    	int date;
    	struct Node* lchild;//左孩子节点
    	struct Node* rchild;//右孩子节点
    }*binraytree;
    //创建二叉树
    binraytree CreatTree()
    {
    	binraytree tree;
    	int temp = getchar();  
    	int data = getchar();
    	if (data == 48)          //空节点以0表示
    	{
    		return NULL;       
    	}
    	else
    	{
    		tree = (binraytree)malloc(sizeof(Node));
    		if (tree != NULL)
    		{
    			tree->date = data;
    			printf("请输入%c树的左叶子节点的值!\n", data);
    			tree->lchild = CreatTree();
    			printf("请输入%c树的右叶子节点的值!\n", data);
    			tree->rchild = CreatTree();
    			return tree;
    		}
    	}
    }
     int treehight(binraytree tree)//获取树的高度
     {
    	 int lchildh, rchildh;
    	 if (tree == NULL)
    	 {
    		 return 0;
    	 }
    	 else
    	 {
    		 lchildh = treehight(tree->lchild);
    		 rchildh = treehight(tree->rchild);
    		 return (lchildh > rchildh ? lchildh + 1 : rchildh + 1);
    	 }
     }
     void FrontPrint(binraytree tree)//前序非递归遍历
     {
    	 binraytree st[Maxsize], node = NULL;
    	 int top = -1;
    	 if (tree != NULL)
    	 {
    		 st[0] = tree;
    		 top++;
    		 while (top != -1)   //如果栈不为空
    		 {
    			 node = st[top];
    			 printf("%c\t", node->date);//出栈
    			 top--;
    			 if (node->rchild != NULL)
    			 {
    				 st[++top] = node->rchild;//右孩子不为空先进栈
    			 }
    			 if (node->lchild != NULL)
    			 {
    				 st[++top] = node->lchild;//左孩子不为空先进栈
    			 }
    		 }
    	}
     }
     
     void Midlideprint(binraytree tree)//非递归中序遍历
     {
    	 binraytree st[Maxsize], node = NULL;
    	 int top = -1;
    	 while (top != -1 || tree != NULL)          //栈或树非空
    	 {
    		 while (tree != NULL)
    		 {
    			 st[++top] = tree;
    			 tree = tree->lchild;
    		 }
    		 if (top != -1)
    		 {
    			 node = st[top--];
    			 printf("%c\t", node->date);
    			 tree = node->rchild;
    		 }
    	 }
     }
     void LastPrint(binraytree tree)//后序递归调用
     {
    	 if (tree == NULL)
    	 {
    		 return;//遍历到的当前节点如果为空则返回
    	 }
    	 LastPrint(tree->lchild);
    	 LastPrint(tree->rchild);
    	 printf("%c\t", tree->date);
    
     }
     void Changetree(binraytree tree)//左右子树交换
     {
    	 if (tree != NULL)
    	 {
    		 binraytree temp;
    		 temp = tree->lchild;
    		 tree->lchild = tree->rchild;
    		 tree->rchild = temp;
    		 printf("左右子树交换成功\n");
    	 }
    	 else
    	 {
    		 printf("左右子树交换失败\n");
    	 }
     }
     int  Growtree(binraytree tree)//非递归计算树的叶子数
     {
    	 int top = -1;
    	 binraytree st[Maxsize];
    	 int count = 0;
    	 while (tree != NULL || top != -1)
    	 {
    		 while (tree != NULL) // 当前节点不为空
    		 {
    			 if (tree->lchild == NULL && tree->rchild == NULL) // 若当前根节点的左右子树都为空,则是叶子节点
    				 count++;
    			 st[++top] = tree; // 先 ++top,然后将当前的根节点入栈
    
    			 tree = tree->lchild; // 然后访问当前根节点的左子树
    
    		 }
    		 if (top != -1) // 栈不为空
    		 {
    			 tree = st[top--];
    			 tree = tree->rchild;
    		 }
    	 }
    
    	 return count;
     }
     void GetTree(binraytree tree, int type, int level)
     {
    	 int i;
    
    	 if (NULL == tree)
    		 return;
    
    	 GetTree(tree->rchild, 2, level + 1);
    	 switch (type)
    	 {
    	 case 0:
    		 printf("%2c\n", tree->date);
    		 break;
    	 case 1:
    		 for (i = 0; i < level; i++)
    			 printf("\t");
    		 printf("\\\n");
    		 for (i = 0; i < level; i++)
    			 printf("\t");
    		 printf("  %2c\n", tree->date);
    
    		 break;
    	 case 2:
    
    		 for (i = 0; i < level; i++)
    			 printf("\t");
    		 printf(" %2c\n", tree->date);
    		 for (i = 0; i < level; i++)
    			 printf("\t");
    		 printf("/\n");
    		 break;
    	 }
    	 GetTree(tree->lchild, 1, level + 1);
     }
     void travlevel(binraytree tree)
     {
    	 binraytree qu[Maxsize];
    	 int front, rear;
    	 front = rear = 0;
    	 if (tree != NULL)
    		 printf("%c",tree->date);
    	 rear++;
    	 qu[rear] = tree;
    	 while (rear != front)
    	 {
    		 front = (front + 1) % Maxsize;
    		 tree = qu[front];
    		 if (tree->lchild != NULL)
    		 {
    			 printf("%2c", tree->lchild->date);
    			 rear = (rear + 1) % Maxsize;
    			 qu[rear] = tree->lchild;
    		 }
    		 if (tree->rchild != NULL)
    		 {
    			 printf("%2c", tree->rchild->date);
    			 rear = (rear + 1) % Maxsize;
    			 qu[rear] = tree->rchild;
    
    		 }
    	 }
    
    
      }
     int main()
     {
    	 binraytree tree = NULL;
    	 int choice = 0, h = 0, num = 0;
    	 while (choice != 9)
    	 {
    		 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("***      9.退出             ***\n");
    		 printf("*******************************\n");
    		 scanf_s("%d", &choice);
    		 switch (choice)
    		 {
    		 case 1:
    			 printf("\n请输入树的节点的值!\n");
    			 tree = CreatTree();//创建二叉树
    			 system("cls");
    			 printf("\n创建成功!\n");
    			 GetTree(tree,num,h);
    			 break;
    		 case 2:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 printf("\n前序遍历结果为:\n");
    			 FrontPrint(tree);//非递归前序遍历
    			 printf("\n\n");
    			 break;
    		 case 3:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 printf("\n中序遍历结果为:\n");//非递归中序遍历
    			 Midlideprint(tree);
    			 printf("\n\n");
    			 break;
    		 case 4:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 printf("\n后序遍历结果为:\n");
    			 LastPrint(tree);  //递归后序遍历
    			 printf("\n\n");
    			 break;
    		 case 5:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 h = treehight(tree);
    			 printf("\n树的高度为:%d\n\n", h);
    			 break;
    		 case 6:
    			 system("cls"); 
    			 GetTree(tree, num, h);
    			 Changetree(tree);
    			 GetTree(tree, num, h);
    			 break;
    		 case 7:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 num = Growtree(tree);
    			 printf("\n叶子结点个数为:%d\n", num);
    			 break;
    		 case 8:
    			 system("cls");
    			 GetTree(tree, num, h);
    			 printf("\n层次遍历为:\n");
    			 travlevel(tree);
    			 printf("\n\n");
    			 break;
    		 case 9:
    			 break;
    		 default:
    			 system("cls");
    			 printf("\n没有此选项,请重新选择!\n\n");
    			 break;
    		 }
    	 }
     }

    展开全文
  • 二叉树建立与遍历详解

    千次阅读 2020-02-08 18:38:10
    1、二叉树建立与遍历分布详解 定义二叉树结构体: typedef struct BinaryTreeNode { TelemType data; struct BinaryTreeNode *Left; struct BinaryTreeNode *Right; }Node; 创建二叉树: Node* ...

    1、二叉树的建立与遍历分布详解

    • 定义二叉树结构体:
    typedef struct BinaryTreeNode
    {
        TelemType data;
        struct BinaryTreeNode *Left;
        struct BinaryTreeNode *Right;
    }Node;
    
    • 创建二叉树:
    Node* createBinaryTree()
    {
        Node *p;
        TelemType ch;
        cin>>ch;
        if(ch == 0)     //如果到了叶子节点,接下来的左、右子树分别赋值为0
        {
            p = NULL;
        }
        else
        {
            p = (Node*)malloc(sizeof(Node));
            p->data = ch;
            p->Left  = createBinaryTree();  //递归创建左子树
            p->Right = createBinaryTree();  //递归创建右子树
        }
        return p;
    }
    
    

    注意:创建二叉树顺序为先中心节点,然后左子树,然后右子树,到了叶子节点后要把它的左右子树分别赋值为0。

    • 先序遍历:
    void preOrderTraverse(Node* root)
    {
        if( root )
        {
            cout<<root->data<<' ';
            preOrderTraverse(root->Left);
            preOrderTraverse(root->Right);
        }
    }
    
    
    • 中序遍历:
    void inOrderTraverse(Node* root)
    {
        if( root )
        {
            inOrderTraverse(root->Left);
            cout<<root->data<<' ';
            inOrderTraverse(root->Right);
        }
    }
    
    
    • 后序遍历:
    void lastOrderTraverse(Node* root)
    {
        if( root )
        {
            lastOrderTraverse(root->Left);
            lastOrderTraverse(root->Right);
            cout<<root->data<<' ';
        }
    }
    
    
    • 二叉树节点总数目:
    int Nodenum(Node* root)
    {
        if(root == NULL)
        {
            return 0;
        }
        else
        {
            return 1+Nodenum(root->Left)+Nodenum(root->Right);
     
        }
    }
    
    
    • 二叉树深度:
    int DepthOfTree(Node* root)
    {
        if(root)
        {
            return DepthOfTree(root->Left)>DepthOfTree(root->Right)?DepthOfTree(root->Left)+1:DepthOfTree(root->Right)+1;
        }
        if( root == NULL )
        {
            return 0;
        }
    }
    
    
    • 二叉树叶子节点数:
    int Leafnum(Node* root)
    {
        if(!root)
        {
            return 0;
        }
        else if(  (root->Left == NULL) && (root->Right == NULL) )
        {
            return 1;
        }
        else
        {
            return  (Leafnum(root->Left) + Leafnum(root->Right)) ;
        }
    }
    
    

    2、下面是整个程序的代码:

    #include <iostream>
    #include<cstdio>
    #include<cstdlib>
     
    using namespace std;
     
    typedef int TelemType;
     
    typedef struct BinaryTreeNode
    {
        TelemType data;
        struct BinaryTreeNode *Left;
        struct BinaryTreeNode *Right;
    }Node;
     
     
    //创建二叉树,顺序依次为中间节点->左子树->右子树
    Node* createBinaryTree()
    {
        Node *p;
        TelemType ch;
        cin>>ch;
        if(ch == 0)     //如果到了叶子节点,接下来的左、右子树分别赋值为0
        {
            p = NULL;
        }
        else
        {
            p = (Node*)malloc(sizeof(Node));
            p->data = ch;
            p->Left  = createBinaryTree();  //递归创建左子树
            p->Right = createBinaryTree();  //递归创建右子树
        }
        return p;
    }
     
    //先序遍历
    void preOrderTraverse(Node* root)
    {
        if( root )
        {
            cout<<root->data<<' ';
            preOrderTraverse(root->Left);
            preOrderTraverse(root->Right);
        }
    }
     
    //中序遍历
    void inOrderTraverse(Node* root)
    {
        if( root )
        {
            inOrderTraverse(root->Left);
            cout<<root->data<<' ';
            inOrderTraverse(root->Right);
        }
    }
     
    //后序遍历
    void lastOrderTraverse(Node* root)
    {
        if( root )
        {
            lastOrderTraverse(root->Left);
            lastOrderTraverse(root->Right);
            cout<<root->data<<' ';
        }
    }
     
    //二叉树节点总数目
    int Nodenum(Node* root)
    {
        if(root == NULL)
        {
            return 0;
        }
        else
        {
            return 1+Nodenum(root->Left)+Nodenum(root->Right);
     
        }
    }
     
    //二叉树的深度
    int DepthOfTree(Node* root)
    {
        if(root)
        {
            return DepthOfTree(root->Left)>DepthOfTree(root->Right)?DepthOfTree(root->Left)+1:DepthOfTree(root->Right)+1;
        }
        if( root == NULL )
        {
            return 0;
        }
    }
     
    //二叉树叶子节点数
    int Leafnum(Node* root)
    {
        if(!root)
        {
            return 0;
        }
        else if(  (root->Left == NULL) && (root->Right == NULL) )
        {
            return 1;
        }
        else
        {
            return  (Leafnum(root->Left) + Leafnum(root->Right)) ;
        }
    }
     
     
    int main()
    {
        Node *root = NULL;
        root = createBinaryTree();
        printf("二叉树建立成功");
        cout<<endl;
     
        cout<<"二叉树总节点数为:"<<Nodenum(root)<<endl;
     
        cout<<"二叉树深度为:"<<DepthOfTree(root)<<endl;
     
        cout<<"二叉树叶子节点数为:"<<Leafnum(root)<<endl;
     
        cout<<"前序遍历结果:"<<endl;
        preOrderTraverse(root);
        cout<<endl;
     
        cout<<"中序遍历结果:"<<endl;
        inOrderTraverse(root);
        cout<<endl;
     
        cout<<"后序遍历结果:"<<endl;
        lastOrderTraverse(root);
        cout<<endl;
     
        return 0;
    }
    
    

    分别输入两个二叉树来验证结果:
    第一个二叉树为:
    在这里插入图片描述 在这里插入图片描述

    第二个二叉树为:
    在这里插入图片描述在这里插入图片描述

    展开全文
  • 建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。 2.基本要求: 从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(先序、中序...
  • 线索二叉树建立,前中后线索的建立,前中后序递归非递归遍历,广义表形式输出,层序遍历
  • C语言数据结构实现二叉树建立与遍历.cpp
  • 二叉树的中序遍历 题目描述: 解题思路: 第一种:递归。又是递归,可以发现很多题都可以用到递归的思路…。二叉树的中序遍历,这里不太了解的可以看看这个博客:二叉树遍历,总结了二叉树的所有遍历情况。这道题所...
  • 实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
  • 本文实例讲述了C语言实现线索二叉树的定义与遍历。分享给大家供大家参考,具体如下: #include #include typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // ...
  • 二叉树_二叉树遍历_

    2021-10-04 07:03:48
    1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...
  • C++实现二叉树建立与遍历,简单易懂!!!
  • 二叉树建立遍历

    2013-07-02 10:00:03
    以二叉链表存储二叉树,按照完全二叉树的编号顺序输入节点,创建二叉树,最后,给出三种遍历的结果
  • 层次遍历二叉树是大家再熟悉不过的二叉树操作了,看到这个算法通常会联想到队列,没错,叨叨Chen设计的层次遍历算法也是用到了队列(先进先出),下面一起进入算法游乐场吧。It's show time!Punchline--------------...
  • 二叉树建立与遍历【数据结构实验报告】

    万次阅读 多人点赞 2017-11-06 21:20:24
    数据结构实验报告实验名称:实验四 二叉树建立遍历学号:***姓名:gnosed实验日期:2017.11.5 一、实验目的1、掌握树的先根构造2、了解树的遍历 二、实验具体内容1、实验题目1:(1)题目构造一棵二叉树,并...
  • 主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
  • 二叉树遍历遍历二叉树有四种方法 二叉树遍历原理 二叉树遍历(traversing binary tree) 是指从根节点除法,按照某种次序一次访问二叉树中的所有结点 使得每个结点被访问一次 , 且仅被访问一次 关键词...
  • 二叉树建立与遍历小结

    千次阅读 2019-02-25 16:58:43
    好久前就学完二叉树了,不过不善总结,到现在才温习一遍,感觉全是模板啊,有点难的就是那个树的同构~。...建立二叉树后我们可以先序(根左右),中序(左根右),后序(左右根),层序,来遍历二叉树...
  • (1)建立一棵二叉树(以链表存储),对该二叉树进行遍历并输出该二叉树的前序,中序,后序遍历序列。要求前序、中序遍历用非递归方法,后序遍历用递归方法完成。 (2)实现二叉树左右子树的交换。 (3)统计二叉树中...
  • 什么是二叉排序树? 1.二叉排序树又叫二叉查找树或者二叉搜索树,它首先是一个二叉树,而且必须满足下面的条件: ...2.除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为
  • 数据结构 第六次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一实验内容 1) 采用二叉树链表作为存储结构完成二叉树建立先序中序和后序 以及按层次遍历的操作求所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,873
精华内容 27,149
关键字:

二叉树的建立与遍历

友情链接: CHAP1_1.zip