初学树Ⅰ

二叉树的一些性质

  1. 在二叉树的第i层上至多有\(2^{i-1}\)个节点(i≥1)

  2. 深度为k的二叉树至多有\(2^{k-1}\)个节点(k≥1)

  3. 对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1

  4. 具有n个节点的完全二叉树的深度为[log2n]+1

  5. 如果一棵有n个节点的完全二叉树,对任意一个节点i有:

    1. 如果i>1,双亲是[i/2]

    2. 如果2*i>n,无左孩子

      否则左孩子是节点2*i

    3. 如果2*i+1>n,无右孩子

      否则右孩子是节点[2*i+1]

二叉树的建立和一些操作

二叉树的二叉链表的节点结构定义

1
2
3
4
5
typedef struct BiTnode
{
char data;
struct BiTnode *lchild, *rchild;
}node;

###建立:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node* CreateBiTree()
{
char ch;
node *T;
scanf("%c",&ch);
if(ch=='#')
T = NULL;
else
{
T = (node *)malloc(sizeof(node));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;
}

###前序遍历(递归实现)

1
2
3
4
5
6
7
8
9
10
void InOrderTraverse(node *T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
return;
}

###中序遍历(递归实现)

1
2
3
4
5
6
7
8
9
10
void InOrderTraverse(node *T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
return;
}

后序遍历(递归实现)

1
2
3
4
5
6
7
8
9
10
void PostOrderTraverse(node *T)
{
if(T)
{
PostOrderTraverse(T->lchild);
printf("%c",T->data);
PostOrderTraverse(T->rchild);
}
return;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
int main(void)
{
node *Tree;
Tree = CreateBiTree();
PreOrderTraverse(Tree);
printf("\n");
InOrderTraverse(Tree);
printf("\n");
PostOrderTraverse(Tree);
printf("\n");
return 0;
}