二叉树、二叉排序树及其遍历

缺乏、安全感 2022-10-08 15:21 171阅读 0赞

### 文章目录 ###

*   *  先序创建二叉树
     *  二叉树的中序、后须、层次遍历
     *  二叉排序树的建立

## 先序创建二叉树 ##

/*二叉链表存储结构*/
    typedef struct BiTNode {
        
        TElemType data;
        struct BiTNode* lchid, * rchid;
    }BiTNode,*BiTree;
    
    /*先序创建二叉树*/
    BiTree CreateBiTree(){
        
        BiTree T;//根节点
        TElemType item;
        cin >> item;
        if (item == '#') {
         //叶节点数据标志
            T = NULL;  //若某一节点为叶子节点，则其左右子树均为NULL，0表示建空树
        }
        else {
        
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = item;
            T->lchid = CreateBiTree();
            T->rchid = CreateBiTree();
        }
        return T;
    }

## 二叉树的中序、后须、层次遍历 ##

/*非递归中序遍历*/
    void InOrderTraverse(BiTree t)
    {
        
        SqStack S;
        InitStack(S);
        BiTree p = t;
        while (p||!StackEmpty(S))
        {
        
            if (p) {
        
                Push(S, (SElemType)p);
                p = p->lchid;
            }
            else {
        
                Pop(S, (SElemType&)p);
                cout << p->data;
                p = p->rchid;
            }
        }
    
        
    }
    /*递归后序遍历*/
    void PostOrder(BiTree t) {
        
        if (t) {
        
            PostOrder(t->lchid);
            PostOrder(t->rchid);
            cout << t->data;
       }
    }
    
    /*递归层序遍历*/
    void LevelOrder(BiTree t)
    {
        
        if (t)
        {
        
            LinkQueue  Q;
            InitQueue(Q); //设置一空队列        
            EnQueue(Q, (int)t); //根结点入队
            while (!QueueEmpty(Q)) //当队非空时重复执行下列操作
            {
        
                DeQueue(Q, (int&)t);
                // Visit(p->data); //出队访问
                cout << t->data;
                if (t->lchid) {
        
                    EnQueue(Q, (QElemType)t->lchid);
                }
                if (t->rchid) {
        
                    EnQueue(Q, (QElemType)t->rchid);
                }
            }
            DestoryQueue(Q);
        }
    }

## 二叉排序树的建立 ##

/*二叉链表存储结构*/
    typedef struct BiTNode {
        
    	int data;
    	struct BiTNode* lchild, * rchild;
    }BiTNode, * BiTree;
    
    int SearchBST(BiTree T, int key, BiTree f, BiTree& p)
    //查找成功，参数p指向查找到的结点，f指向它的双亲；否则p指向key应插入的父结点或指向空（当T为空时）
    {
        
    	if (!T)
    	{
        
    		p = f;
    		return 0;
    	}
    	else if (key == T->data)
    	{
        
    		p = T;
    		return 1;
    	}
    	else if (key < T->data)
    		return (SearchBST(T->lchild, key, T, p));
    	else
    		return (SearchBST(T->rchild, key, T, p));
    }
    
    
    int InsertBST(BiTree& T, int e)
    //在二叉排序树中插入值为elem的元素，T指向二叉排序树根结点
    {
        
    	BiTree p = NULL, f = NULL;
    	if (!SearchBST(T, e, f, p)) // 如果查找不成功
    	{
        
    		BiTree s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = e;
    		s->lchild = s->rchild = NULL;
    		if (!p) // 若二叉树为空被插结点作为树的根结点
    			T = s; 
    		else if (e< p->data) //被插结点插入到p的左子树中
    			p->lchild = s;
    		
    		else  //被插结点插入到p的右子树中
    			p->rchild = s; 
    		return 1;
    	}
    	else // 查找成功,不插
    		return 0; 
    }