二叉树的基本操作的思想、算法（链式存储结构）_简述以下关于二叉树某操作的算法的功能和主要思想。 typedef struct bitnode {4

学完二叉树的定义、类型、性质、存储结构后，继续学习二叉树的基本操作：创建二叉树、找指定结点、找孩子结点、求二叉树的高度、输出二叉树。
下面的算法基于这个二叉树的链式存储结构。

//二叉树的二叉链存储表示可描述为：
typedef struct node{
    
ElemType data;     /* 存放结点的值，ElemType是元素的基本类型 */
struct node *lchild;  /* 指向左孩子结点指针*/
struct node *rchild;  /* 指向右孩子结点指针 */
} BTNode;
1
2
3
4
5
6

创建二叉树CreateBTNode
根据括号表示法的字符串构造二叉树，举个栗子：

用ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况：
① 若ch=’(’：则将前面刚创建的节点作为双亲结点进栈，并置tag=1，表示其后创建的结点将作为这个结点的左孩子结点；
② 若ch=’)’：表示栈中结点的左右孩子结点处理完毕，退栈；
③ 若ch=‘,’：表示其后创建的结点为右孩子结点，置tag=2；
④ 其他情况：当tag=1时，表示这个结点作为栈中结点的左孩子结点；当tag=2时，表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。

void CreateBTNode(BTNode * &T,char *str)
{
    
BTNode *St[MaxSize],*p=NULL;
int top=-1,tag,j=0;  
char ch;
T=NULL;          /*建立的二叉树初始时为空*/
ch=str[j];
while (ch!='\0')            /*str未扫描完时循环*/
{
     switch(ch) 
  {
   
        case '(':top++;St[top]=p;tag=1; break;
        case ')'
1
2
3
4
5
6
7
8
9
10
11
12
13
14