《数据结构与算法》——二叉树

luciferzf

1.视频一共介绍了三种储存方式，父母，孩子，以及父母和孩子。利用父母储存法，在每一个节点都保存了父母的地址，所以根据儿子节点我们可以快速地找到它的父母；同理，孩子储存法和父母孩子储存法则能快速地找到该节点的孩子，或者孩子和父母。
2.满二叉树：节点个数n和深度k满足n=2^k-1,即除了叶子其他节点都有两个子节点。
  完全二叉树：根据层编号后，编号与满二叉树一致。
——>满二叉树是一种特殊的完全二叉树
——>完全二叉树的度为0的节点个数n0，度为2的节点个数n2,满足n0=n2+1。
3.完全二叉树根据层编号后，满足
——>[i/2]是i父母节点，若i*2>n，则该节点没有左节点；若i*2+1>n，则该节点没有子节点
4.二叉树的遍历
1）前序遍历:若二叉树为空，则返回；否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树
2）后序遍历：从左到右先子叶后节点的方式遍历访问左右子树，最后访问根节点。
3）中序遍历：从根节点开始，先中序遍历左子树，然后访问根节点，最后再中序遍历右子树。
4）层序遍历：从根节点开始，从上往下，从左往右逐层遍历

5.二叉树的建立和遍历
1）建立:定义一个有着两个指针的结构体，利用递归的方法，将数据不断地从上到下，从左到右地储存在二叉树中完成建立
2）遍历：根据根节点，我们可以利用四种遍历方式，用递归的方式实现遍历

1. #include<cstdlib>
   
2. #include<cstdio>
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. class bitree
   
7. {
   
8. public:
   
9.         char data;
   
10.         bitree *l, *r;
    
11. };
    
12. 
    
13. void Create(bitree *&p)
    
14. {
    
15.         char c;
    
16.         scanf_s("%c", &c);
    
17.         if (' ' == c)
    
18.         {
    
19.                 p = NULL;
    
20.                 return;
    
21.         }
    
22.         else
    
23.         {
    
24.                 p = new bitree;
    
25.                 p->data = c;
    
26.                 Create(p->r);
    
27.                 Create(p->l);
    
28.         }
    
29. }
    
30. 
    
31. void TreeTravel(bitree *p,int level)
    
32. {
    
33.         if (p != NULL)
    
34.         {
    
35.                 printf("%c is in the level %d\n", p->data, level);
    
36.                 TreeTravel(p->l, level + 1);
    
37.                 TreeTravel(p->r, level + 1);
    
38.         }
    
39.        
    
40. }
    
41. 
    
42. int main()
    
43. {
    
44.         bitree *root=NULL;
    
45.         Create(root);
    
46.         TreeTravel(root, 1);
    
47. 
    
48.         system("PAUSE");
    
49. }

复制代码