精华内容
下载资源
问答
  • 2021-11-19 16:55:21

    C++中二叉树的构建及使用:


    二叉树的构建:

    代码:

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

    二叉树的初始化:

    代码:

    TreeNode* creatTreeNode(TreeNode* root, int val)
    {
    	if (root == nullptr)
    	{
    		root = new TreeNode();
    		root->val = val;
    		return root;
    	}
    
    	if (val < root->val)
    	{
    		root->left = creatTreeNode(root->left, val);
    	}
    	else if (val > root->val)
    	{
    		root->right = creatTreeNode(root->right,val);
    	}
    
    	return root;
    }
    

    二叉树的使用:

    简单的实现一个先序遍历功能来演示二叉树的使用:

    void preOrder(TreeNode* root)
    {
    	if (root == nullptr)
    	{
    		return;
    	}
    	cout << root->val;
    	preOrder(root->left);
    	preOrder(root->right);
    }
    

    完整代码:

    #include <iostream>
    #include <vector>
    using namespace std;
    
    struct TreeNode
    {
    	int val;
    	struct TreeNode* left;
    	struct TreeNode* right;
    	struct TreeNode() :left(nullptr), right(nullptr) {}
    };
    
    TreeNode* creatTreeNode(TreeNode* root, int val)
    {
    	if (root == nullptr)
    	{
    		root = new TreeNode();
    		root->val = val;
    		return root;
    	}
    
    	if (val < root->val)
    	{
    		root->left = creatTreeNode(root->left, val);
    	}
    	else if (val > root->val)
    	{
    		root->right = creatTreeNode(root->right,val);
    	}
    
    	return root;
    }
    
    void preOrder(TreeNode* root)
    {
    	if (root == nullptr)
    	{
    		return;
    	}
    	cout << root->val;
    	preOrder(root->left);
    	preOrder(root->right);
    }
    
    int mian()
    {
    	//二叉树的构造与遍历
    	vector<int> vecTree;
    	vecTree.push_back(5);
    	vecTree.push_back(4);
    	vecTree.push_back(6);
    	vecTree.push_back(3);
    	vecTree.push_back(7);
    	TreeNode* root = nullptr;
    	for (int i = 0; i < vecTree.size(); i++)
    	{
    		root = creatTreeNode(root,vecTree[i]);
    	}
    	preOrder(root);
    	cout << endl;
    	
    	getchar();
    	return 0;
    }
    

    更多相关内容
  • 包含一下方法: 1.通过一个数组来构造一颗二叉树 2.通过一个数组来构造一颗完全二叉树 3.使用递归 先序遍历一棵二叉树 4.使用递归 中序遍历一棵...PS:代码为C++代码 可以直接下载使用!!! PS2:每句代码都有详细注释
  • C++二叉树的创建与遍历实验报告 作者: 日期 ? 二叉树的创建与遍历 一 实验目的 1.学会实现二叉树结点结构和对二叉树的基本操作 2.掌握对二叉树每种操作的具体实现学会利用递归和非递归方法编写对二叉树这种递归数据...
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • 在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多...
  • C++二叉树

    千次阅读 2020-07-31 11:05:14
    本篇主要写二叉树的结构,中序、前序、后序、层序遍历算法。 二叉树的结构,本篇以如下这个二叉树进行遍历: 中序遍历:左子节点---->中间节点---->右子节点 前序遍历:中间节点----->左子节点---->...

    本篇主要写二叉树的结构,中序、前序、后序、层序遍历算法。

    二叉树的结构,本篇以如下这个二叉树进行遍历:

    中序遍历:左子节点---->中间节点---->右子节点

    前序遍历:中间节点----->左子节点---->右子节点

    后序遍历:  左子节点----->右子节点----->中间节点

    层序遍历:一层一层的从上往下遍历

    以上图二叉树结构为例,开始编写代码:

    #include <iostream>
    #include <queue>
    using namespace std;
    
    
    template <class T> class BinaryTree;
    
    
    template <class T>
    class TreeNode
    {
    	template <class T>
    	friend class BinaryTree;
    public:
    
    	TreeNode(const T & d):data(d)
    	{
    		leftChild = rightChild = NULL;
    	}
    //private:
    	T data;
    	TreeNode *leftChild;
    	TreeNode *rightChild;
    
    };
    
    template <class T>
    class BinaryTree
    {
    public:
    	void InOrder(); //中序遍历    左->中->右
    	void InOrder(TreeNode<T> * current);  
    	void PreOrder(); //前序遍历  中->左->右
    	void PreOrder(TreeNode<T> *current);
    	void PostOrder();//后序遍历  左->右->中
    	void PostOrder(TreeNode<T>*current);
    	void LevelOrder(); //层序遍历
    	void Visit(TreeNode<T>*current);
    
    	int getTreeHight(TreeNode<T>* root);  //计算思路:树的深度=左链的深度和右链深度的最大值 +1
    
    	TreeNode<T> *  getRoot()
    	{
    		return root;
    	}
    
    //private:
    	TreeNode<T> *root;
    
    };
    
    template <class T>
    void BinaryTree< T>::Visit(TreeNode<T>*current)
    {
    	if (current)
    		cout << current->data << " ";
    }
    template <class T>
    void BinaryTree< T>::InOrder(TreeNode<T>*current)
    {
    	if (current)
    	{
    		InOrder(current->leftChild);
    		Visit(current);
    		InOrder(current->rightChild);
    	}
    }
    template <class T>
    void BinaryTree< T>::InOrder()
    {
    	InOrder(root);
    }
    template <class T>
    void BinaryTree<T>::PreOrder()
    {
    	PreOrder(root);
    }
    template <class T>
    void BinaryTree<T>::PreOrder(TreeNode<T> *current)
    {
    	if (current)
    	{
    		Visit(current);
    		PreOrder(current->leftChild);
    		PreOrder(current->rightChild);
    	}
    }
    
    template <class T>
    void BinaryTree<T>::PostOrder()
    {
    	PostOrder(root);
    }
    
    template <class T>
    void BinaryTree<T>::PostOrder(TreeNode<T> *current)
    {
    	if (current)
    	{
    		PostOrder(current->leftChild);
    		PostOrder(current->rightChild);
    		Visit(current);
    	}
    }
    
    template <class T>
    void BinaryTree<T>::LevelOrder()
    {
    	//层序遍历,充分利用了queue先进先出的特点
    	queue<TreeNode<T>* > q;
    
    	TreeNode<T>* current = root;
    
    	while (current)
    	{
    		Visit(current);
    		if (current->leftChild) q.push(current->leftChild); //先把左子节点放到队列
    		if (current->rightChild) q.push(current->rightChild); //再把右子节点放到队列
    
    		if (q.empty()) return;  //到队列空的时候就返回
    
    		current = q.front(); //当前指针指向先放进去的指针
    		q.pop();  //将上边这个弹出队列
    	}
    }
    
    template <class T>
    int BinaryTree<T>::getTreeHight(TreeNode<T>* root) 
    {
    	if (NULL == root)
    		return 0;
    
    	int leftHigh = getTreeHight(root->leftChild);
    	int rightHigh = getTreeHight(root->rightChild);
    
    	int maxHigh = leftHigh >= rightHigh ? leftHigh + 1 : rightHigh + 1;
    
    	return maxHigh;
    
    }
    
    int main()
    {
    	TreeNode<char> node1('+'),node2('-'), node3('*'), node4('/'), node5('A'), node6('B'), node7('C'), node8('D'), node9('E');
    
    	BinaryTree<char> tree;
    	
    
    	tree.root = &node1;
    
    	node1.leftChild = &node2;
    	node1.rightChild = &node9;
    
    	node2.leftChild = &node3;
    	node2.rightChild = &node8;
    
    	node3.leftChild = &node4;
    	node3.rightChild = &node7;
    
    	node4.leftChild = &node5;
    	node4.rightChild = &node6;
    
    	//中序遍历
    	cout << "中序遍历:   ";
    	tree.InOrder();
    	cout << endl;
    
    	//前序遍历
    	cout << "前序遍历:   ";
    	tree.PreOrder();
    	cout << endl;
    
    	//后序遍历
    	cout << "后序遍历:  ";
    	tree.PostOrder();
    	cout << endl;
    
    	//层序遍历
    	cout << "层序遍历  ";
    	tree.LevelOrder();
    	cout << endl;
    
    
    	cout << "树的深度 ";
    	cout << tree.getTreeHight(tree.getRoot())<<endl;
    
    	return 0;
    }

    运行结果:

     

     

     

    展开全文
  • 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点
  • c++二叉树代码
  • C++二叉树的创建与一些基本使用

    千次阅读 2022-03-15 15:16:24
    C++二叉树通过队列创建以及一些基本的使用

    二叉树的基本组成

    结构体和类的构造和使用方法非常像,所以,在C++中,结构体也存在无参和有参构造;可以根据自己的需求来定义。

    struct BiNode{
        int val;
        BiNode *lchild,*rchild;
        //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}
        // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
        // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}
    };
    

    创建二叉树

    这里我是通过队列的方式来创建二叉树的
    每创建一个节点,就拿出一个数

    void CreateTree(BiNode* &root,queue<int>& dp){   //通过队列创建二叉树
        if(dp.empty()) return ;
        int n=dp.front();
        dp.pop();
        if(n==0){   //等于0时,就是空节点
            return;
        }
        else{
            root =new BiNode();
            root->val=n;
            CreateTree(root->lchild,dp);
            CreateTree(root->rchild,dp);
        }
    }
    

    二叉树的4种常用遍历

    先序遍历

    void preOrder(BiNode* root){    //前序遍历
        if(root){
            cout<<root->val<<" ";
            preOrder(root->lchild);
            preOrder(root->rchild);
        }
    }
    

    中序遍历

    void inOrder(BiNode* root){    //中序遍历
        if(root!=NULL){        
            inOrder(root->lchild);
            cout<<root->val<<" ";
            inOrder(root->rchild);
        }
    }
    

    后序遍历

    void postOrder(BiNode* root){    //后序遍历
        if(root){        
            postOrder(root->lchild);        
            postOrder(root->rchild);
            cout<<root->val<<" ";
        }
    }
    

    层序遍历

    前面的三种先、中、后遍历方法,很常用,也很简单,基本上学会了其中一种,另外两种自然也就会了,只要调换一下位置就行了,原理非常简单;
    第四种方法:层序遍历,也是非常的常用,使用的场景也很多,我这里是使用两重vector容器,把它的每一层都单独放在一起,在一般的做题或者其他场景,不需要这么细致的话,使用一维vector也是一样的。

    vector<vector<int>> levelOrder(BiNode*& root) {  //层序遍历
        vector<vector<int>> res;
        if(root==NULL)  return res;   
        queue<BiNode*> dp;
        dp.push(root);
    
        while(!dp.empty()){  //如果队列为空,则已经遍历完毕
            int n=dp.size();    //获取队列的大小,也就是这一层的节点数
            res.push_back(vector<int> ());
            for(int i=1;i<=n;i++){  //每一次都把这一层的所有节点输出,遍历完这一层的,队列剩下的就是下一层的
                auto p=dp.front();dp.pop();
                res.back().push_back(p->val);
                if(p->lchild)     dp.push(p->lchild);   //把非空的节点加入队列
                if(p->rchild)    dp.push(p->rchild);
            }
        }
        return res;
    }
    

    在二叉树中查找值为val的节点

    思路:
    1、当root == NULL; return NULL;
    2、当root->val ==num; return root;
    3、当root->val!=num ; 则先去左子树中找,FindNode(root->lchild,num);
    4、以上都不满足,则去右子树找

    BiNode* FindNode(BiNode* &root,int num){
        BiNode* p;
        if(!root)   return NULL;	//节点为空
        else if (root->val==num)    return root;
        else{
            
            p=FindNode(root->lchild,num);
            if(p){
                return p;
            }
            else{
                return FindNode(root->rchild,num);
            }
        }
    }
    

    二叉树的高度(深度)

    直接递归左右子树,比大小

    int HeightTree(BiNode* root){
        if(!root)   return 0;
        return max(HeightTree(root->lchild),HeightTree(root->rchild))+1;
    }
    

    查找二叉树中的叶子节点

    通过叶子节点性质,直接查找左右子节点都为空的节点,把它加入进vector数组

    void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode){
        if(root){
            if(!root->lchild && !root->rchild){
                leafnode.push_back(root);
                return;
            }
            if(root->lchild)    FindLeaf(root->lchild,leafnode);
            if(root->rchild)    FindLeaf(root->rchild,leafnode);
        }
    }
    

    以上就是本次介绍的关于二叉树的创建以及一些基本的使用
    这是本次演示所使用的二叉树
    这是本次演示所使用的二叉树,下面附上一下演示的代码

    #include<iostream>
    #include<vector>
    using namespace std;
    #include<queue>
    
    struct BiNode{
        int val;
        BiNode *lchild,*rchild;
        //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}
        // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {}
        // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}
    };
    
    void CreateTree(BiNode* &root,queue<int>& dp);  //创建二叉树
    
    void preOrder(BiNode* root);    //先序遍历
    void inOrder(BiNode* root);     //中序遍历
    void postOrder(BiNode* root);   //后序遍历
    vector<vector<int>> levelOrder(BiNode*& root);  //层序遍历,一层层的输出
    
    //template<class T> 
    BiNode* FindNode(BiNode* &root,int val);    //查找值为val 的结点,找到了返回该节点地址,没找到则返回NULL
    int HeightTree(BiNode* root);   //求二叉树的高度(深度)
    void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode);    //查找到叶子节点,并输出
    
    //中间的函数在上面,就不再写了
    int main(){
        BiNode* root;
        queue<int> dp;
        vector<int> arr={1,2,4,0,6,0,0,0,3,0,5,0,0};
        for(int i=0;i<arr.size();i++){
            dp.push(arr[i]);
        }
        //创建二叉树
        CreateTree(root,dp);
        
        //先、中、后三中遍历
        cout<<"preOrder: "<<endl;
        preOrder(root);
        cout<<"\ninOrder: "<<endl;
        inOrder(root);
        cout<<"\npostOrder: "<<endl;
        postOrder(root);
        cout<<"\nlevelOrder:  "<<endl;
    
    	//层序遍历,一层层的输出
        vector<vector<int>> res=levelOrder(root);
        for(auto &ch:res){  //一层一层的输出
            for(auto &num:ch){
                cout<<num<<" ";
            }
            cout<<endl;
        }
    	
    	//查找指定节点,这里我是没有定义,直接给了一个固定值10,纯属是为了演示
        BiNode* findnode;
        findnode=FindNode(root,10);
        if(findnode){
            cout<<"findnode->val="<<findnode->val<<endl;
        }
        else{
            cout<<"This node does not exist in this binary tree! "<<endl;
        }
    	
    	//定义了一个ans,接收该二叉树的高度
        int ans=HeightTree(root);
        cout<<"The height of the binary tree is "<<ans<<endl;
    	
    	//查找该二叉树的叶子节点,并输出
        vector<BiNode*> leafnode(dp.size());
        FindLeaf(root,leafnode);
        for(auto& leaf:leafnode){
            cout<<leaf->val<<" ";
        }
        cout<<endl;
    }
    

    疑问,希望有大佬能够帮忙解惑!

    以上便是我本次学习所得,不过有一个疑问,
    在我用struct定义二叉树的基本结构的时候,如果我写了无参构造

    BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}
    

    那么我在创建二叉树的时候,无论是

    BiNode* root =new BiNode();
    

    亦或是

    BiNode* root =new BiNode;
    

    都可以运行,且得出的答案都一样,
    但如果我不写这个无参构造
    那么第二种定义,在vscode中,虽然不会报错,但不会得出答案,便直接结束了。在网上找了很久,依然没有找到,希望有懂得大佬看到了能帮忙解惑,先谢谢了!

    上述问题的原因

    上述问题,在前一段时间困扰了我很久,一直没找到原因。
    直到今天终于找到了,原来:
    在自定义的数据类型中

    1. 如果该类没有定义构造函数(由编译器合成默认构造函数)也没有虚函数,那么BiNode *root= new BiNode ;将不调用合成的默认构造函数,而BiNode *root = new BiNode ();则会调用默认构造函数。
    2. 如果该类没有定义构造函数(由编译器合成默认构造函数)但有虚函数,那么BiNode *root= new BiNode ;和BiNode *root= new BiNode ();一样,都会调用默认构造函数。
    3. 如果该类定义了默认构造函数,那么BiNode *root= new BiNode ;和BiNode *root= new BiNode ();一样,都会调用默认构造函数。

    在内置的数据类型中,也是有区别的,但是因为现在还没有搞懂,所以就不写了。等以后明白了再回来补充!

    展开全文
  • 主要介绍了C++ 二叉树的镜像实例详解的相关资料,需要的朋友可以参考下
  • C++ 二叉树常见用法

    2020-06-17 10:41:58
    二叉树的创建: 上篇文章遍历的时候二叉树的创建是这样的: TreeNode* T1 = new TreeNode(8); TreeNode* T2 = new TreeNode(8); TreeNode* T3 = new TreeNode(7); TreeNode* T4 = new TreeNode(9); TreeNode* ...

    二叉树的创建:

    上篇文章遍历的时候二叉树的创建是这样的:

    	TreeNode* T1 = new TreeNode(8);
    	TreeNode* T2 = new TreeNode(8);
    	TreeNode* T3 = new TreeNode(7);
    	TreeNode* T4 = new TreeNode(9);
    	TreeNode* T5 = new TreeNode(2);
    	TreeNode* T6 = new TreeNode(4);
    	TreeNode* T7 = new TreeNode(7);
    	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;
    

    显然这种创建方式很繁琐,当二叉树分枝不多的情况下可以这样创建,但是复杂的时候我们就需要一种方便简洁的创建方式。之所以没有先讲二叉树的创建是因为创建方式依靠的背景不一样。还记得前序遍,中序遍历和后序遍历没。一般二叉树的创建是依靠遍历创建的。

    我们依照前序遍历的准则创建二叉树:
    创建的二叉树如下图所示,#代表为空,因为我们定义的是int型而不是char型,故下面的代码把#看成0输入为空。
    在这里插入图片描述

    下面代码用了两种构建方式:
    第一种的前序遍历如图;
    前序遍历的方式输入:889002007400700
    
    #include<iostream>
    #include<queue>
    using namespace std;
    struct TreeNode {
    	int data;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode(int x):
    		data(x),left(NULL),right(NULL){}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         
    };
    void preprintftree(TreeNode* root) {   //前序遍历
    	if (root) {
    		cout << root->data;    // 打印根结点
    		preprintftree(root->left); // 前序遍历左子树
    		preprintftree(root->right); // 前序遍历右子树
    	}
    	else
    		root = NULL;
    }
    void preCreateTree(TreeNode* &T)  // 前序遍历创建二叉树,需要注意* &T目的是让传递进来的指针发生改变
    {
    	int data;
    	cin >> data;
    	if (data == 0)
    	{
    		T = nullptr;
    	}
    	else
    	{
    		T = new TreeNode(data); //构造结点
    		preCreateTree(T->left);  //递归创建左子树
    		preCreateTree(T->right); //递归创建右子树
    	}
    }
    int main()
    {
    	TreeNode* T1 = new TreeNode(8);
    	TreeNode* T2 = new TreeNode(8);
    	TreeNode* T3 = new TreeNode(7);
    	TreeNode* T4 = new TreeNode(9);
    	TreeNode* T5 = new TreeNode(2);
    	TreeNode* T6 = new TreeNode(4);
    	TreeNode* T7 = new TreeNode(7);
    	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;
    	cout << "普通创建方式:" << endl;
    	preprintftree(T1);
    	cout << endl;
    	TreeNode* Tree=nullptr;
    	cout << "前序遍历创建方式:" << endl;
    	preCreateTree(Tree);
    	cout << "前序遍历结果:" << endl;
    	preprintftree(Tree);
    	return 0;
    }
    

    代码结果如下所示:
    在这里插入图片描述

    二叉树的重建

    二叉树的创建讲完了,下面介绍二叉树的重建:
    先了解:

    	已知前序遍历和中序遍历可以确定唯一的二叉树;
    	已知后序遍历和中序遍历可以确定唯一的二叉树;
    	但是已知前序和后序不能确定。
    

    已知二叉树的前序和中序,重建二叉树:

    前序为:{ 1,2,4,7,3,5,6,8 }
    中序为:{ 4,7,2,1,5,3,8,6 }
    解题思路:
    先序遍历规则:根节点==》左子树==》右子树
    
    中序遍历规则:左子树==》根节点==》右子树
    
    分析题目可知,二叉树中的节点值均是唯一的,不存在重复值。所以,
    我们可以利用二叉树先序遍历和中序遍历特点,完成如下的工作:
    
    Step1:确定根节点,即先序遍历preorder中的首个节点;
    Step2:在中序遍历inorder中找到根节点的索引值index,以此为界,将中序遍历序列划分为
    【左子树,根节点,右子树】,其中,左子树为索引值0至index,即inorder[0:index],
    右子树为index+1至中序遍历末尾元素,即inorder[index+1:];
    Step3:根据中序遍历序列中左右子树的节点数量,将先序遍历序列划分为【根节点,左子树,右子树】,
    其中,左子树为索引值1至index+1,即preorder[1:index+1],
    右子树为index+1至先序遍历末尾元素,即preorder[index+1:];
    Step4:分别利用先序遍历和中序遍历中的左子树递归构造二叉树的左子树,
    先序遍历和中序遍历中的右子树递归构造二叉树的右子树
    
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct treeNode {
        int data;
        treeNode* left;
        treeNode* right;
        treeNode(int x) :
            data(x),left(NULL), right(NULL) {}
    };
    treeNode* buildtree(vector<int>& pre, vector<int>& vin) {
        if (pre.size() == 0 || vin.size() == 0) return nullptr;
        int val = pre[0];
        treeNode* root = new treeNode(val);
        int index = 0;
        for (int i =0; i<vin.size(); i++)
            if (vin[i] == pre[0]) {
                index = i;
                break;
            }
        vector<int> preleft(pre.begin() + 1, pre.begin() + index+1);
        vector<int> vinleft(vin.begin() , vin.begin() + index);
        vector<int> preright(pre.begin() + index +1,pre.end());
        vector<int> vinright(vin.begin() + index +1,vin.end());
        root->left = buildtree(preleft, vinleft);
        root->right = buildtree(preright, vinright);
        return root;
    }
    void postprintfTree(treeNode* root) {
        if (root!=nullptr) {
            postprintfTree(root->left);
            postprintfTree(root->right);
            cout << root->data;
        }
        else {
            root = NULL;
        }
    }
    int main()
    {
        vector<int>pre={ 1,2,4,7,3,5,6,8 };
        vector<int>vin={ 4,7,2,1,5,3,8,6 };
        treeNode* tree = buildtree(pre,vin);
        postprintfTree(tree); // 后序打印结果
        return 0;
    }
    

    判断二叉树是否为另一个二叉树的子树:

    思路:
    输入两个二叉树,判断其中的一个是否为另一个的子树:
    1、首先设置标志位flag = false,因为一旦匹配成功flag就设为true,
    剩下的代码不会执行,如果匹配不成功,默认返回false
    2、递归思想,如果根节点相同则递归调用comparetree(),
    如果根节点不相同,则判断tree1的左子树和tree2是否相同,
    再判断右子树和tree2是否相同
    3、注意null的条件,HasSubtree中,如果两棵树都不为空才进行判断,
    comparetree中,如果Tree2为空,则说明第二棵树遍历完了,即匹配成功,
    tree1为空有两种情况(1)如果tree1为空&&tree2不为空说明不匹配,
    (2)如果tree1为空,tree2为空,说明匹配。

    #include<iostream>
    using namespace std;
    struct treeNode {
    	int data;
    	treeNode* left;
    	treeNode* right;
    	treeNode(int x):
    		data(x),left(NULL),right(NULL){}
    };
    bool comparetree(treeNode* s1, treeNode* s2) {
    	if (s2 == nullptr) return true;
    	if (s1 == nullptr) return false;
    	if (s1->data != s2->data) return false;
    	return comparetree(s1->left, s2->left) && comparetree(s1->right, s2->right);
    }
    bool HasSubtree(treeNode* root1, treeNode* root2)
    {
    	bool flag = false;
    	if (root1 == nullptr || root2 == nullptr) return false;
    	if (root1->data == root2->data) flag = comparetree(root1,root2);
     	if (!flag) flag = HasSubtree(root1->left,root2);
    	if (!flag) flag = HasSubtree(root1->right, root2);
    	return flag;
    }
    void preprintftree(treeNode* root) {
    	if (root) {
    		cout << root->data;
    		preprintftree(root->left);
    		preprintftree(root->right);
    	}
    	else
    		root = NULL;
    }
    int main()
    {
    	treeNode* t1 = new treeNode(8);
    	treeNode* t2 = new treeNode(8);
    	treeNode* t3 = new treeNode(7);
    	treeNode* t4 = new treeNode(9);
    	treeNode* t5 = new treeNode(2);
    	treeNode* t6 = new treeNode(4);
    	treeNode* t7 = new treeNode(7);
    	t1->left = t2; t1->right = t3; t2->left = t4; t2->right = t5; t3->left = t6; t3->right = t7;
    	treeNode* tt1 = new treeNode(8);
    	treeNode* tt2 = new treeNode(9);
    	treeNode* tt3 = new treeNode(2);
    	tt1->left = tt2; tt1->right = tt3;
    	preprintftree(t1);
    	cout << endl;
    	preprintftree(tt1);
    	cout << endl;
    	bool res = HasSubtree(t1, tt1);
    	cout << res << endl;
    	return 0;
    }
    

    二叉树的镜像

    在这里插入图片描述
    这个其实很简单,和swap原理一样。
    核心代码:

    思路:左右分枝对换就行了;
    TreeNode* Mirror(TreeNode* pRoot) {
    	if (pRoot == nullptr) return pRoot;
    	TreeNode* temp;
    	temp = pRoot->left;
    	pRoot->left = pRoot->right;
    	pRoot->right = temp;
    	Mirror(pRoot->left);
    	Mirror(pRoot->right);
    	return pRoot;
    }
    

    总的代码:

    #include<iostream>
    using namespace std;
    struct TreeNode {
    	int data;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode(int x):
    		data(x),left(NULL),right(NULL){}
    };
    TreeNode* Mirror(TreeNode* pRoot) {
    	if (pRoot == nullptr) return pRoot;
    	TreeNode* temp;
    	temp = pRoot->left;
    	pRoot->left = pRoot->right;
    	pRoot->right = temp;
    	Mirror(pRoot->left);
    	Mirror(pRoot->right);
    	return pRoot;
    }
    void preprintftree(TreeNode* root) {
    	if (root) {
    		cout << root->data;
    		preprintftree(root->left);
    		preprintftree(root->right);
    	}
    	else
    		root = NULL;
    }
    int main()
    {
    	TreeNode* T1 = new TreeNode(8);
    	TreeNode* T2 = new TreeNode(8);
    	TreeNode* T3 = new TreeNode(7);
    	TreeNode* T4 = new TreeNode(9);
    	TreeNode* T5 = new TreeNode(2);
    	TreeNode* T6 = new TreeNode(4);
    	TreeNode* T7 = new TreeNode(7);
    	T1->left = T2; T1->right = T3; T2->left = T4; T2->right = T5; T3->left = T6; T3->right = T7;
    	preprintftree(T1);
    	cout << endl;
    	TreeNode* p = Mirror(T1);
    	preprintftree(p);
    	return 0;
    }
    

    判断二叉树是否对称

    由于上面给出了很多二叉树的测试用例,下面介绍的功能函数直接放核心代码函数接口:

    bool isSame(TreeNode* p1,TreeNode* p2)
        {
            if(p1==NULL&&p2!=NULL)return false;
            if(p2==NULL&&p1!=NULL)return false;
            if(p1==NULL&&p2==NULL)return true;
            if(p1->val==p2->val)return isSame(p1->right,p2->left)
                && isSame(p1->left,p2->right);
            else
                return false;
        }
        bool isSymmetrical(TreeNode* pRoot)
        {
            if(pRoot==NULL)return true;        
            return isSame(pRoot->left,pRoot->right);
        }
    

    求二叉树的深度:

    思路:
    从跟节点出发, 查询左子树的深度 , 获取右子树的深度,比较一下,取大的,再加一 。就是整个二叉树的深度
    递归的三个条件
    边界条件:当前节点下,是否还有子节点,没有返回,有继续递归
    递归前进段:当前节点下,还有子节点
    递归返回段:当前节点下,没有子节点

    int TreeDepth1(TreeNode pRoot)
        {
            if(pRoot == null){
                return 0;
            }
            int left = TreeDepth1(pRoot.getLeft());
            int right = TreeDepth1(pRoot.getRight());
            return Math.max(left, right) + 1;
        }
    

    为了便于理解,请看下图:
    在这里插入图片描述

    二叉树是否为平衡二叉树:

    平衡二叉树的定义:如果二叉树的每个节点的左子树和右子树的深度不大于1,它就是平衡二叉树。
    思路:
    最直接的做法,遍历每个结点,借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡,然后递归地对左右子树进行判断。

    public classSolution {
        public boolean IsBalanced_Solution(TreeNode root) {
            if(root == null) {
                return true;
            }
            return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
                IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }
        private int maxDepth(TreeNode root) {
            if(root == null) {
                return 0;
            }
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }
    

    这种做法有很明显的问题,在判断上层结点的时候,会多次重复遍历下层结点,增加了不必要的开销。如果改为从下往上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,则直接停止遍历,这样至多只对每个结点访问一次。

    public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            return getDepth(root) != -1;
        }
        private int getDepth(TreeNode root) {
            if (root == null) return 0;
            int left = getDepth(root.left);
            if (left == -1) return -1;
            int right = getDepth(root.right);
            if (right == -1) return -1;
            return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
        }
    }
    
    展开全文
  • C++二叉树简单介绍

    2020-12-18 08:41:25
    树结构 树结构是一种数据结构,它由结点(node)以及连接结点的边... T没有任何结点 T由以下三个不包含共通元素的顶点集合构成 根(root) 称为左子树(left subtree)的二叉树 称为右子树(right subtree)的二叉树
  • c++二叉树的基本操作

    2015-11-25 22:15:48
    递归二叉树的基本操作,递归创建,递归先序遍历、中序遍历、后序遍历,求树的高度,求叶子结点的个数,交换树的左右孩子
  • C++ 二叉树的层次建树及其遍历

    千次阅读 2022-02-06 10:47:05
    :队列结点的数据域 p 存放的是树结点的地址 ( BiTNode *p 类型 ) ,头指针 phead 指向该队列头部,尾指针 ptail 指向该队列尾部,队列指针 pCur 始终指向当前操作位置,当前操作位置指的是:有新结点加入二叉树时,...
  • 二叉树的顺序存储结构 顺序存储即为在计算机内存中开辟一段连续的内存空间用于存放二叉树的信息。对于一个二叉树,将二叉树按照满二叉树的标号方式,从上到下、从左到右、从0开始,依次给二叉树的结点进行标号。...
  • 主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • C++ 二叉树序列化与反序列化1、题目要求2、题目说明3、核心问题4、解题思路5、代码实现6、问题扩展7、重要说明 1、题目要求   请实现两个函数,分别用来序列化和反序列化二叉树? 2、题目说明   序列化的意思是...
  • C++二叉树的基本操作

    2020-10-28 09:57:18
    二叉树的基本操作(存放整形数组) 1.创建一颗二叉树 60 20 -1 -1 100 -1 2.中序遍历二叉树 3.左右交换算法 4.计算一下二叉树中非终端的个数 5.计算结点的值小于x结点的个数 遍历算法 (函数原型:int countx...
  • C++二叉树实现.zip

    2021-08-20 14:54:28
    C++实现二叉树,包含h文件和测试文件
  • c++二叉树的所有路径

    2020-06-02 18:02:08
    给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明:叶子节点是指没有子节点的节点。 递归(dfs) /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * ...
  • C++二叉树的遍历源码

    2020-06-29 17:19:31
    C++版的二叉树遍历源码,包括:广度优先、深度优先、先序遍历(递归/非递归)、中序遍历(递归/非递归)、后序遍历(递归/非递归)。
  • C++二叉树操作

    2013-12-16 18:12:35
    C++二叉树的操作 其中包括对二叉树的建立,二叉树的先跟遍历 中根遍历 后根遍历 二叉树节点的增添 和删除
  • 二叉树(基于Mfc的程序开发),具有二叉树的先序遍历、中序遍历、后续遍历、以及非递归中序遍历、以及树形控件显示
  • C++二叉树详解ppt

    2018-01-24 10:12:36
    初学者资源,对C++二叉树的详解,哈尔滨理工大学C++课程课件
  • C++二叉树的创建与遍历

    千次阅读 2020-03-19 22:40:05
    最近学习了二叉树的一点知识,感觉数据结构真的很难啊,所以学习过程中的笔记还是要记录一下。 文章目录一、二叉树二、实现代码三、运行效果四、小结 一、二叉树 在我们使用的数据结构中,一对一的线性结构使我们...
  • C++ 二叉树的基本操作

    千次阅读 2020-03-27 14:08:56
    对于一棵二叉树,有三种基本遍历方式: 1、前序遍历(DLR):先访问根结点,然后遍历左子树,最后遍历右子树。 归结为:从根结点一直从左子树向下直到叶结点,然后返回到叶结点的父亲,再从其父结点的右子树向下。 ...
  • c++二叉树打印(只为美观)

    千次阅读 多人点赞 2020-09-30 15:32:16
    } /** * 利用下划线和正反斜杠打印出美观的二叉树,没有破坏二叉树结构,但传入的root会有变化 * @param root 二叉树根节点 */ void printTree(TreeNode *root) { if (!root)return; auto tmp = root; std::vector...
  • C++二叉树实验

    2020-07-26 19:56:55
    C++二叉树实验 实验目的: 1. 熟练掌握二叉链的存储特点; 2. 熟练掌握二叉树的基本操作; 3. 熟练掌握基于二叉链的二叉树操作算法实现; 4. 能灵活使用二叉树解决具体的问题; 实验内容: 1.定义二叉链的类模板,...
  • 数据结构作业 二叉树的建立,递归,非递归的前中后序遍历,注释详细。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 76,701
精华内容 30,680
关键字:

c++ 二叉树

c++ 订阅