高中网站制作,大专毕业证怎么弄一个,自己制作招聘的小程序,wordpress 媒体插件将第一组n个互不相同的正整数先后插入到一棵空的二叉查找树中#xff0c;得到二叉查找树T1#xff1b;再将第二组n个互不相同的正整数先后插入到一棵空的二叉查找树中#xff0c;得到二叉查找树T2。判断T1和T2是否是同一棵二叉查找树。 二叉查找(搜索)树定义得到二叉查找树T1再将第二组n个互不相同的正整数先后插入到一棵空的二叉查找树中得到二叉查找树T2。判断T1和T2是否是同一棵二叉查找树。 二叉查找(搜索)树定义 ①要么二叉查找树是一颗空树。
②要么二叉查找树由根节点、左子树、右子树构成其中左子树和右子树都是二叉查找树且左子树上所有结点的数据域都小于或等于根结点的数据域右子树上所有的结点的数据域均大于根节点的数据域。
由定义可以发现这么一个二叉查找树的性质
二叉查找树如果中序遍历左儿子根结点右儿子得到的必定是一个由小到大的有序序列。
而正是因为这么一个性质才被称为查找树。
回到本题解题思路
根据给定的两组数进行建立二叉查找树然后进行先序遍历得到序列若二者的先序遍历序列相等则说明为同一棵树。
完整代码如下
#include iostream
#include vector
using namespace std;struct node{int data;int lchild;int rchild;
}nodes[51];int nodecount 0;
vectorint tree1,tree2;void PreOrderTraverse(int root,vectorint tree){//注意要用引用这样才改变内容不然只是浅拷贝。if(root -1){return;}tree.push_back(nodes[root].data);PreOrderTraverse(nodes[root].lchild,tree);PreOrderTraverse(nodes[root].rchild,tree);
}int newNode(int data){nodes[nodecount].data data;nodes[nodecount].lchild -1;nodes[nodecount].rchild -1;return nodecount;
}int insert(int root,int data){if(root -1){//若根结点为-1则说明找到了插入的位置。return newNode(data);}if(datanodes[root].data){//利用二叉查找树的性质nodes[root].lchild insert(nodes[root].lchild,data);}else{nodes[root].rchild insert(nodes[root].rchild,data);}return root;
}int buildtree(int n,int data[]){nodecount 0;int root -1;//一开始树为空。for(int i0;in;i){root insert(root,data[i]);}return root;
}int main(){int n;cinn;int data[n];for(int i0;in;i){cindata[i];}int root buildtree(n,data);PreOrderTraverse(root,tree1);for(int i0;in;i){cindata[i];}root buildtree(n,data);PreOrderTraverse(root,tree2);if(tree1tree2){coutYesendl;}else{coutNoendl;}return 0;
}
