数据结构二叉树题目
发布网友
发布时间：2022-05-29 20:02
共2个回答
热心网友
时间：2023-11-18 05:59
下面是c++的代码。 主要是一个递归的思维。收好都是我自己写的，能用
//BinTree.h 定义
{
int data;
Node *lchild,*rchild;
};
class BinTree
{
Node *Root;
public:
BinTree();
BinTree(char pre[]);
BinTree(char pre[],char mid[],int n);
virtual ~BinTree();
void PreOrder();
void MidOrder();
void PostOrder();
Node * Search(int x);
int Count();
int LeafCount();
int Depth();
private:
void PreOrder(Node *p);
void MidOrder(Node *p);
void PostOrder(Node *p);
Node * Search(Node *p, int x);
int Count(Node *p);
int LeafCount(Node *p);
int Depth(Node *p);
Node *CreateByPre(char pre[],int &i);
Node *CreateByPreMid(char pre[],int ipre, char mid[], int imid,int n);
};
//BinTree.cpp
#include "BinTree.h"
BinTree::BinTree() //无参构造函数
{
Root = NULL;
}
BinTree::BinTree(char pre[])
{
int i = 0;
Root = CreateByPre(pre, i);
}
Node *BinTree::CreateByPre(char pre[], int &i)
{
char c = pre[i]; i++;
if(c == '*') return NULL;
Node *p = new Node;p->data = c-'0';
p->lchild = CreateByPre(pre, i);
p->rchild = CreateByPre(pre, i);
return p;
}
//根据先序序列中序序列 创建二叉树
BinTree::BinTree(char pre[], char mid[], int n)
{
Root = CreateByPreMid(pre, 0, mid, 0, n);
}
//先序序列: pre[ipre]...pre[ipre+n-1]
//中序序列: mid[imid]...mid[imid+n-1]
Node *BinTree::CreateByPreMid(char pre[], int ipre, char mid[], int imid, int n)
{
if(n <= 0) return NULL;
Node *p = new Node; p->data = pre[ipre] - '0';
for(int i = 0; i < n; i++)
if(mid[imid+i] == pre[ipre])
break;
//先序序列: pre[ipre] (....pre[ipre+i]) (....pre[ipre+n-1])
//中序序列: (mid[imid]....) mid[imid+i] (.....mid[imid+n-1])
p->lchild = CreateByPreMid(pre,ipre+1, mid, imid, i );
p->rchild = CreateByPreMid(pre,ipre+i+1, mid, imid+i+1, n-i-1);
return p;
}
BinTree::~BinTree()
{}
void BinTree::PreOrder()
{
PreOrder(Root); //先序遍历
cout << endl;
}
void BinTree::PreOrder(Node *p)
{
if(p == NULL) return;
cout << p->data << " ";
PreOrder(p->lchild); //先序遍历左子树
PreOrder(p->rchild); //先序遍历右子树
}
void BinTree::MidOrder()
{
MidOrder(Root); //中序遍历
cout << endl;
}
void BinTree::MidOrder(Node *p)
{
if(p == NULL) return;
MidOrder(p->lchild); //中序遍历左子树
cout << p->data << " ";
MidOrder(p->rchild); //中序遍历右子树
}
void BinTree::PostOrder()
{
PostOrder(Root); //中序遍历
cout << endl;
}
void BinTree::PostOrder(Node *p)
{
if(p == NULL) return;
PostOrder(p->lchild); //后序遍历左子树
PostOrder(p->rchild); //后序遍历右子树
cout << p->data << " ";
}
//深度，即二叉树的高度
int BinTree::Depth()
{
return Depth(Root);
}
int BinTree::Depth(Node *p)
{
if(p == NULL) return 0;
int left = Depth(p->lchild);
int right = Depth(p->rchild);
if(left > right)
return left + 1;
else
return right + 1;
}
//查询值x的节点
Node * BinTree::Search(int x)
{
return Search(Root,x);
}
Node * BinTree::Search(Node *p, int x)
{
if(p == NULL) return NULL;
if(p->data == x) return p;
Node *q = Search(p->lchild,x); //按照先序 查找左子树
if(q != NULL) return q;
return Search(p->rchild,x); //按照先序 查找右子树
}
//所有节点个数
int BinTree::Count()
{
return Count(Root);
}
int BinTree::Count(Node *p)
{
if(p==NULL) return 0;
int left = Count(p->lchild);
int right= Count(p->rchild);
return left+right+1;
}
//所有叶子节点的个数
int BinTree::LeafCount()
{
return LeafCount(Root);
}
int BinTree::LeafCount(Node *p)
{
if(p==NULL) return 0;
if(p->lchild==NULL && p->rchild==NULL) return 1;
int left =LeafCount(p->lchild);
int right=LeafCount(p->rchild);
return left+right;
}
热心网友
时间：2023-11-18 05:59
int val;
//左孩子
TreeNode left;
//右孩子
TreeNode right;
}
二叉树的题目普遍可以用递归和迭代的方式来解
1. 求二叉树的最大深度
int maxDeath(TreeNode node){
if(node==null){
return 0;
}
int left = maxDeath(node.left);
int right = maxDeath(node.right);
return Math.max(left,right) + 1;
}
2. 求二叉树的最小深度
int getMinDepth(TreeNode root){
if(root == null){
return 0;
}
return getMin(root);
}
int getMin(TreeNode root){
if(root == null){
return Integer.MAX_VALUE;
}
if(root.left == null&&root.right == null){
return 1;
}
return Math.min(getMin(root.left),getMin(root.right)) + 1;
}
3. 求二叉树中节点的个数
int numOfTreeNode(TreeNode root){
if(root == null){
return 0;
}
int left = numOfTreeNode(root.left);
int right = numOfTreeNode(ro
