二叉树的c++基本操作实现(创建、各种遍历、计算深度、节点数、叶子节点数、查找相应节点并且输出)（附C++实现代码）

川长思鸟来 2023-06-12 04:14 11阅读 0赞

本文有些递归有些摘自以下链接：[点击传送][Link 1]

**我当时自己在编写代码的时候主要碰到的问题是：对于递归，处于一种一看就会，一写就跪的境界，然后我去找资料理解递归**  
**递归有神人总结为以下模板，仅供参考：**

下面实现的代码中并没有将基本操作定义成TreeNode的成员方法，其实想要封装好，将这些方法变成成员方法比较好。

**二叉树的理解主要是递归概念的理解，二叉树是一种递归概念**  
**还有一些二叉树的基本功能还没有实现，后序会更新。**  
**1、通过先序遍历顺序来创建一颗二叉树**  
**2、先序遍历、中序遍历和后序遍历（递归实现）、非递归方式实现这些遍历的会在后序补充更新。**  
**3、计算二叉树的深度**  
**4、计算二叉树的节点数**  
**5、计算二叉树度数为1的节点数**  
**6、计算二叉树的叶子节点**  
**7、查找值为value的节点并且输出其左右子树**

//TreeNode.h文件进行二叉树节点定义和函数声明
    #pragma once
    #include<iostream>
    using namespace std;
    class TreeNode {
    public:
    	char value;//节点的值
    	TreeNode* lTree;//左子树
    	TreeNode* rTree;//右子树
    	TreeNode(char value) {
    		this->value = value;
    		this->lTree = NULL;
    		this->rTree = NULL;
    	}
    };
    
    //创建一个空树
    TreeNode* creatNuTree();
    
    //先序遍历的顺序建立二叉树
    void creatBinTree(TreeNode* &root);
    
    //二叉树的先序遍历
    void outTreeDLR(TreeNode* root);
    
    //二叉树的中序遍历
    void outTreeLDR(TreeNode* root);
    
    //二叉树的后序遍历
    void outTreeLRD(TreeNode* root);
    
    //二叉树的复制操作
    void cloneTree(TreeNode* root, TreeNode* &newRoot);
    
    //计算二叉树的深度
    int treeDepth(TreeNode* root);
    
    //计算二叉树的节点数量
    int treeNodeNum(TreeNode* root);
    
    //计算二叉树的叶子节点的数量
    int treeleNodeNum(TreeNode* root);
    
    //查找某个值为value的节点在不在二叉树中，如果在返回其左右子树,如果不在返回false
    bool search(TreeNode* root,char value);
    
    //计算二叉树的度数为1的节点数
    int treeDegree_1(TreeNode* root);

函数实现文件
    hanshu.cpp  
    #include"TreeNode.h"
    #include<iostream>
    #include<Stack>
    using namespace std;
    //创建一个空树
    TreeNode* creatNuTree() {
    	TreeNode* binTree = new TreeNode(-1);//创建的树的根值默认为-1
    	return binTree;
    }
    
    //先序遍历的顺序建立二叉树
    void creatBinTree(TreeNode* &root) {
    	
    	//先序遍历比较简单
    	char ch = '0';
    	cin >> ch;
    	//递归停止的标志  
    	if (ch == '#'){
    		//将根节点置空
    		root = NULL;
    		return;
    	}
    	else{
    	
    		root = new TreeNode(ch);
    		//递归创建一个左子树
    		creatBinTree(root->lTree);
    		//递归创建一个右子树
    		creatBinTree(root->rTree);
    	}
    }
    
    //二叉树的先序遍历
    void outTreeDLR(TreeNode* root) {
    	//中序遍历可以通过递归的方式来实现或者非递归的方式来实现
    
    	if (root) {
    		//递归按照LDR(中左右)的顺序进行实现
    		cout << root->value;
    		outTreeDLR(root->lTree);
    		outTreeDLR(root->rTree);
    	}
    }
    
    //二叉树的中序遍历
    void outTreeLDR(TreeNode* root) {
    	//中序遍历可以通过递归的方式来实现或者非递归的方式来实现
    
    	if (root) {
    
    		//递归按照LDR(中左右)的顺序进行实现
    		outTreeLDR(root->lTree);
    		cout << root->value;
    		outTreeLDR(root->rTree);
    	}
    }
    
    //二叉树的后序遍历
    void outTreeLRD(TreeNode* root) {
    	//中序遍历可以通过递归的方式来实现或者非递归的方式来实现
    
    	if (root) {
    
    		outTreeLRD(root->lTree);
    		outTreeLRD(root->rTree);
    		cout << root->value;
    	}
    }
    
    //二叉树的复制操作
    void cloneTree(TreeNode* root, TreeNode* &newRoot) {
    	if (root == NULL) {
    		newRoot = NULL;  //递归结束标志
    		return;
    	}
    	else {
    		newRoot = new TreeNode(root->value);
    
    		cloneTree(root->lTree, newRoot->lTree);
    		cloneTree(root->rTree, newRoot->rTree);
    	}
    }
    
    //计算二叉树的深度
    int treeDepth(TreeNode* root) {
    	//二叉树的深度计算为：左子树或者右子树中深度比较大的加上1,通过递归的方式来计算
    	if (root == NULL) {
    		return 0;
    	}
    	else {
    
    		int lDepth = 0;
    		lDepth = treeDepth(root->lTree);
    		int rDepth = 0;
    		rDepth = treeDepth(root->rTree);
    
    		if (lDepth >= rDepth) {
    			return lDepth + 1;
    		}
    		else {
    			return rDepth + 1;
    		}
    	}
    }
    
    //计算二叉树的节点数量
    int treeNodeNum(TreeNode* root) {
    	//计算二叉树的节点数量，整棵树的节点数 == 左半边的节点数 + 右半边的节点数
    	if (root == NULL) {
    		return 0;
    	}
    	else
    	{
    		int lnum = 0;
    		lnum = treeNodeNum(root->lTree);
    
    		int rnum = 0;
    		rnum = treeNodeNum(root->rTree);
    
    		return rnum + lnum + 1;
    	}
    }
    
    //计算二叉树的叶子节点的数量
    int treeleNodeNum(TreeNode* root) {
    	//计算二叉树的叶子节点的数量    叶子节点 == 左子树的叶子节点 + 右子树的叶子节点
    	if (root == NULL) {
    		return 0;//递归结束标志
    	}
    	else {
    
    		if (root->lTree == NULL && root->rTree == NULL) {
    			return 1;
    		}
    
    		return treeleNodeNum(root->rTree) + treeleNodeNum(root->lTree);
    	}
    }
    
    //查找某个值为value的节点在不在二叉树中，如果在返回其左右子树,如果不在返回false
    bool search(TreeNode* root, char value) {
    	if (root == NULL) {
    		return false;
    	}
    	else {
    		if (root->value == value ) {
    			if (root->lTree != NULL) {
    				cout << root->lTree->value << endl;;
    			}
    			else {
    				cout << "lTree is NULL" << endl;
    			}
    			if (root->rTree != NULL) {
    				cout << root->rTree->value << endl;;
    			}
    			else {
    				cout << "rTree is NULL" << endl;
    			}
    			return true;
    		}
    		return search(root->lTree, value) || search(root->rTree, value);
    	}
    }
    
    //计算二叉树的度数为1的节点数
    int treeDegree_1(TreeNode* root) {
    	//二叉树的度 == 左子树的度 + 右子树的度
    	if (root == NULL) {
    		return 0;//递归结束条件
    	}
    	else {
    
    		int num = 0;
    
    		num = treeDegree_1(root->lTree) + treeDegree_1(root->rTree);
    
    		if ((root->lTree == NULL && root->rTree != NULL) || (root->lTree != NULL && root->rTree == NULL))
    		{
    			return  num + 1;
    		}
    		else {
    			return num;
    		}
    	}
    }

**数据结构菜鸟上路咯！**

[Link 1]: https://blog.csdn.net/struggleshu/article/details/51051140