树（树，二叉树，二叉查找树）

时间：2022-11-17 17:30:50

1.定义： n（n≥0）个结点构成的有限集合。当n=0时，称为空树

2.对于任一棵非空树（n> 0），它具备以下性质：
（1）、树中有一个称为“根（Root）”的特殊结点，用 r 表示；
（2）、其余结点可分为m(m>0)个互不相交的有限集T1，T2，… ， 其中每个集合本身又是一棵树，称为原来树的子树。

3.树的一些性质:
（1）、子树是不相交的；
（2）、除了根结点外，每个结点有且仅有一个父结点；
（3）、 一棵N个结点的树有N-1条边。

4、树的一些基本术语
（1）. 结点的度（Degree）：结点的子树个数
（2）.树的度：树的所有结点中最大的度数
（3）. 叶结点（Leaf）：度为0的结点
（4）. 父结点（Parent）：有子树的结点是其子树
的根结点的父结点
（5）. 子结点（Child）：若A结点是B结点的父结
点，则称B结点是A结点的子结点；子结点也
称孩子结点。
（6）. 兄弟结点（Sibling）：具有同一父结点的各
结点彼此是兄弟结点
（7）. 路径和路径长度：从结点n1到nk的路径为一个结点序列
n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
（8）. 祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
（9）. 子孙结点(Descendant)：某一结点的子树
中的所有结点是这个结点的子孙。
（10）. 结点的层次（Level）：规定根结点在1层，
其它任一结点的层数是其父结点的层数加1。
（11）. 树的深度（Depth）：树中所有结点中的最
大层次是这棵树的深度。

5.二叉树：一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成。

（1）、斜二叉树：只有左儿子或者只有右儿子

（2）、完美二叉树（满二叉树）：每个结点都有两个儿子，除了最下面 一层的叶。

（3）、完全二叉树：有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同。

（4）、二叉树几个重要性质：
(1. 一个二叉树第 i 层的最大结点数为：2^(i-1) (i >= 1)。
(2.深度为k的二叉树有最大结点总数为： 2k-1，k>=1。
(3. 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0= n2+1。

（5）、二叉树的存储：数组或者链表
(1.数组存储：对于完全二叉树，数组存储可以保证连续，并且能够找到父子关系，但是对于一般的二叉树，数组实现虽然也能够找到对应的父子关系，但是浪费空间很大。
(2.链表存储：
链表存储的结构体构造（ElementType为数据类型）：

struct TreeNode{
    ElementType Data;
struct TreeNode* Left;
struct TreeNode* Right;
};
typedef struct TreeNode Node;

（6）、二叉树的遍历：
(1.先序遍历：根结点，左子树，右子树。
核心代码：

void preorder_tree(Node* tree)
{
if(tree != NULL)
    {
        printf("%d ", tree->Data);
        preorder_tree(tree->Left);
        preorder_tree(tree->Right);
    }
}

(2.中序遍历:左子树、根、右子树
核心代码：

void midorder_tree(Node* tree)
{
if(tree != NULL)
    {
        midorder_tree(tree->Left);
        printf("%d ", tree->Data);
        midorder_tree(tree->Right);
    }
}

(3.后序遍历：左子树、右子树、根。
核心代码：

void postorder_tree(Node* tree)
{
if(tree != NULL)
    {
        postorder_tree(tree->Left);
        postorder_tree(tree->Right);
        printf("%d ", tree->Data);
    }
}

6、二叉查找树：它的左子树中所有关键字的值小于树中的每个节点，而它的右子树的所有关键字的值大于树中的每个节点。

1-1.查找操作的核心代码：
Node * find(int x,Node* tree)
{
if(tree == NULL)
return NULL;
else if(x < tree->Data)
return find(x,tree->Left);
//如果查找的值比当前节点小，就返回查找的值和左子树 
else if(x > tree->Data)
return find(x,tree->Right);
//如果查找的值比当前节点大，就返回查找的值和右子树 
else
return tree;//找到了，就返回当前节点 
}
1-2.查找最大值操作的核心代码：
Node* findmax(Node* tree)//递归实现 
{
if(tree == NULL)
return NULL;
else if(tree->Right == NULL)
return tree;
else
return findmax(tree->Right);
} 
 1-3.查找最小值操作的核心代码：
Node * findmin(Node *tree)//非递归实现 
{
if(tree == NULL)
return NULL;
else
    {
while(tree->Left != NULL)
        tree = tree->Left;
    }
return tree;
 } 
2、插入操作：插入操作的关键是找到插入的位置，寻找位置的过程可以根据Find函数类推。
核心代码：
Node* insert(int x,Node* tree)
{
if(tree == NULL)//若原树为空，生成并返回一个二叉树 
    {
        tree = (Node*)malloc(sizeof(Node));
if(tree == NULL)//判断是否申请成功 
        {
            printf("no pace!\n");
            exit(0);
        }
        tree->Data = x;
        tree->Left = tree->Right = NULL; 
    }
//开始找插入的位置 
else if(tree->Data > x)//递归插入左子树 
    tree->Left = insert(x,tree->Left);
else if(tree->Data < x)//递归插入右子树 
    tree->Right = insert(x,tree->Right);
/*else x存在，不做任何操作，返回原树*/ 
return tree; 
}

注意：递归应保留前一个结点的值，这样才能是插入连接起来，如果把代码“tree->Left = insert(x,tree->Left);”中的左边改为return，就跟查找很像了，就不能实现插入的操作。最后不要忘记返回tree！

3.删除操作：

！！！
有三种情况：（1）、要删除的结点没有子树，这种情况直接将其删除再将父结点置为NULL
（2）、要删除的结点有一个孩子，将要删除的结点的父结点指向删除结点的孩子节点。
（3）、最复杂的一种情况，删除的结点有左儿子和右儿子。用另一个结点代替要删除的结点：左子树的最大值，右子树的最小值

！！！
核心代码： 

Node* Delet(int x,Node* tree)
{
if(tree == NULL)
    {
        printf("未找到删除的结点！\n");
    }
else if(x > tree->Data)
    tree->Right = Delet(x,tree->Right);//右子树递归删除
else if(x < tree->Data)
    tree->Left = Delet(x,tree->Left);//左子树递归删除
else//找到x结点
    {
        Node* temp; 
if(tree->Left &&tree->Right)//有左子树和右子树的情况
        {
            temp = findmin(tree->Right)
//在右子树中找最小的元素，然后代替删除的结点
            tree->Data = temp->Data;
            tree->Right = Delet(tree->Data,tree->Right);
//在右子树中删除最小元，
//因为最小元一定是右子树中最左边的，只有一个孩子或者没有孩子,
//简化了删除操作 
        }
else//被删除的有一个子结点或没有子结点的 
        {
            temp = tree;
if(tree->Left == NULL)//有右儿子或者无儿子
            tree = tree->Right;
else if(tree->Right == NULL)//有左儿子或者无儿子
            tree = tree->Left; 
            free(temp); 
        }

    }
return tree;
}

以上是关于树的基本概念；二叉树的一些概念、二叉树的实现以及二叉树的遍历；二叉查找树的一些基本操作（包括查找元素，查找最值，插入结点，删除结点）。
关于树的完整代码将在后面补充。
标签：

相关文章