如何用C语言实现构造这样的二叉树?

如何用C语言实现构造这样的二叉树?
例如,我忽略(不输入)终止符以先根次序输入ABGHERGSK.二叉树的每个节点存储一个字符,那么我如何才能得到所有可能的二叉树构型??

20 个解决方案

#1

有意思我帮你实现！开工！

#2

楼上开工啊……

#3

好阿~~其实给个算法也成,谢谢啦~~

#4

自己顶~~~

#5

我想了一个办法，挺笨的，先根次序输入ABGHERGSK，只能确定根节点A，通过穷举法把ABGHERGSK可能二叉树都例举出来，再用先根遍历分别遍历这些二叉树，把结果与“ABGHERGSK”同的筛选出来，就得出所有可能的结果了！

#6

我想了一个办法，挺笨的，先根次序输入ABGHERGSK，只能确定根节点A，通过穷举法把ABGHERGSK可能二叉树都例举出来，再用先根遍历分别遍历这些二叉树，把结果与“ABGHERGSK”同的筛选出来，就得出所有可能的结果了！

#7

那这样是不是只有在字符个数比较少的情况下可行啊?
还有~~穷举要怎么实现呢?
其实我是想在其中插入终止符,但也不知道该怎么实现~~

#8

根节点是a，下面有这几种情况：左子树0个右子树8个，左子树1个右子树7个。。。左子树8个右子树0个
分别对应：A(BGHERGSK),(B)A(GHERGSK),...,(BGHERGSK)A
然后递归？

#9

不好意思我研究树的打印去了……
算法不难就是按先序顺序插入节点构造同时枚举所有二叉数。
必须得走了，我明天一定把实现贴上并附上树的完美打印！

#10

sf

#11

看看先

#12

大家好我回来了……
很遗憾树的水平打印还是有点问题，目前只能竖着打印一棵树到屏幕，效果见windows命令行cmd下的tree命令,后面也有展示。
我分条来说！

【原问题】
  如何用C语言实现构造这样的二叉树?
  例如,我忽略(不输入)终止符以先根次序输入ABGHERGSK.二叉树的每个节点存储一个字符,那么我如何才能得到所有可能的二叉树构型?? 

 ABGHERGSK中有两个"G",这里为了方便说明问题这里只考虑输入的元素各不相同的情况,如要处理重复元素只需将输入处理为(A,1)(B,2)(G,3)...(G,7)(S,8)(K,9)结构即可。

【解的个数】
  一个解是一颗树的实例。对于给定的输入串str, 另其长度为n(不含终结符'.'),则所有满足条件的解的个数记为f(n).
  则 f(0) = f(1) = 1. (按照定义空树也是二叉树). 
  现假设设f(0),f(1)..f(n-1)的值已知，来递推f(n)的值.
  如8楼所示,对于一颗满足条件的树，设左子树的结点个数为i, 右子树的节点个数为j,那么对于这种类型的树由乘法原理知其总数有f(i)*f(j)
个，那么对i,j枚举(i+j=n-1)，我们可以得到 f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0).
  数列f(n)的前十项为:{1,1,2,5,14,42,132,429,1430,4862...}.
  f(n)的增长是指数级的。原题要求构造并显示所有的树因此是NP问题。
  级数f(n)也许有个名字，也许有个求和公式，希望知道的朋友指点一下。

【构造方法】
  方法1. 见8楼，但我实现不出，求指点。
  方法2. 按先序次序插入元素构造二叉树树，并对所有可插入点枚举（回溯）。见下图。
  
  假设A、B、C已经加入，现D出队列并将其插入树节点，并保证先序次序为符合元素输入顺序，那么可以插入的位置如上图所示。当D元素插入
完毕的时候接着用同样的方法处理D后面的元素，一旦最后一个元素被插入，就是找到了一个解，将其打印出来。然后D回溯，选择下一个可插入点，继续构造。按照这种回溯枚举的方法便可以穷举出所有解。很暴力但用递归的形式实现比较方便。
  每次往树中插入新节点时先找到先序遍历的最后一个节点（上一次插入的节点），之后才能枚举待插入节点的位置，用found来记录。大致算法如下。

  InsertItem([ref]treenode, item, [ref]found)
  {
     if (treenode为空)
     {
        if (found)
        {
          为treenode分配节点空间;
          把item插入到treenode里去;
        
          if (item是最后一个)
             打印树;

          //回溯
          item从treenode里删除 
          释放treenode
          返回;
        }
        返回; 
     }
     if (treenode是上次插入的节点) found := true;
     InsertItem(treenode.left, item, found)
     InsertItem(treenode.right, item, found)
  }

【树的打印】
   在Console上打印，效果参见控制台上tree命令.
  
   本来想按习惯水平打印但实现遇到了困难,求指点。
   这里垂直打印，需要做个说明：

    Root
   ├─Right Child
   └─Left Child

   注意右子树在上方。

【运行结果】
   控制台上输入: ABCDE.

   输出:


  Instance 1:
A
├─(null)
└─B
  ├─(null)
  └─C
    ├─(null)
    └─D
      ├─(null)
      └─E

Instance 2:
A
├─(null)
└─B
  ├─(null)
  └─C
    ├─(null)
    └─D
      ├─E
      └─(null)

Instance 3:
A
├─(null)
└─B
  ├─(null)
  └─C
    ├─E
    └─D

Instance 4:
A
├─(null)
└─B
  ├─E
  └─C
    ├─(null)
    └─D

Instance 5:
A
├─E
└─B
  ├─(null)
  └─C
    ├─(null)
    └─D

Instance 6:
A
├─(null)
└─B
  ├─(null)
  └─C
    ├─D
    │ ├─(null)
    │ └─E
    └─(null)

Instance 7:
A
├─(null)
└─B
  ├─(null)
  └─C
    ├─D
    │ ├─E
    │ └─(null)
    └─(null)

Instance 8:
A
├─(null)
└─B
  ├─E
  └─C
    ├─D
    └─(null)

Instance 9:
A
├─E
└─B
  ├─(null)
  └─C
    ├─D
    └─(null)

Instance 10:
A
├─(null)
└─B
  ├─D
  │ ├─(null)
  │ └─E
  └─C

Instance 11:
A
├─(null)
└─B
  ├─D
  │ ├─E
  │ └─(null)
  └─C

Instance 12:
A
├─E
└─B
  ├─D
  └─C

Instance 13:
A
├─D
│ ├─(null)
│ └─E
└─B
  ├─(null)
  └─C

Instance 14:
A
├─D
│ ├─E
│ └─(null)
└─B
  ├─(null)
  └─C

Instance 15:
A
├─(null)
└─B
  ├─C
  │ ├─(null)
  │ └─D
  │   ├─(null)
  │   └─E
  └─(null)

Instance 16:
A
├─(null)
└─B
  ├─C
  │ ├─(null)
  │ └─D
  │   ├─E
  │   └─(null)
  └─(null)

Instance 17:
A
├─(null)
└─B
  ├─C
  │ ├─E
  │ └─D
  └─(null)

Instance 18:
A
├─E
└─B
  ├─C
  │ ├─(null)
  │ └─D
  └─(null)

Instance 19:
A
├─(null)
└─B
  ├─C
  │ ├─D
  │ │ ├─(null)
  │ │ └─E
  │ └─(null)
  └─(null)

Instance 20:
A
├─(null)
└─B
  ├─C
  │ ├─D
  │ │ ├─E
  │ │ └─(null)
  │ └─(null)
  └─(null)

Instance 21:
A
├─E
└─B
  ├─C
  │ ├─D
  │ └─(null)
  └─(null)

Instance 22:
A
├─D
│ ├─(null)
│ └─E
└─B
  ├─C
  └─(null)

Instance 23:
A
├─D
│ ├─E
│ └─(null)
└─B
  ├─C
  └─(null)

Instance 24:
A
├─C
│ ├─(null)
│ └─D
│   ├─(null)
│   └─E
└─B

Instance 25:
A
├─C
│ ├─(null)
│ └─D
│   ├─E
│   └─(null)
└─B

Instance 26:
A
├─C
│ ├─E
│ └─D
└─B

Instance 27:
A
├─C
│ ├─D
│ │ ├─(null)
│ │ └─E
│ └─(null)
└─B

Instance 28:
A
├─C
│ ├─D
│ │ ├─E
│ │ └─(null)
│ └─(null)
└─B

Instance 29:
A
├─B
│ ├─(null)
│ └─C
│   ├─(null)
│   └─D
│     ├─(null)
│     └─E
└─(null)

Instance 30:
A
├─B
│ ├─(null)
│ └─C
│   ├─(null)
│   └─D
│     ├─E
│     └─(null)
└─(null)

Instance 31:
A
├─B
│ ├─(null)
│ └─C
│   ├─E
│   └─D
└─(null)

Instance 32:
A
├─B
│ ├─E
│ └─C
│   ├─(null)
│   └─D
└─(null)

Instance 33:
A
├─B
│ ├─(null)
│ └─C
│   ├─D
│   │ ├─(null)
│   │ └─E
│   └─(null)
└─(null)

Instance 34:
A
├─B
│ ├─(null)
│ └─C
│   ├─D
│   │ ├─E
│   │ └─(null)
│   └─(null)
└─(null)

Instance 35:
A
├─B
│ ├─E
│ └─C
│   ├─D
│   └─(null)
└─(null)

Instance 36:
A
├─B
│ ├─D
│ │ ├─(null)
│ │ └─E
│ └─C
└─(null)

Instance 37:
A
├─B
│ ├─D
│ │ ├─E
│ │ └─(null)
│ └─C
└─(null)

Instance 38:
A
├─B
│ ├─C
│ │ ├─(null)
│ │ └─D
│ │   ├─(null)
│ │   └─E
│ └─(null)
└─(null)

Instance 39:
A
├─B
│ ├─C
│ │ ├─(null)
│ │ └─D
│ │   ├─E
│ │   └─(null)
│ └─(null)
└─(null)

Instance 40:
A
├─B
│ ├─C
│ │ ├─E
│ │ └─D
│ └─(null)
└─(null)

Instance 41:
A
├─B
│ ├─C
│ │ ├─D
│ │ │ ├─(null)
│ │ │ └─E
│ │ └─(null)
│ └─(null)
└─(null)

Instance 42:
A
├─B
│ ├─C
│ │ ├─D
│ │ │ ├─E
│ │ │ └─(null)
│ │ └─(null)
│ └─(null)
└─(null)

42 instances found

#13

代码在这里，没怎么整理。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXDEPTH 255 //输入串最大长度

int instance_count = 0; //解的个数

int times_malloc = 0;
int times_free = 0;
int state[MAXDEPTH + 1];

#define MALLOC(sz) (++times_malloc, malloc(sz))
#define FREE(ptr) {++times_free; free((ptr)); (ptr) = NULL;}

#define BLANK " "
#define VERTICAL "│"
#define HORIZON "─"
#define BRANCH "├"
#define BRANCHEND "└"

#define EMPTY_TREE "(null)"

#define BLANK_FLAG 0
#define VERTICAL_FLAG 1
#define HORIZON_FLAG 2
#define BRANCH_FLAG 3
#define BRANCHEND_FLAG 4

#define PRINT(SYMBOL) printf("%s", SYMBOL)

//树节点
typedef struct tagTreeNode
{
	struct tagTreeNode *left;
	struct tagTreeNode *right;
	char c;
} TreeNode;

TreeNode* new_node(char ch);
void printInstance(TreeNode *root);
void printTree(TreeNode *root, int depth, int last);
void FindAndTryInsertItem(TreeNode **pCurrent, int *found, char *input_str, int index, int length, TreeNode **ppRoot);


int main()
{
	char input_str[MAXDEPTH];
	int length, found;
	TreeNode *pRoot = NULL;

	scanf("%s", input_str);
    length = strlen(input_str) - 1;
	if (length != 0)      //树非空 
	{
		found = 0;
		pRoot = new_node(input_str[0]);
		FindAndTryInsertItem(&pRoot, &found, input_str, 1, length, &pRoot);
		FREE(pRoot);
	} 
	else 
		instance_count = 1; //empty tree

	printf("%d instances found\n", instance_count);
	printf("malloc times = %d, free times = %d\n", times_malloc, times_free);

	return 0;
}

//新开节点
TreeNode* new_node(char ch)
{
	TreeNode *pNewNode = (TreeNode*)MALLOC(sizeof(TreeNode));
	pNewNode->left = NULL;
	pNewNode->right = NULL;
	pNewNode->c = ch;
	return pNewNode;
}

//InsertItem
void FindAndTryInsertItem(TreeNode **pCurrent, int *found, char *input_str, int index, int length, TreeNode **ppRoot)
{
	if (index == length) 
	{
		printInstance(*ppRoot);
		return;
	}

	if (*pCurrent == NULL)
	{
		if (*found)
		{
			int fnd = 0;
			*pCurrent = new_node(input_str[index]);
			FindAndTryInsertItem(ppRoot, &fnd, input_str, index + 1, length, ppRoot);
			FREE(*pCurrent);
			*pCurrent = NULL;
		}
		return;
	}

	if ((*pCurrent)->c == input_str[index - 1]) *found = 1;

	FindAndTryInsertItem(&((*pCurrent)->left), found, input_str, index, length, ppRoot);
	FindAndTryInsertItem(&((*pCurrent)->right), found, input_str, index, length, ppRoot);
}

// 打印实例
void printInstance(TreeNode *root)
{
	++instance_count;
	printf("Instance %d:\n", instance_count);
	printTree(root, 0, 0);
	printf("\n");
}

//打印一棵二叉树到屏幕
void printTree(TreeNode *root, int depth, int last)
{
	int i, tmp;
	int newlast;

	for (i = 0; i < depth; ++i)
	{
	   switch (state[i])
	   {
			case BLANK_FLAG: PRINT(BLANK); break;
			case VERTICAL_FLAG: PRINT(VERTICAL); break;
			case BRANCH_FLAG: PRINT(BRANCH); break;
			case BRANCHEND_FLAG: PRINT(BRANCHEND); break;
			case HORIZON_FLAG: PRINT(HORIZON); break;
			default: printf("error at line %d\n", __LINE__);
	   }
	   if (i < depth - 1)
		   PRINT(BLANK);
       else PRINT(HORIZON);
	}

	char *info = EMPTY_TREE;

	if (root == NULL)
	{
		printf("%s\n", info);
		return;
	}

	printf("%c\n", root->c);

	if (depth > 0 && last) state[depth - 1] = BLANK_FLAG;
	if (root->left == NULL && root->right == NULL) return; //没有子节点

	newlast = 0;
	for (i = 0; i < 2; ++i)
	{
	   if (i == 1)
	   {
			newlast = 1;
			state[depth] = BRANCHEND_FLAG;
	   } 
	   else 
		   state[depth] = BRANCH_FLAG;

	   if (depth > 0)
	   {
			tmp = state[depth - 1];
			if (state[depth - 1] != BLANK_FLAG && state[depth - 1] != VERTICAL_FLAG)
				state[depth - 1] = VERTICAL_FLAG;
	   }

	   if (i == 0)
			printTree(root->right, depth + 1, newlast);
	   else
			printTree(root->left, depth + 1, newlast);

	   if (depth > 0) 
			state[depth - 1] = tmp;
	}
}

#14

……我还想讨论下

#15

恩~~不好意思啊~~已经把帖子结了,要不再开一个?

#16

哦那不用了。
弄清楚了，f(n) = C(2n,n)/n+1,即有n个节点的二叉树的个数.

#17

让我想起了经典的汉诺塔，学习了，谢谢Paradin了。

#18

这个我标记一下，找时间看看

#19

学习了~

#20

学习了下

#21

• C语言实现一个二叉树