BiTree

二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作左子树和右子树。二叉树常被用于实现二叉查找树。

二叉树的每个节点至多只有2棵子树（不存在度大于2的节点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^i-1结点；深度为k的二叉树至多有2^k - 1个结点；对任何一棵二叉树T，如果其终端结点数为n0,度为2的节点数为n2，则n0 = n2 + 1.

一棵深度为k，且有2^k- 1个结点称之为满二叉树；深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中序号为1至n的结点对应时，称之为完全二叉树。

与树不同，树的结点个数至少为1，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2.树的节点无左右之分，而二叉树的结点有左右之分。

一棵深度为k，且有2^k - 1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。

而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干结点，则此二叉树称为完全二叉树。

二叉树的基本操作

递归算法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #define MAXSIZE 55
 8 using namespace std;
 9 
10 struct BiTree
11 {
12     char data;
13     BiTree *left, *right;
14 };
15 
16 BiTree *Create()
17 {
18     char ch;
19     scanf("%c", &ch);
20     getchar();
21     if (ch == '#')
22     {
23         return NULL;
24     }
25     else
26     {
27         BiTree *btree = (BiTree *)malloc(sizeof(BiTree));
28         if (NULL == btree)
29         {
30             return NULL;
31         }
32         btree->data = ch;
33         btree->left = Create();
34         btree->right = Create();
35         return btree;
36     }
37 }
38 
39 void Preorder(BiTree *bt)
40 {
41     if (NULL != bt)
42     {
43         printf ("%c ", bt->data);
44         Preorder(bt->left);
45         Preorder(bt->right);
46     }
47 }
48 
49 void Inorder(BiTree *bt)
50 {
51     if (NULL != bt)
52     {
53         Inorder(bt->left);
54         printf ("%c ", bt->data);
55         Inorder(bt->right);
56     }
57 }
58 
59 void Postorder(BiTree *bt)
60 {
61     if (NULL != bt)
62     {
63         Postorder(bt->left);
64         Postorder(bt->right);
65         printf ("%c ", bt->data);
66     }
67 }
68 
69 int Height(BiTree *bt)
70 {
71     int depth1, depth2;
72     if (NULL == bt)
73     {
74         return 0;
75     }
76     else
77     {
78         depth1 = Height(bt->left);
79         depth2 = Height(bt->right);
80         if (depth1 > depth2)
81         {
82             return (depth1 + 1);
83         }
84         else
85         {
86             return (depth2 + 1);
87         }
88     }
89 }
90 
91 int main()
92 {
93 
94 }

View Code