设计一个算法求二叉树bt的最小枝长

Question

假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储，设计一个算法求二叉树bt的最小枝长，所谓最小枝长指的是根结点到最近叶子结点的路径长度。

Answer 1

• 这篇博客也许可以解决你的问题👉 ：设计一个递归算法由二叉树BT复制产生另一棵二叉树BT1（假设二叉树采用二叉链存储结构）
• 除此之外, 这篇博客: 设计一个递归算法由二叉树BT复制产生另一棵二叉树BT1（假设二叉树采用二叉链存储结构）中的 设计一个递归算法由二叉树BT复制产生另一棵二叉树BT1（假设二叉树采用二叉链存储结构） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 源代码如下：

  #include <iostream>
  using namespace std;
  
  //二叉树的结构
  typedef struct BTNode {
  	char data;
  	struct BTNode *left;
  	struct BTNode *right;
  }BTNode;
  
  //由二叉树BT复制产生另一棵二叉树BT1
  void copyBTree(BTNode*BT, BTNode*&BT1) {
  	if (BT==NULL) {
  		BT1 = NULL;
  	}else{
  		BT1 = (BTNode*)malloc(sizeof(BTNode));
  		BT1->data = BT->data;
  		copyBTree(BT->left, BT1->left);
  		copyBTree(BT->right, BT1->right);
  	}
  
  
  }
  
  
  //根据先序序列和中序序列递归创建二叉树
  BTNode * BTCreate(char a[], char b[], int n) {
  	int k;
  	if (n == 0) {
  		return NULL;
  	}
  	int root = a[0];
  	BTNode *BT = (BTNode *)malloc(sizeof(BTNode));
  	BT->data = root;   //树根的值可以确定了
  
  	for (k = 0; k < n; k++) {                  //在b中查找b[k]=root的根节点
  		if (b[k] == root) {
  			break;
  		}
  	}
  	BT->left = BTCreate(a + 1, b, k);               //递归创建左子树
  	BT->right = BTCreate(a + k + 1, b + k + 1, n - k - 1);        //递归创建右子树
  	return BT;
  }
  
  void PreOrder(BTNode *BTNode)
  {
  	if (BTNode == NULL)
  		return;
  	cout << BTNode->data << " ";
  
  	PreOrder(BTNode->left); //递归调用，先序遍历左子树 
  	PreOrder(BTNode->right); //递归调用，先序遍历右子树 
  
  }
  
  
  
  int main() {
  	int n = 0;
  	cout << "请输入序列个数" << endl;
  	cin >> n;
  
  	char *a = new char[n];
  	cout << "请输入先序序列" << endl;
  	for (int i = 0; i < n; i++) {
  		cin >> a[i];
  	}
  
  	char *b = new char[n];
  	cout << "请输入中序序列" << endl;
  	for (int i = 0; i < n; i++) {
  		cin >> b[i];
  	}
  
  	BTNode *BT = NULL;
  	BT = BTCreate(a, b, n);        //创建成功
  	PreOrder(BT);                    //检验是否创建成功
  	cout << endl;
  	BTNode *BT1 = NULL;
  	
  	copyBTree(BT, BT1);
  	
  	PreOrder(BT1);           //检验是否复制成功
  	cout << endl;
  
  
  	system("pause");
  	return 0;
  }

  输出为：

  请输入序列个数
  8
  请输入先序序列
  a b d g c e f h
  请输入中序序列
  d g b a e c h f
  a b d g c e f h
  a b d g c e f h
  请按任意键继续. . .