二叉树、线索二叉树的创建及基本操作（c/c++)

墨蓝 2023-03-13 05:53 9阅读 0赞

编写一个程序，实现二叉树的各种运算，并在此基础上设计一个程序完成如下功能：  
（1）创建一棵二叉树（用键盘按照先序遍历序列输入一个字符串生成二叉树）；  
（2）输出前序、中序、后序遍历的遍历序列；  
（3）统计并输出二叉树的的结点个数；  
（4）计算二叉树的深度  
用键盘输入一个字符串，按照满二叉树的特点生成一棵二叉树。  
例如：如下二叉树的输入字符串为：ABD\#\#\#C\#E\#\#

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]

## 一、二叉树的创建及基本操作 ##

#include<Windows.h>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    //二叉链表的结点类型
    typedef struct BiTNode
    {
        
    	char data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //先序遍历创建二叉树
    BiTree CreateBiTree()
    {
        
    	BiTree T;
    	char ch;
    	if ((ch = getchar()) == '#')T = NULL;
    	else
    	{
        
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		T->data = ch;
    		T->lchild = CreateBiTree();
    		T->rchild = CreateBiTree();
    	}
    	return T;
    }
    //输出前序遍历二叉树的遍历序列
    void PreOrderTraverse(BiTree T)
    {
        
    	
    	if (T != NULL)
    	{
        
    		cout << T->data;
    		PreOrderTraverse(T->lchild);
    		PreOrderTraverse(T->rchild);
    	}
    }
    //输出中序遍历二叉树的遍历序列
    void InOrderTraverse(BiTree T)
    {
        
    	if (T != NULL)
    	{
        
    		InOrderTraverse(T->lchild);
    		cout << T->data;
    		InOrderTraverse(T->rchild);
    	}
    }
    //输出后序遍历二叉树的遍历序列
    void PostOrderTraverse(BiTree T)
    {
        
    	if (T != NULL)
    	{
        
    		PostOrderTraverse(T->lchild);
    		PostOrderTraverse(T->rchild);
    		cout << T->data;
    	}
    }
    //计算二叉树结点个数
    int NodeCount(BiTree T)
    {
        
    	if (T == NULL)return 0;
    	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
    //计算叶子结点个数
    int Leaf_NodeCount(BiTree T)
    {
        
    	int a = 0;
    	if (T == NULL)return 0;
    	else
    	{
        
    		if (!T->lchild&&!T->rchild)a++;
    		return a + Leaf_NodeCount(T->lchild) + Leaf_NodeCount(T->rchild);
    	}
    }
    //计算树的深度
    int Tree_depth(BiTree T)
    {
        
    	if (T != NULL) {
        
    		return MAX(Tree_depth(T->lchild),Tree_depth(T->rchild)) + 1;
    	}
    	return 0;
    }
    int main()
    {
        
    
    	BiTree T;
    	T = CreateBiTree();
    	while (1)
    	{
        
    		Sleep(1000);
    		cout << "**************操作介绍***************" << endl;
    		cout << "     0:退出操作系统                    " << endl;
    		cout << "     1:输出前序遍历二叉树的遍历序列     " << endl;
    		cout << "     2:输出中序遍历二叉树的遍历序列     " << endl;
    		cout << "     3:输出后序遍历二叉树的遍历序列     " << endl;
    		cout << "     4:输出计算二叉树结点个数          " << endl;
    		cout << "     5:输出计算二叉树叶子结点个数      " << endl;
    		cout<<  "     6:输出计算二叉树的深度            "<<endl;
    		cout << "*************************************" << endl;
    		cout << "请输入操作代号：";
    		int a;
    		cin >> a;
    		cout << "***************************************" << endl;
    		switch (a)
    		{
        
    		case 1:
    			cout << "该二叉树的前序序列为：";
    	        PreOrderTraverse(T);
    	        cout << endl;
    			break;
    		case 2:
                cout << "该二叉树的中序序列为：";
    	        InOrderTraverse(T);
    	        cout << endl;
    			break;
    		case 3:
    			cout << "该二叉树的后序序列为：";
    	        PostOrderTraverse(T);
    	        cout << endl;
    			break;
    		case 4:
    			cout << "该二叉树结点个数为：";
    			int b;
    			b = NodeCount(T);
    			cout << b<<"个"<<endl;
    			break;
    		case 5:
    			cout << "该二叉树叶子结点个数为：";
    			int c;
    			c = Leaf_NodeCount(T);
    			cout << c << "个" << endl;
    			break;
    		case 6:
    			cout << "该二叉树的深度为：";
    			int d;
    			d = Tree_depth(T);
    			cout << d <<endl;
    			break;
    		}
    		if (a == 0)break;
    	}
    	return 0;
    }

**运行结果为：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200511200402590.png]  
![在这里插入图片描述][20200523220043869.png]  
![在这里插入图片描述][20200511200437176.png]  
![在这里插入图片描述][20200511200453841.png]

## 二、线索二叉树的创建及遍历 ##

在前一实验的基础上完成如下功能：  
（1）中序线索化二叉树；  
（2）中序遍历线索二叉树并输出的遍历序列；

#include<stdio.h>
    #include<iostream>
    using namespace std;
    //线索二叉树结点结构
    typedef struct BiTree {
        
    	char data;
    	int LTag, RTag;
    	struct BiTree *lchild, *rchild;
    }BiTree,*BiThrTree;
    BiThrTree pre;  //全局变量，（前驱结点）
    //创建一个二叉树(先序遍历）
    BiThrTree InitTree(BiThrTree T)
    {
        
    	
    	char ch;
    	if ((ch = getchar()) == '#')T = NULL;
    	else
    	{
        
    		T = (BiTree*)malloc(sizeof(BiTree));
    		T->data = ch;
    		T->LTag = 0;
    		T->RTag = 0;
    		T->lchild=InitTree(T->lchild);
    		T->rchild=InitTree(T->rchild);
    	}
    	return T;
    }
    //中序线索化二叉树
    void Inthreading(BiThrTree T)
    {
        
    	if (T)
    	{
        
    		Inthreading(T->lchild);
    		if (T->lchild == NULL)   //当T的左儿子为空时
    		{
        
    			T->LTag = 1;
    			T->lchild = pre;
    		}
    		if (!pre->rchild)        //当pre的右儿子为空时
    		{
        
    			pre->RTag = 1;
    			pre->rchild = T;
    		}
    		pre = T;
    		Inthreading(T->rchild);
    	}
    }
    //设置根结点
    BiThrTree Inorderthreading(BiThrTree head, BiThrTree T)
    {
        
    	head= (BiTree*)malloc(sizeof(BiTree));
    	head->LTag = 0;
    	head->RTag = 1;
    	head->rchild = NULL;
    	if(!T)
    	{
        
    		head->rchild = head;
    	}
    	else
    	{
        
    		head->lchild = T;
    		pre = head;
    		Inthreading(T);
    		pre->rchild = head;
    		pre->RTag = 1;
    		head->rchild = pre;
    	}
    	return head;
    }
    //访问一个结点
    void visit(char c)
    {
        
    	cout<<c<<" ";
    }
    //中序遍历线索二叉树
    void InOrderTraverse(BiThrTree T)
    {
        
    	BiThrTree p;
    	p = T->lchild;
    	while (p != T)
    	{
        
    		while (p->LTag == 0)p = p->lchild;
    		visit(p->data);
    		while (p->RTag == 1 && p->rchild != T)
    		{
        
    			p = p->rchild;
    			visit(p->data);
    		}
    		p = p->rchild;
    	}
    }
    int main()
    {
        
    	BiThrTree T = NULL, head = NULL;
    	cout << "请输入二叉树先序遍历序列：";
    	T=InitTree(T);
    	head=Inorderthreading(head,T);
    	cout << "线索二叉树中序遍历为：";
    	InOrderTraverse(head);
    	cout << endl;
    	return 0;
    }

**运行结果如下：**  
![在这里插入图片描述][20200514191948803.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: /images/20230312/4d8d785271984341b4afaef86e03060d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: /images/20230312/9c545e914ab1476499ebe63d4eb0d773.png
[20200511200402590.png]: /images/20230312/245d54538647458d80c3356f830226dd.png
[20200523220043869.png]: /images/20230312/41ed4ca5848b4b619decf792dfefd027.png
[20200511200437176.png]: /images/20230312/65c2940f7e37418ea689ec8655750684.png
[20200511200453841.png]: /images/20230312/fa299606134d4998b56bae50ce107f55.png
[20200514191948803.png]: /images/20230312/720764f146964814a443c75171cfddd4.png