【算法笔记】树和二叉树相关基础

1、树的基本概念和三种排序

1.树的常用概念
根节点(Root)、叶子节点(Leaf)、父节点(Parent)、子节点(Child)、兄弟节点(Siblings)，还有节点的高度、深度以及层数，树的高度。

Root: Top node in a tree
Child: Nodes that are next to each other and connected downwards
Parent: Converse notion of child
Siblings: Nodes with the same parent
Descendant: Node reachable by repeated proceeding from parent to child
Ancestor: Node reachable by repeated proceeding from child to parent.
Leaf: Node with no children
Internal node: Node with at least one child
External node: Node with no children

2.概念解释
节点：树中的每个元素称为节点
父子关系：相邻两节点的连线，称为父子关系
根节点：没有父节点的节点
叶子节点：没有子节点的节点
父节点：指向子节点的节点
子节点：被父节点指向的节点
兄弟节点：具有相同父节点的多个节点称为兄弟节点关系
节点的高度：节点到叶子节点的最长路径所包含的边数
节点的深度：根节点到节点的路径所包含的边数
节点的层数：节点的深度+1（根节点的层数是1）
树的高度：等于根节点的高度

二叉树

1.概念
①什么是二叉树？
每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。如下图123
可以看出一些二叉树的性质，如：

②什么是满二叉树？
有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。如下图2
③什么是完全二叉树？
有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。如下图3

完全二叉树的存储 非完全二叉树的存储，浪费内存

什么是平衡二叉树？
树上任意节点的左子树和右子树的深度之差不超过1

2.完全二叉树的存储
①链式存储
每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。

C语言实现二叉树的创建

/* Includes structure for a node and a newNode() function which
   can be used to create a new node in the tree. 
   It is assumed that the data in nodes will be an integer, though
   function can be modified according to the data type, easily.
 */

#include <stdio.h>
#include <stdlib.h>

struct node
{
    struct node *leftNode;
    int data;
    struct node *rightNode;
};

struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));

    node->leftNode = NULL;
    node->data = data;
    node->rightNode = NULL;

    return node;
}

int main(void)
{
    /* new node can be created here as :-

       struct node *nameOfNode = newNode(data);

       and tree can be formed by creating further nodes at
       nameOfNode->leftNode and so on.
    */

    return 0;
}

②顺序存储
用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，反过来，下标i/2位置存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。
3.二叉树的遍历
①前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
②中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。
③后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
时间复杂度：3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)。

C语言二叉树三种遍历的实现

/* Includes the functions for Recursive Traversals
   of a Binary Tree. It is assumed that nodes and
   tree have been created as per create_node.c
 */

#include <stdio.h>

void inOrderTraversal(struct node *node)
{
    if(node == NULL) //if tree is empty
        return;

    inOrderTraversal(node->leftNode);
    printf("\t%d\t", node->data);
    inOrderTraversal(node->rightNode);
}

void preOrderTraversal(struct node *node)
{
    if(node == NULL) //if tree is empty
        return;

    printf("\t%d\t", node->data);
    preOrderTraversal(node->leftNode);
    preOrderTraversal(node->rightNode);
}

void postOrderTraversal(struct node *node)
{
    if(node == NULL) //if tree is empty
        return;

    postOrderTraversal(node->leftNode);
    postOrderTraversal(node->rightNode);
    printf("\t%d\t",node->data);
}

int main(void)
{
    /* traversals can be done by simply invoking the
       function with a pointer to the root node.
    */

    return 0;
}

三种遍历的示范：

值得注意的是，当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。

另外，后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易。 这里是一个例子：

您可以使用中序遍历轻松找出原始表达式。 但是程序处理这个表达式时并不容易，因为你必须检查操作的优先级。

如果你想对这棵树进行后序遍历，使用栈来处理表达式会变得更加容易。 每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中。

下面继续讲解，三种遍历的非递归实现：
来自：二叉树的非递归前序、中序、后序遍历算法详解及代码实现（C语言） 这篇文章

从当前节点开始遍历：（当入栈时访问节点内容，则为前序遍历；出栈时访问，则为中序遍历）

1. 若当前节点存在，就存入栈中，并访问左子树；

2. 直到当前节点不存在，就出栈，并通过栈顶节点访问右子树；

3. 不断重复12，直到当前节点不存在且栈空。

typedef struct TreeNode{
    int data;
    struct TreeNode *lChild;
    struct TreeNode *rChild;
}TreeNode;


//先序遍历的非递归实现

void preOrder(TreeNode *T){
    TreeNode *stack[15];
    int top = -1;
    TreeNode *p = T;
    while(p!=NULL||top!=-1){
        if(p!=NULL){
            stack[++ top] = p;
            printf("%d\t",p->data); //入栈时，访问输出
            p = p->lChild;
        }else{
            p = stack[top --];
            p = p->rChild;
        }
    }
}

//中序遍历的非递归实现

void inOrder(TreeNode *T){
    TreeNode *stack[15];
    int top = -1;
    TreeNode *p = T;
    while(p!=NULL||top!=-1){
        if(p!=NULL){
            stack[++ top] = p;
            p = p->lChild;
        }else{
            p = stack[top --];
            printf("%d\t",p->data);  //出栈时，访问输出
            p = p->rChild;
        }
    }
}

后序遍历整体与前中序遍历过程相似。但要注意，这时对于父节点的访问输出，需要在其右子树遍历完成的前提下进行。所以不能像前中序遍历一样，在遍历完左子树后，就直接出栈。我们需要利用这个未出栈的栈顶元素去获取右子树，在遍历完右子树后，就可以出栈，并对此节点进行访问输出。

这里我们需要使用一个标记，以区分是从左子树取栈还是从右子树出栈：（如图所示）

从当前节点开始遍历：

1. 若当前节点存在，就存入栈中，并且置节点flag为1（第一次访问），然后访问其左子树；

2. 直到当前节点不存在，需要回退，这里有两种情况：

   1）当栈顶节点flag为1时，则表明是从左子树回退，这时需置栈顶节点flag为2（第二次访问），然后通过栈顶节点访问其右子树（取栈顶节点用，但不出栈）
   
   2）当栈顶节点flag为2时，则表明是从右子树回退，这时需出栈，并取出栈节点做访问输出。（需要注意的是，输出完毕需要置当前节点为空，以便继续回退。具体可参考代码中的p = NULL）
   

3. 不断重复12，直到当前节点不存在且栈空。
   相关代码：

void postOrder(TreeNode *T){
    TreeNode *stack[15];
    int top = -1;
    int flagStack[15];   //记录每个节点访问次数栈
    TreeNode *p = T;
    while(p!=NULL||top!=-1){
        if(p!=NULL){     //第一次访问，flag置1，入栈
            stack[++ top] = p;
            flagStack[top] = 1;   
            p = p->lChild;
        }else{//（p == NULL）
            if(flagStack[top] == 1){  //第二次访问，flag置2，取栈顶元素但不出栈
                p = stack[top];
                flagStack[top] = 2;
                p = p->rChild;
            }else{         //第三次访问，出栈
                p = stack[top --];
                printf("%d\t",p->data);    //出栈时，访问输出
                p = NULL;      //p置空，以便继续退栈
            }
        }
    }
}

二叉树的层次遍历：
实现思路：
一个二叉树，层次遍历就是每一行每一行的取出数据。
这个图的结果就是 ABCDEFGH

就是先父节点进入队列，然后循环，出队时带入下一组子节点进队，没有就没有进入队列的，当队列为空时结束循环。

伪代码如下：

完整代码参考文章最后。

2、 二叉查找树（binary search tree） BST tree

1，二叉查找树最大的特点是：支持动态数据集合的快速插入，删除，查找操作
2，二叉查找树的要求：在树中的任意一个节点，其中左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

3，二叉查找树的查找操作
先取根节点，如果他等于要查找的数据，就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找

Java语言实现，查找操作,这里我添加递归和非递归两种方式

public class BinarySearchTree {

/**
*二叉查找树-查找-非递归实现
*/
  public Node find(Node tree, int data) {
    while (tree != null) {
      if (data < tree.data) tree = tree.left;
      else if (data > p.data) tree = tree.right;
      else return tree;
    }
    return null;
  }


/**
*二叉查找树-查找-递归实现
*/
  public Node findInRecursion(Node tree, int data){
    if(tree ==null) return null;
    if(tree.data<data) 
      tree=findInRecursion(tree.right,data);
    if(tree.data>data)
      tree=findInRecursion(tree.left,data);
  }


  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

4，二叉查找树的插入操作
二叉查找树的插入过程有些类似查找操作。新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系。
如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插入右子节点的位置；如果不为空，就在递归遍历右子树，查找插入位置。

java语言实现二叉查找树的插入操作，,这里我添加递归和非递归两种方式

/**
*二叉查找树-插入-非递归实现
*/
public Node insert(Node tree, int data) {
  if (tree == null) {
    tree = new Node(data);
    return tree;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return p.right;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return p.left;
      }
      p = p.left;
    }
  }
}


/**
*二叉查找树-插入-递归实现
*/
public void insertInRecursion(Node tree, int data){
   if(tree ==null) return new Node(val);
    if(tree.data<data) 
      insertInRecursion(tree.right,data);
    if(tree.data>data)
      insertInRecursion(tree.left,data);
}

5，二叉查找树的删除操作
二叉查找树的删除要分三种情况：
①：如果要删除的节点没有子节点，只需要直接将父节点中指向要删除节点的指针置为为null。
②：如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
③：如果要删除的节点有两个子节点，我们需要找到这个节点的右子节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以就可以应用上面两条规则来删除这个最小节点。

java语言实现，二叉树的删除操作

/**
*二叉查找树-删除-递归实现
*/
public void delete(Node tree, int data) {
  // Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

/**
*二叉查找树-删除-递归实现
*/
public Node deleteInRecursion(Node node, int data){
   if(tree ==null) return null;
   if(tree.data == data){
    //处理删除根结点且根无左右子树，删除根结点且根无左子树，删除根结点且根无右子树三种情况
      if(root.left == null) return node.right;
      if(root.right == null) return node.left;
      //处理删除跟结点，且其有左右子树的情况，这里用右子树的最小结点取代当前根结点
      Node minNode= getMin(node.right);
      node.data= minNode.data;
      root.right=deleteInRecursion(root.right,minNode.data)
   }
    else if(tree.data<data) 
      insertInRecursion(tree.right,data);
    else if(tree.data>data)
      insertInRecursion(tree.left,data);
}

public Node getMin(Node node){
  //BST中最左边的就是最小的
  while(tree.left!=null) node =node.left;
  return node;

}

6，二叉查找树的其他操作
除了插入，删除，查找操作之外，二叉查找树中还可以可以支持快速地查找最大节点和最小节点，前驱节点和后继节点。
二叉查找树还有一个重要的特性：中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。因此，二叉查找树也叫二叉排序树。

7，二叉查找树支持重复数据
在实际开发中，是在二叉查找树中存储的对象，我们利用对象的某个字段作为键值（key）来构建二叉查找树，并把对象中的其他字段叫作卫星数据。

针对：如果存储两个对象键值相同的处理方式：
第一种方式：二叉查找树中每个节点不仅会存储一个数据，因此可通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
第二种方式：每个节点仍然只存储一个数据，在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，即把这个新插入的数据当做大于这个节点的值来处理。

这样当要查找数据时，遇到值相同的节点，不通知查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。
删除操作，也需要先查找到每个要删除的节点，然后在按前面讲的删除操作的方法，依次删除。

8，二叉查找树的时间复杂度分析
二叉查找树的形态多种多样，每种的查找，插入，删除操作的执行效率都不一样。
但，不管操作是插入，删除还是查找，时间复杂度其实都根树的高度正比，即O(height)。
树的高度等于最大层数减一，每层包含的节点个数是2^{(k-1)。但对于完全二叉树，最后一层节点个数不遵守这个规律。它包含的节点个数在1个到2}(L-1)个之间（假设最大层数是L）。
如果将每一层的节点数加起来就是总的节点个数n。则n满足以下关系：
n>=1+2+4+8+……+2^(L-2)+1
n<=1+2+4+8+……+2^(L-2)+2(L-1)
得到L的范围是[log2^(n+1)，log2n +1]。
完全二叉树的层数小于等于log2^n + 1，即完全二叉树的高度小于等于log2^n
所以，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除，插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树—平衡二叉查找树。

散列表无法替代二分查找树的原因：
1，散列表中的数据是无序存储的，若要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
2，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，在工程中常用的二叉查找树的性能非常稳定，时间复杂度稳定在O(logn。
3，笼统地讲，虽然散列表的查找操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个个常量不一定比logn小，所以实际查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定比平衡二叉查找树的效率高。
4，散列表的构造比二叉查找树要复杂，需要考虑的东西很多，如散列函数的设计，冲突解决办法，扩容，缩容等。而平衡二叉树只需要考虑平衡性这个一个问题，且这个问题的解决方案比较成熟，固定。
同时，为了避免过多的散列冲突，散列表的装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

3、 一些代码搜集+整理

完整的二叉查找树（C语言），代码来自网络

#include <stdio.h>
#include <stdlib.h>

/* A basic unbalanced binary search tree implementation in C, with the following functionalities implemented:
 - Insertion
 - Deletion
 - Search by key value
 - Listing of node keys in order of value (from left to right)
*/

// Node, the basic data structure in the tree
typedef struct node{

    // left child
    struct node* left;

    // right child
    struct node* right;

    // data of the node
    int data;
} node;

// The node constructor, which receives the key value input and returns a node pointer
node* newNode(int data){

    // creates a slug
    node* tmp = (node*)malloc(sizeof(node));

    // initializes the slug
    tmp->data = data;
    tmp->left = NULL;
    tmp->right = NULL;

    return tmp;
}

// Insertion procedure, which inserts the input key in a new node in the tree
node* insert(node* root, int data){
    // If the root of the subtree is null, insert key here
    if (root == NULL)
        root = newNode(data);
    // If it isn't null and the input key is greater than the root key, insert in the right leaf
    else if (data > root->data)
        root->right = insert(root->right, data);
    // If it isn't null and the input key is lower than the root key, insert in the left leaf
    else if (data < root->data)
        root->left = insert(root->left, data);
    // Returns the modified tree
    return root;
}

// Utilitary procedure to find the greatest key in the left subtree
node* getMax(node* root){
    // If there's no leaf to the right, then this is the maximum key value
    if (root->right == NULL)
        return root;
    else
        root->right = getMax(root->right);
}

// Deletion procedure, which searches for the input key in the tree and removes it if present
node* delete(node* root, int data){
    // If the root is null, nothing to be done
    if (root == NULL)
        return root;
    // If the input key is greater than the root's, search in the right subtree
    else if (data > root->data)
        root->right = delete(root->right, data);
    // If the input key is lower than the root's, search in the left subtree
    else if (data < root->data)
        root->left = delete(root->left, data);
    // If the input key matches the root's, check the following cases
    // termination condition
    else if (data == root->data){
        // Case 1: the root has no leaves, remove the node
        if ((root->left == NULL) && (root->right == NULL)){
            free(root);
            return NULL;
        }
        // Case 2: the root has one leaf, make the leaf the new root and remove the old root
        else if (root->left == NULL){
            node* tmp = root;
            root = root->right;
            free(tmp);
            return root;
        }
        else if (root->right == NULL){
            node* tmp = root;
            root = root->left;
            free(tmp);
            return root;
        }
        // Case 3: the root has 2 leaves, find the greatest key in the left subtree and switch with the root's
        else {

            // finds the biggest node in the left branch.
            node* tmp = getMax(root->left);

            // sets the data of this node equal to the data of the biggest node (lefts)
            root->data = tmp->data;
            root->left = delete(root->left, tmp->data);
        }
    }
    return root;
}

// Search procedure, which looks for the input key in the tree and returns 1 if it's present or 0 if it's not in the tree
int find(node* root, int data){
    // If the root is null, the key's not present
    if (root == NULL)
        return 0;
    // If the input key is greater than the root's, search in the right subtree
    else if (data > root->data)
        return find(root->right, data);
    // If the input key is lower than the root's, search in the left subtree
    else if (data < root->data)
        return find(root->left, data);
    // If the input and the root key match, return 1
    else if (data == root->data)
        return 1;
}

// Utilitary procedure to measure the height of the binary tree
int height(node* root){
    // If the root is null, this is the bottom of the tree (height 0)
    if (root == NULL)
        return 0;
    else{
        // Get the height from both left and right subtrees to check which is the greatest
        int right_h = height(root->right);
        int left_h = height(root->left);

        // The final height is the height of the greatest subtree(left or right) plus 1(which is the root's level)
        if (right_h > left_h)
            return (right_h + 1);
        else
            return (left_h + 1);
    }
}

// Utilitary procedure to free all nodes in a tree
void purge(node* root){
    if (root != NULL){
        if (root->left != NULL)
            purge(root->left);
        if (root->right != NULL)
            purge(root->right);
        free(root);
    }
}

// Traversal procedure to list the current keys in the tree in order of value (from the left to the right)
void inOrder(node* root){
    if(root != NULL){
        inOrder(root->left);
        printf("\t[ %d ]\t", root->data);
        inOrder(root->right);
    }
}

void main(){

    // this reference don't change.
    // only the tree changes.
    node* root = NULL;
    int opt = -1;
    int data = 0;

    // event-loop.
    while (opt != 0){
        printf("\n\n[1] Insert Node\n[2] Delete Node\n[3] Find a Node\n[4] Get current Height\n[5] Print Tree in Crescent Order\n[0] Quit\n");
        scanf("%d",&opt); // reads the choice of the user

        // processes the choice
        switch(opt){
            case 1: printf("Enter the new node's value:\n");
                scanf("%d",&data);
                root = insert(root,data);
                break;

            case 2: printf("Enter the value to be removed:\n");
                if (root != NULL){
                    scanf("%d",&data);
                    root = delete(root,data);
                }
                else
                    printf("Tree is already empty!\n");
                break;

            case 3: printf("Enter the searched value:\n");
                scanf("%d",&data);
                find(root,data) ? printf("The value is in the tree.\n") : printf("The value is not in the tree.\n");
                break;

            case 4: printf("Current height of the tree is: %d\n", height(root));
                break;

            case 5: inOrder(root);
                break;
        }
    }

    // deletes the tree from the heap.
    purge(root);
}

二叉树的层次遍历（C语言）：

#include<stdio.h>
#include<malloc.h>

#define MaxSize 1024

typedef struct Node{                        //定义二叉链
    struct Node *lchild;                    //指向左孩子节点
    char data;                              //数据元素
    struct Node *rchild;                    //指向右孩子节点 
}BTNode;                                    //struct Node 的别名                        

typedef struct Quene{                       //定义顺序队 
    int front;                              //队头指针 
    BTNode *data[MaxSize];                  //存放队中元素 
    int rear;                               //队尾指针 
}SqQueue;                                   //struct Queue 的别名 

//初始化队列 
void initQueue(SqQueue * &q){
    q=(SqQueue *)malloc(sizeof(SqQueue));   //分配一个空间 
    q->front=q->rear=-1;                    //置 -1 
}

//判断队列是否为空
bool emptyQueue(SqQueue * &q){
    if(q->front==q->rear){                  //首指针和尾指针相等，说明为空 
        return true;                        //返回真 
    }
    else{
        return false;                       //返回假 
    }
}

//进队列
bool enQueue(SqQueue * &q,BTNode * &BT){
    if(q->rear==MaxSize-1){                 //判断队列是否满了 
        return false;                       //返回假 
    }
    q->rear++;                              //头指针加 1 
    q->data[q->rear]=BT;                    //传值 
    return true;                            //返回真 
}

//出队列 
bool deQueue(SqQueue * &q,BTNode * &BT){
    if(q->front==q->rear){                  //判断是否空了 
        return false;                       //返回假 
    }
    q->front++;                             //尾指针加 1 
    BT=q->data[q->front];                   //取值 
    return true;                            //返回真 
}

//创建二叉树 
int createBTNode(BTNode * &BT,char *str,int n){ 
    char ch=str[n];                             //把第 n 个字符赋给ch,方便后面判断 
    n=n+1;
    if(ch!='\0'){                               //如果 ch 不等于结束符就继续创建，否则就结束 
        if( ch=='#'){                           //以 # 号代表 NULL，下面没有了 
            BT = NULL;
        }
        else{
            BT = new BTNode;                    //新建一个二叉链 
            BT->data=ch;                        //把字符存入二叉链 
            n=createBTNode(BT->lchild,str,n);   //左递归创建 
            n=createBTNode(BT->rchild,str,n);   //右递归创建 
        }
    }
    return n;                                   //返回 n,记录字符串使用到哪里了 
}

//先序遍历
void preOrder(BTNode * &BT){
    if(BT!=NULL){                               //判断不为空 
        printf("%c",BT->data);                  //访问根节点
        preOrder(BT->lchild);                   //递归，先序遍历左子树 
        preOrder(BT->rchild);                   //递归，先序遍历右子树 
    }
}

//中序遍历
void inOrder(BTNode * &BT){
    if(BT!=NULL){
        inOrder(BT->lchild);
        printf("%c",BT->data);
        inOrder(BT->rchild);
    }
}

//后序遍历
void postOrder(BTNode * &BT){
    if(BT!=NULL){
        postOrder(BT->lchild);
        postOrder(BT->rchild);
        printf("%c",BT->data);
    }
}

//层次遍历 
void levelOrder(BTNode * &BT){
    SqQueue *q;                                 //定义队列 
    initQueue(q);                               //初始化队列 
    if(BT!=NULL){
        enQueue(q,BT);                          //根节点指针进队列 
    } 
    while(emptyQueue(q)!=true){                 //队不为空循环 
        deQueue(q,BT);                          //出队时的节点 
        printf("%c",BT->data);                  //输出节点存储的值 
        if(BT->lchild!=NULL){                   //有左孩子时将该节点进队列 
            enQueue(q,BT->lchild);
        }
        if(BT->rchild!=NULL){                   //有右孩子时将该节点进队列 
            enQueue(q,BT->rchild);
        }                                       //一层一层的把节点存入队列 
    }                                           //当没有孩子节点时就不再循环 
} 


int main(){
    
    //例子：ABDH###E##CF##G##
    BTNode *BT;
    printf("输入字符串：");
    char *str=(char *)malloc(sizeof(char) * 1024);
    scanf("%s",str); 
    createBTNode(BT,str,0);
    printf("二叉树建立成功\n");
    
    printf("先序遍历结果：");
    preOrder(BT);
    printf("\n");
    
    printf("中序遍历结果：");
    inOrder(BT);
    printf("\n");
    
    printf("后序遍历结果：");
    postOrder(BT);
    printf("\n");

    printf("层序遍历结果：");
    levelOrder(BT);
    printf("\n");
    
    return 0;
}

二叉树的线索化,看这篇文章：线索二叉树的创建及遍历(C语言实现)

#include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;

BiThrTree pre=NULL;

//采用前序初始化二叉树
//中序和后序只需改变赋值语句的位置即可
void CreateTree(BiThrTree * tree){
    char data;
    scanf("%c",&data);
    if (data!='#'){
        if (!((*tree)=(BiThrNode*)malloc(sizeof(BiThrNode)))){
            printf("申请结点空间失败");
            return;
        }else{
            (*tree)->data=data;//采用前序遍历方式初始化二叉树
            CreateTree(&((*tree)->lchild));//初始化左子树
            CreateTree(&((*tree)->rchild));//初始化右子树
        }
    }else{
        *tree=NULL;
    }
}
//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (pre&&!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//pre指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}
//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p)
{
    while(p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while(p->Ltag == Link){
            p = p->lchild;
        }
        printf("%c ", p->data);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while(p->Rtag == Thread && p->rchild !=NULL)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}

int main() {
    BiThrTree t;
    printf("输入前序二叉树:\n");
    CreateTree(&t);
    InThreading(t);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(t);
    return 0;
}

树的遍历的python实现

"""
This is pure Python implementation of tree traversal algorithms
"""
import queue
from typing import List


class TreeNode:
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None


def build_tree():
    print("\n********Press N to stop entering at any point of time********\n")
    check = input("Enter the value of the root node: ").strip().lower() or "n"
    if check == "n":
        return None
    q: queue.Queue = queue.Queue()
    tree_node = TreeNode(int(check))
    q.put(tree_node)
    while not q.empty():
        node_found = q.get()
        msg = "Enter the left node of %s: " % node_found.data
        check = input(msg).strip().lower() or "n"
        if check == "n":
            return tree_node
        left_node = TreeNode(int(check))
        node_found.left = left_node
        q.put(left_node)
        msg = "Enter the right node of %s: " % node_found.data
        check = input(msg).strip().lower() or "n"
        if check == "n":
            return tree_node
        right_node = TreeNode(int(check))
        node_found.right = right_node
        q.put(right_node)


def pre_order(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> pre_order(root)
    1 2 4 5 3 6 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    print(node.data, end=" ")
    pre_order(node.left)
    pre_order(node.right)


def in_order(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> in_order(root)
    4 2 5 1 6 3 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    in_order(node.left)
    print(node.data, end=" ")
    in_order(node.right)


def post_order(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> post_order(root)
    4 5 2 6 7 3 1 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.data, end=" ")


def level_order(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> level_order(root)
    1 2 3 4 5 6 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    q: queue.Queue = queue.Queue()
    q.put(node)
    while not q.empty():
        node_dequeued = q.get()
        print(node_dequeued.data, end=" ")
        if node_dequeued.left:
            q.put(node_dequeued.left)
        if node_dequeued.right:
            q.put(node_dequeued.right)


def level_order_actual(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> level_order_actual(root)
    1 
    2 3 
    4 5 6 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    q: queue.Queue = queue.Queue()
    q.put(node)
    while not q.empty():
        list = []
        while not q.empty():
            node_dequeued = q.get()
            print(node_dequeued.data, end=" ")
            if node_dequeued.left:
                list.append(node_dequeued.left)
            if node_dequeued.right:
                list.append(node_dequeued.right)
        print()
        for node in list:
            q.put(node)


# iteration version
def pre_order_iter(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> pre_order_iter(root)
    1 2 4 5 3 6 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    stack: List[TreeNode] = []
    n = node
    while n or stack:
        while n:  # start from root node, find its left child
            print(n.data, end=" ")
            stack.append(n)
            n = n.left
        # end of while means current node doesn't have left child
        n = stack.pop()
        # start to traverse its right child
        n = n.right


def in_order_iter(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> in_order_iter(root)
    4 2 5 1 6 3 7 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    stack: List[TreeNode] = []
    n = node
    while n or stack:
        while n:
            stack.append(n)
            n = n.left
        n = stack.pop()
        print(n.data, end=" ")
        n = n.right


def post_order_iter(node: TreeNode) -> None:
    """
    >>> root = TreeNode(1)
    >>> tree_node2 = TreeNode(2)
    >>> tree_node3 = TreeNode(3)
    >>> tree_node4 = TreeNode(4)
    >>> tree_node5 = TreeNode(5)
    >>> tree_node6 = TreeNode(6)
    >>> tree_node7 = TreeNode(7)
    >>> root.left, root.right = tree_node2, tree_node3
    >>> tree_node2.left, tree_node2.right = tree_node4 , tree_node5
    >>> tree_node3.left, tree_node3.right = tree_node6 , tree_node7
    >>> post_order_iter(root)
    4 5 2 6 7 3 1 
    """
    if not isinstance(node, TreeNode) or not node:
        return
    stack1, stack2 = [], []
    n = node
    stack1.append(n)
    while stack1:  # to find the reversed order of post order, store it in stack2
        n = stack1.pop()
        if n.left:
            stack1.append(n.left)
        if n.right:
            stack1.append(n.right)
        stack2.append(n)
    while stack2:  # pop up from stack2 will be the post order
        print(stack2.pop().data, end=" ")


def prompt(s: str = "", width=50, char="*") -> str:
    if not s:
        return "\n" + width * char
    left, extra = divmod(width - len(s) - 2, 2)
    return f"{left * char} {s} {(left + extra) * char}"


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(prompt("Binary Tree Traversals"))

    node = build_tree()
    print(prompt("Pre Order Traversal"))
    pre_order(node)
    print(prompt() + "\n")

    print(prompt("In Order Traversal"))
    in_order(node)
    print(prompt() + "\n")

    print(prompt("Post Order Traversal"))
    post_order(node)
    print(prompt() + "\n")

    print(prompt("Level Order Traversal"))
    level_order(node)
    print(prompt() + "\n")

    print(prompt("Actual Level Order Traversal"))
    level_order_actual(node)
    print("*" * 50 + "\n")

    print(prompt("Pre Order Traversal - Iteration Version"))
    pre_order_iter(node)
    print(prompt() + "\n")

    print(prompt("In Order Traversal - Iteration Version"))
    in_order_iter(node)
    print(prompt() + "\n")

    print(prompt("Post Order Traversal - Iteration Version"))
    post_order_iter(node)
    print(prompt())

平衡二叉树的python实现

"""
An auto-balanced binary tree!
"""
import math
import random


class my_queue:
    def __init__(self):
        self.data = []
        self.head = 0
        self.tail = 0

    def isEmpty(self):
        return self.head == self.tail

    def push(self, data):
        self.data.append(data)
        self.tail = self.tail + 1

    def pop(self):
        ret = self.data[self.head]
        self.head = self.head + 1
        return ret

    def count(self):
        return self.tail - self.head

    def print(self):
        print(self.data)
        print("**************")
        print(self.data[self.head : self.tail])


class my_node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

    def getdata(self):
        return self.data

    def getleft(self):
        return self.left

    def getright(self):
        return self.right

    def getheight(self):
        return self.height

    def setdata(self, data):
        self.data = data
        return

    def setleft(self, node):
        self.left = node
        return

    def setright(self, node):
        self.right = node
        return

    def setheight(self, height):
        self.height = height
        return


def getheight(node):
    if node is None:
        return 0
    return node.getheight()


def my_max(a, b):
    if a > b:
        return a
    return b


def leftrotation(node):
    r"""
            A                      B
           / \                    / \
          B   C                  Bl  A
         / \       -->          /   / \
        Bl  Br                 UB Br  C
       /
     UB
  
    UB = unbalanced node  
    """
    print("left rotation node:", node.getdata())
    ret = node.getleft()
    node.setleft(ret.getright())
    ret.setright(node)
    h1 = my_max(getheight(node.getright()), getheight(node.getleft())) + 1
    node.setheight(h1)
    h2 = my_max(getheight(ret.getright()), getheight(ret.getleft())) + 1
    ret.setheight(h2)
    return ret


def rightrotation(node):
    """
        a mirror symmetry rotation of the leftrotation
    """
    print("right rotation node:", node.getdata())
    ret = node.getright()
    node.setright(ret.getleft())
    ret.setleft(node)
    h1 = my_max(getheight(node.getright()), getheight(node.getleft())) + 1
    node.setheight(h1)
    h2 = my_max(getheight(ret.getright()), getheight(ret.getleft())) + 1
    ret.setheight(h2)
    return ret


def rlrotation(node):
    r"""
            A              A                    Br      
           / \            / \                  /  \
          B   C    RR    Br  C       LR       B    A
         / \       -->  /  \         -->    /     / \
        Bl  Br         B   UB              Bl    UB  C  
             \        /
             UB     Bl
    RR = rightrotation   LR = leftrotation
    """
    node.setleft(rightrotation(node.getleft()))
    return leftrotation(node)


def lrrotation(node):
    node.setright(leftrotation(node.getright()))
    return rightrotation(node)


def insert_node(node, data):
    if node is None:
        return my_node(data)
    if data < node.getdata():
        node.setleft(insert_node(node.getleft(), data))
        if (
            getheight(node.getleft()) - getheight(node.getright()) == 2
        ):  # an unbalance detected
            if (
                data < node.getleft().getdata()
            ):  # new node is the left child of the left child
                node = leftrotation(node)
            else:
                node = rlrotation(node)  # new node is the right child of the left child
    else:
        node.setright(insert_node(node.getright(), data))
        if getheight(node.getright()) - getheight(node.getleft()) == 2:
            if data < node.getright().getdata():
                node = lrrotation(node)
            else:
                node = rightrotation(node)
    h1 = my_max(getheight(node.getright()), getheight(node.getleft())) + 1
    node.setheight(h1)
    return node


def getRightMost(root):
    while root.getright() is not None:
        root = root.getright()
    return root.getdata()


def getLeftMost(root):
    while root.getleft() is not None:
        root = root.getleft()
    return root.getdata()


def del_node(root, data):
    if root.getdata() == data:
        if root.getleft() is not None and root.getright() is not None:
            temp_data = getLeftMost(root.getright())
            root.setdata(temp_data)
            root.setright(del_node(root.getright(), temp_data))
        elif root.getleft() is not None:
            root = root.getleft()
        else:
            root = root.getright()
    elif root.getdata() > data:
        if root.getleft() is None:
            print("No such data")
            return root
        else:
            root.setleft(del_node(root.getleft(), data))
    elif root.getdata() < data:
        if root.getright() is None:
            return root
        else:
            root.setright(del_node(root.getright(), data))
    if root is None:
        return root
    if getheight(root.getright()) - getheight(root.getleft()) == 2:
        if getheight(root.getright().getright()) > getheight(root.getright().getleft()):
            root = rightrotation(root)
        else:
            root = lrrotation(root)
    elif getheight(root.getright()) - getheight(root.getleft()) == -2:
        if getheight(root.getleft().getleft()) > getheight(root.getleft().getright()):
            root = leftrotation(root)
        else:
            root = rlrotation(root)
    height = my_max(getheight(root.getright()), getheight(root.getleft())) + 1
    root.setheight(height)
    return root


class AVLtree:
    def __init__(self):
        self.root = None

    def getheight(self):
        #        print("yyy")
        return getheight(self.root)

    def insert(self, data):
        print("insert:" + str(data))
        self.root = insert_node(self.root, data)

    def del_node(self, data):
        print("delete:" + str(data))
        if self.root is None:
            print("Tree is empty!")
            return
        self.root = del_node(self.root, data)

    def traversale(self):  # a level traversale, gives a more intuitive look on the tree
        q = my_queue()
        q.push(self.root)
        layer = self.getheight()
        if layer == 0:
            return
        cnt = 0
        while not q.isEmpty():
            node = q.pop()
            space = " " * int(math.pow(2, layer - 1))
            print(space, end="")
            if node is None:
                print("*", end="")
                q.push(None)
                q.push(None)
            else:
                print(node.getdata(), end="")
                q.push(node.getleft())
                q.push(node.getright())
            print(space, end="")
            cnt = cnt + 1
            for i in range(100):
                if cnt == math.pow(2, i) - 1:
                    layer = layer - 1
                    if layer == 0:
                        print()
                        print("*************************************")
                        return
                    print()
                    break
        print()
        print("*************************************")
        return

    def test(self):
        getheight(None)
        print("****")
        self.getheight()


if __name__ == "__main__":
    t = AVLtree()
    t.traversale()
    l = list(range(10))
    random.shuffle(l)
    for i in l:
        t.insert(i)
        t.traversale()

    random.shuffle(l)
    for i in l:
        t.del_node(i)
        t.traversale()

二叉树python实现：

class Node:  # This is the Class Node with a constructor that contains data variable to type data and left, right pointers.
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def display(tree):  # In Order traversal of the tree

    if tree is None:
        return

    if tree.left is not None:
        display(tree.left)

    print(tree.data)

    if tree.right is not None:
        display(tree.right)

    return


def depth_of_tree(
    tree,
):  # This is the recursive function to find the depth of binary tree.
    if tree is None:
        return 0
    else:
        depth_l_tree = depth_of_tree(tree.left)
        depth_r_tree = depth_of_tree(tree.right)
        if depth_l_tree > depth_r_tree:
            return 1 + depth_l_tree
        else:
            return 1 + depth_r_tree


def is_full_binary_tree(
    tree,
):  # This function returns that is it full binary tree or not?
    if tree is None:
        return True
    if (tree.left is None) and (tree.right is None):
        return True
    if (tree.left is not None) and (tree.right is not None):
        return is_full_binary_tree(tree.left) and is_full_binary_tree(tree.right)
    else:
        return False


def main():  # Main function for testing.
    tree = Node(1)
    tree.left = Node(2)
    tree.right = Node(3)
    tree.left.left = Node(4)
    tree.left.right = Node(5)
    tree.left.right.left = Node(6)
    tree.right.left = Node(7)
    tree.right.left.left = Node(8)
    tree.right.left.left.right = Node(9)

    print(is_full_binary_tree(tree))
    print(depth_of_tree(tree))
    print("Tree is: ")
    display(tree)


if __name__ == "__main__":
    main()

二叉查找树的python实现：

"""
A binary search Tree
"""


class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent  # Added in order to delete a node easier
        self.left = None
        self.right = None

    def __repr__(self):
        from pprint import pformat

        if self.left is None and self.right is None:
            return str(self.value)
        return pformat({"%s" % (self.value): (self.left, self.right)}, indent=1)


class BinarySearchTree:
    def __init__(self, root=None):
        self.root = root

    def __str__(self):
        """
        Return a string of all the Nodes using in order traversal
        """
        return str(self.root)

    def __reassign_nodes(self, node, new_children):
        if new_children is not None:  # reset its kids
            new_children.parent = node.parent
        if node.parent is not None:  # reset its parent
            if self.is_right(node):  # If it is the right children
                node.parent.right = new_children
            else:
                node.parent.left = new_children
        else:
            self.root = new_children

    def is_right(self, node):
        return node == node.parent.right

    def empty(self):
        return self.root is None

    def __insert(self, value):
        """
        Insert a new node in Binary Search Tree with value label
        """
        new_node = Node(value, None)  # create a new Node
        if self.empty():  # if Tree is empty
            self.root = new_node  # set its root
        else:  # Tree is not empty
            parent_node = self.root  # from root
            while True:  # While we don't get to a leaf
                if value < parent_node.value:  # We go left
                    if parent_node.left is None:
                        parent_node.left = new_node  # We insert the new node in a leaf
                        break
                    else:
                        parent_node = parent_node.left
                else:
                    if parent_node.right is None:
                        parent_node.right = new_node
                        break
                    else:
                        parent_node = parent_node.right
            new_node.parent = parent_node

    def insert(self, *values):
        for value in values:
            self.__insert(value)
        return self

    def search(self, value):
        if self.empty():
            raise IndexError("Warning: Tree is empty! please use another.")
        else:
            node = self.root
            # use lazy evaluation here to avoid NoneType Attribute error
            while node is not None and node.value is not value:
                node = node.left if value < node.value else node.right
            return node

    def get_max(self, node=None):
        """
        We go deep on the right branch
        """
        if node is None:
            node = self.root
        if not self.empty():
            while node.right is not None:
                node = node.right
        return node

    def get_min(self, node=None):
        """
        We go deep on the left branch
        """
        if node is None:
            node = self.root
        if not self.empty():
            node = self.root
            while node.left is not None:
                node = node.left
        return node

    def remove(self, value):
        node = self.search(value)  # Look for the node with that label
        if node is not None:
            if node.left is None and node.right is None:  # If it has no children
                self.__reassign_nodes(node, None)
            elif node.left is None:  # Has only right children
                self.__reassign_nodes(node, node.right)
            elif node.right is None:  # Has only left children
                self.__reassign_nodes(node, node.left)
            else:
                tmp_node = self.get_max(
                    node.left
                )  # Gets the max value of the left branch
                self.remove(tmp_node.value)
                node.value = (
                    tmp_node.value
                )  # Assigns the value to the node to delete and keep tree structure

    def preorder_traverse(self, node):
        if node is not None:
            yield node  # Preorder Traversal
            yield from self.preorder_traverse(node.left)
            yield from self.preorder_traverse(node.right)

    def traversal_tree(self, traversal_function=None):
        """
        This function traversal the tree.
        You can pass a function to traversal the tree as needed by client code
        """
        if traversal_function is None:
            return self.preorder_traverse(self.root)
        else:
            return traversal_function(self.root)


def postorder(curr_node):
    """
    postOrder (left, right, self)
    """
    node_list = list()
    if curr_node is not None:
        node_list = postorder(curr_node.left) + postorder(curr_node.right) + [curr_node]
    return node_list


def binary_search_tree():
    """
    Example
                  8
                 / \
                3   10
               / \    \
              1   6    14
                 / \   /
                4   7 13

    >>> t = BinarySearchTree().insert(8, 3, 6, 1, 10, 14, 13, 4, 7)
    >>> print(" ".join(repr(i.value) for i in t.traversal_tree()))
    8 3 1 6 4 7 10 14 13
    >>> print(" ".join(repr(i.value) for i in t.traversal_tree(postorder)))
    1 4 7 6 3 13 14 10 8
    >>> BinarySearchTree().search(6)
    Traceback (most recent call last):
    ...
    IndexError: Warning: Tree is empty! please use another.
    """
    testlist = (8, 3, 6, 1, 10, 14, 13, 4, 7)
    t = BinarySearchTree()
    for i in testlist:
        t.insert(i)

    # Prints all the elements of the list in order traversal
    print(t)

    if t.search(6) is not None:
        print("The value 6 exists")
    else:
        print("The value 6 doesn't exist")

    if t.search(-1) is not None:
        print("The value -1 exists")
    else:
        print("The value -1 doesn't exist")

    if not t.empty():
        print("Max Value: ", t.get_max().value)
        print("Min Value: ", t.get_min().value)

    for i in testlist:
        t.remove(i)
        print(t)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    # binary_search_tree()

参考文章

二叉树的非递归前序、中序、后序遍历算法详解及代码实现（C语言）

C语言二叉树常见操作详解

二叉树层次遍历

王道考研 数据结构

天勤数据结构高分笔记

王争数据结构和算法之美 个人笔记