数据结构：二叉树相关代码

1.Create a tree using recursion(递归) Using the function "createtree" to create a tree. The function need three parameters. The basic logic is using recursion method. You need to create a struction to regular the tree node. 1.1 treenode struction - the basic construction is showed below: typedef struct TreeNode { char data_capacity; struct TreeNode* left-child-pointer; struct TreeNode* right-child-pointer; }TreeNode; //the two pointers is used to regulate the address of the child node. You can use it as the node of the list. //the "char data_capacity" is used to preserve the data in every node. After you create the struction, you need to save the data into the tree nodes. There, you ususally need to deliver into a container to deliver the data you need to save. (In order to distinguish the datas which need to be save and the capacities which are used to save the data, we define the name: data_capacity and data_tosave). Usually, the data_tosave is an array or a string. So, you need using a pointer called "index" to point to the data which needs to be save -> data_tosave[index] and then index++. And then you use recursion to create the tree. 2.Clued-binary tree(线索化二叉树) Before you create this binary tree, you should know basic knowledge of this new construction. The traverse of the binary tree usually has three methods including preOrder(前序遍历), inOrder(中序遍历) and postOrder(后续遍历). The first step is to choose the ways of traversing and arrange all the nodes in the order they are visited. As for one node in the linear list, the front node is the front_node(前驱) and the behind-node is "behind-node"(后继). For example, we have read one binary tree and the order is "ABDCE". It has the construction of "B-D-C". The next step is to create the clue-binary tree. In order to ensure where the pointer point to, we should improve the struction. -the improved construction is showed below: typedef struct TreeNode { char data_capacity; struct TreeNode* left-child-pointer; struct TreeNode* right-child-pointer; int ltag; int rtag; }TreeNode; There, we add two signs to record if the node which is pointed by the previous node is emppty or not. If is, the valur is "1". We use the previous clue-binary tree as the example(用前序线索化二叉树作为例子). Firstly, we should judge if the "node->lchlid" or the "node->rchild" has value. If it is, then the left-pointer points to it. If not, then the left-pointer points to the front-node and the right-pointer points to the behind-node. (也就是说，将所有的节点按对应的遍历顺序写成一列，然后看二叉树的图形中对应的节点中的左孩子区域和右孩子区域所指向的地方是否为空。若是， 则左孩子区域中的 指针指向前驱，ltag赋值为1，用于说明这个指针指向前驱，而右区域若也指向空，则同理，右指针指向后继，rtag=1。若不是，则就指向对应的子孩子。)